Next Greater Element

📌 Definition:

📖 Detailed Explanation:

A monotonic decreasing stack of indices solves this in one pass: for each element, pop every index whose value is smaller (the current element is their answer), then push the current index. Any indices left on the stack have no greater element. O(n) time — each index is pushed and popped once.

💻 Solutions:

• Java
• JavaScript
• Python

public static int[] nextGreater(int[] a) {
    int[] res = new int[a.length];
    java.util.Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // indices
    for (int i = 0; i < a.length; i++) {
        while (!stack.isEmpty() && a[i] > a[stack.peek()])
            res[stack.pop()] = a[i];
        stack.push(i);
    }
    return res;
}

function nextGreater(a) {
  const res = new Array(a.length).fill(-1);
  const stack = []; // indices
  for (let i = 0; i < a.length; i++) {
    while (stack.length && a[i] > a[stack[stack.length - 1]])
      res[stack.pop()] = a[i];
    stack.push(i);
  }
  return res;
}

def next_greater(a):
    res = [-1] * len(a)
    stack = []  # indices
    for i, x in enumerate(a):
        while stack and x > a[stack[-1]]:
            res[stack.pop()] = x
        stack.append(i)
    return res

🔑 Key Points:

• Monotonic decreasing stack of indices
• Pop smaller elements — current is their answer
• Leftover indices get -1
• O(n) time, O(n) space

🌍 Real-World Example: