Introduction

The Next Greater Element problem involves finding the first greater element to the right of every array element.

Given an array:

 [arr1, arr2, arr3 ...]

the task is to:

  • find the next greater element
    for every position

If no greater element exists:

  • return -1

This problem is one of the most important applications of:

Monotonic Stack

This problem helps in understanding:

  • stack optimization
  • linear traversal
  • next greater patterns
  • efficient searching

Example

Input:arr = [4,5,2,10]

Output:
[5,10,10,-1]

Explanation:
4 → next greater is 5
5 → next greater is 10
2 → next greater is 10
10 → no greater element

Constraints

 1 <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force Traversal

Explanation

The simplest way is:

  1. Traverse every element
  2. Search right side
  3. Find first greater element

This works but repeated searching becomes inefficient.

Steps

  1. Traverse array.
  2. For each element:
    • search right side
  3. Store first greater element.
  4. Return answer array.

Dry Run

Input:[4,5,2,10]

For 4:
5 is greater

For 5:
10 is greater

For 2:
10 is greater

For 10:
No greater element

Result:
[5,10,10,-1]

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
Nested traversal occurs repeatedly.

Space Complexity: O(1)
Explanation:
Only output array is used.

Approach 2 : Monotonic Stack

Explanation

The optimized solution uses:

 Monotonic Decreasing Stack

Idea:

  • maintain decreasing stack
  • whenever larger element appears:
    • it becomes next greater element

Process:

  1. Traverse from right to left
  2. Remove smaller elements
  3. Stack top becomes next greater element
  4. Push current element

This avoids repeated searching.

Steps

  1. Create stack.
  2. Traverse array from right.
  3. Remove smaller elements.
  4. Store next greater element.
  5. Push current element.

Dry Run

Input:[4,5,2,10]

Traverse from right:
10 → no greater

Stack:
[10]
2 → next greater is 10

Stack:
[10,2]
5 → remove 2

Next greater:
10
4 → next greater:
5

Final Result:
[5,10,10,-1]

Monotonic Stack Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is pushed and popped once.

Space Complexity: O(n)
Explanation:
Stack stores array elements.

Edge Cases

  1. Strictly decreasing array
  2. Strictly increasing array
  3. Duplicate values
  4. Single element array
  5. Large input size

Why This Problem is Important

Next Greater Element helps in understanding:

  1. Monotonic stacks
  2. Stack optimization
  3. Linear traversal
  4. Efficient searching
  5. Pattern-based problems

It is one of the most important monotonic stack interview problems.

Real-World Applications

Next greater concepts are used in:

  1. Stock market systems
  2. Temperature forecasting
  3. Signal analysis
  4. Resource monitoring
  5. Streaming data systems

Common Mistakes

  1. Incorrect stack condition
  2. Forgetting right-to-left traversal
  3. Wrong monotonic order
  4. Missing default -1 assignment

Interview Tips

Interviewers often expect:

  1. Monotonic stack explanation
  2. Linear optimization reasoning
  3. Stack pop condition understanding

Always explain:

  • why decreasing stack is maintained
  • how smaller elements are removed
  • why each element is processed once

Related Questions

  1. Daily Temperatures
  2. Stock Span Problem
  3. Largest Rectangle in Histogram
  4. Trapping Rain Water
  5. Next Smaller Element

Final Takeaway

The Next Greater Element problem is a fundamental monotonic stack problem that teaches efficient next-greater searching and stack optimization techniques. Understanding this problem builds a strong foundation for advanced stack and linear traversal interview problems.