Introduction

The Next Greater Element I problem involves finding the next greater element for each number.

Given:

  • nums1
  • nums2

Rules:

  • for every element in nums1
    find the first greater element
    to its right in nums2
  • 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 traversal
  • monotonic patterns
  • next greater logic
  • efficient searching

Example

Input:nums1 = [4,1,2]
nums2 = [1,3,4,2]

Output:
[-1,3,-1]

Explanation:
4 → no greater element
1 → next greater is 3
2 → no greater element

Constraints

1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 10^4
All integers are unique

Approach 1 : Brute Force Traversal

Explanation

The simplest way is:

  1. Find element position in nums2
  2. Traverse right side
  3. Find first greater element

This works but repeated scanning is inefficient.

Steps

  1. Traverse nums1.
  2. Locate element in nums2.
  3. Search right side.
  4. Store next greater element.
  5. Return result array.

Dry Run

nums1:[4,1,2]
nums2:
[1,3,4,2]

For 4:
No greater element

For 1:
3 is greater

For 2:
No greater element

Result:
[-1,3,-1]

Brute Force Code

Complexity Analysis

Time Complexity: O(n * m)
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 nums2
  2. Resolve smaller stack elements
  3. Store mappings
  4. Build result using hashmap

This avoids repeated searching.

Steps

  1. Create stack.
  2. Traverse nums2.
  3. Pop smaller elements.
  4. Store next greater mapping.
  5. Build answer using hashmap.

Dry Run

nums2:[1,3,4,2]

Stack:
[]
Push 1

Stack:
[1]

Encounter 3
3 > 1

Mapping:
1 → 3
Push 3
Encounter 4
4 > 3

Mapping:
3 → 4

Final Mapping:
1 → 3
3 → 4
4 → -1
2 → -1

Monotonic Stack Code

Complexity Analysis

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

Space Complexity: O(m)
Explanation:
Stack and hashmap are used.

Edge Cases

  1. No greater element
  2. Strictly decreasing array
  3. Single element array
  4. Greater element immediately next
  5. Large arrays

Why This Problem is Important

Next Greater Element I helps in understanding:

  1. Monotonic stacks
  2. Stack-based optimization
  3. Efficient searching
  4. Next greater patterns
  5. Linear traversal optimization

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

Real-World Applications

Next greater concepts are used in:

  1. Stock market analysis
  2. Temperature forecasting
  3. Signal processing
  4. Performance monitoring
  5. Sliding window systems

Common Mistakes

  1. Incorrect stack condition
  2. Forgetting remaining elements
  3. Wrong hashmap updates
  4. Using increasing stack instead

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 next greater elements are resolved
  • why each element is processed once

Related Questions

  1. Valid Parentheses
  2. Min Stack
  3. Implement Stack using Queue
  4. Daily Temperatures
  5. Largest Rectangle in Histogram

Final Takeaway

The Next Greater Element I 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 monotonic stack and linear traversal interview problems.