8.10 Next Greater Element with Position Offset

8.10.1 Metadata

8.10.2 Description

Given an integer array readings, return an array result where result[i] = [value, distance], with value being the next greater element to the right of readings[i] and distance being the index difference. If no greater element exists, return [-1, -1].

Example:

Input:

readings = [2, 1, 2, 4, 3]

Output:

[[4, 3], [2, 1], [4, 1], [-1, -1], [-1, -1]]

Explanation:

For each index i in readings:

  • i=0, value=2. The next greater element to its right is 4 at index 3, so distance = 3 - 0 = 3, result is [4, 3].
  • i=1, value=1. The next greater element is 2 at index 2, distance = 2 - 1 = 1, result is [2, 1].
  • i=2, value=2. The next greater element is 4 at index 3, distance = 3 - 2 = 1, result is [4, 1].
  • i=3, value=4. There is no greater element to the right, result is [-1, -1].
  • i=4, value=3. There is no greater element to the right, result is [-1, -1].

Input Format:

The first line contains an integer n denoting length of array. The next n lines denote the elements in array.

Constraints:

  • \(0 \le\) readings.length \(\le 100000\)
  • \(-1000000000 \le\) readings[i] \(\le 1000000000\)

8.10.3 Walkthrough

This is a classic “next greater element” problem that uses a monotonic stack pattern to efficiently find the next greater element for each position along with the distance.

Key Insight:

A monotonic stack (decreasing in this case) allows us to process elements in a single pass. When we encounter a larger element, we know it’s the “next greater element” for all smaller elements still waiting in the stack. By storing indices instead of values, we can: 1. Look up the original value in the readings array 2. Calculate the distance between indices 3. Update the correct position in the result array

Strategy:

  • Use a stack to store indices (not values) of elements waiting to find their next greater element
  • Maintain the stack in decreasing order by the values at those indices
  • When we encounter a larger element at index i, it becomes the “next greater element” for all indices in the stack with smaller values
  • Pop those indices and update their results with [readings[i], i - stackIndex]
  • Push current index onto stack
  • Elements remaining in stack have no next greater element (already initialized to [-1, -1])

Example trace for readings = [2, 1, 2, 4, 3]:

Initial: result = [[-1,-1], [-1,-1], [-1,-1], [-1,-1], [-1,-1]]
         stack = []

i=0, readings[0]=2:
  - Stack empty, push index 0
  - stack = [0]

i=1, readings[1]=1:
  - 1 is not greater than readings[0]=2, push index 1
  - stack = [0, 1]

i=2, readings[2]=2:
  - 2 > readings[1]=1, pop index 1
    → result[1] = [2, 2-1] = [2, 1]
  - 2 is not greater than readings[0]=2, push index 2
  - stack = [0, 2]
  - result = [[-1,-1], [2,1], [-1,-1], [-1,-1], [-1,-1]]

i=3, readings[3]=4:
  - 4 > readings[2]=2, pop index 2
    → result[2] = [4, 3-2] = [4, 1]
  - 4 > readings[0]=2, pop index 0
    → result[0] = [4, 3-0] = [4, 3]
  - Stack empty, push index 3
  - stack = [3]
  - result = [[4,3], [2,1], [4,1], [-1,-1], [-1,-1]]

i=4, readings[4]=3:
  - 3 is not greater than readings[3]=4, push index 4
  - stack = [3, 4]

Final: Indices 3 and 4 remain in stack (no next greater element)
       result = [[4,3], [2,1], [4,1], [-1,-1], [-1,-1]]

8.10.4 Analysis

Time Complexity: \(O(n)\) where n is the length of the readings array. Although we have a nested while loop inside the for loop, each element is pushed onto the stack exactly once and popped at most once. The total number of push and pop operations across all iterations is \(O(n)\).

Space Complexity: \(O(n)\) for the stack in the worst case. If the array is in strictly decreasing order (e.g., [5, 4, 3, 2, 1]), all indices will be pushed onto the stack and remain there until the end. We also use \(O(n)\) space for the result array.

8.10.5 Implementation Steps

  1. Handle edge case: If readings is empty or null, return result with single [-1, -1] entry

  2. Initialize data structures:

    • Create result lc-list, initializing each entry with immutable [-1, -1] (note: will use set() to update)
    • Create a stack to store indices of elements waiting to find their next greater element

  3. Process array from left to right (index i from 0 to n-1):

    • Get current value at index i
    • While stack is not empty AND current value is greater than value at stack top index:
      • Pop the index (prevIdx) from stack
      • Update result at prevIdx: set index 0 to current value, set index 1 to distance (i - prevIdx)
    • Push current index i onto stack

  4. No post-processing needed: Elements still in stack already have [-1, -1] from initialization

  5. Return result array

8.10.6 Java Code

class Result {

    /*
     * Complete the 'findNextGreaterElementsWithDistance' function below.
     *
     * The function is expected to return a 2D_INTEGER_ARRAY.
     * The function accepts INTEGER_ARRAY readings as parameter.
     */

    public static List<List<Integer>> findNextGreaterElementsWithDistance(List<Integer> readings) {
        List<List<Integer>> result = new ArrayList<>();
        if(readings == null || readings.size() == 0) {
            result.add(Arrays.asList(new Integer[]{-1, -1}));
            return result;
        }
        
        // Write your code here
        Stack<Integer> stack = new Stack<>();
        
        
        //initialize the 2d array
        for(int reading : readings) {
            result.add(Arrays.asList(new Integer[]{-1, -1}));
        }
        
        // Process each element
        for (int i = 0; i < readings.size(); i++) {
            int val = readings.get(i);
            
            // While current element is greater than element at stack top index
            while (!stack.isEmpty() && val > readings.get(stack.peek())) {
                int prevIdx = stack.pop();
                // Update result for prevIndex with [value, distance]
                result.get(prevIdx).set(0, val);
                result.get(prevIdx).set(1, i - prevIdx);
            }

            // Push current index onto stack
            stack.push(i);
        }
        
        return result;
    }

}