How to Solve: Next Greater Element

How to Solve: Next Greater Element

(A Complete FAANG-Level Interview Guide)

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—master it, and you’ll solve problems in O(n) time while others struggle with brute force. It’s the secret weapon for stacks, arrays, and even dynamic programming follow-ups."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you’re comfortable with: 1. Stacks (LIFO) – Push/pop operations, monotonic stacks. 2. Hash Maps (Dictionaries) – O(1) lookups, storing indices/values. 3. Circular Arrays – Modulo arithmetic for wrap-around traversal.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental Checklist (Run This for Every Problem): 1. Clarify the Problem
- Is the array circular? (If yes, use modulo % n.)
- Are we finding next greater or next smaller?
- Should we return indices or values?
- Are duplicates allowed? (If yes, handle ties carefully.)

1. Choose the Right Data Structure
2. Stack → For monotonic traversal (O(n) time).
3. Hash Map → To store results (O(1) lookups).

4. Array → For storing answers (pre-allocate -1 or 0).

5. Initialize Variables

6. stack = [] (empty stack).
7. result = [-1] len(nums) (default: no next greater).

8. map = {} (if tracking indices).

9. Traverse the Array

10. Forward Pass (for next greater to the right):
    python
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
11. Backward Pass (for next greater to the left):
    python
for i in range(len(nums)-1, -1, -1):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)

12. Circular Array (two passes or modulo):
    python
for i in range(2 len(nums)):
idx = i % len(nums)
while stack and nums[stack[-1]] < nums[idx]:
result[stack.pop()] = nums[idx]
stack.append(idx)

13. Handle Edge Cases

14. Empty array → Return [].
15. All elements equal → Return [-1, -1, ...].

16. Single element → Return [-1].

17. Optimize for Follow-Ups

18. If asked for next greater in both directions, run two passes.

19. If asked for next greater with constraints, use DP or sliding window.

20. Verify Time & Space Complexity

21. Time: O(n) (each element pushed/popped once).
22. Space: O(n) (stack + result array).

? WORKED EXAMPLES

Example 1 – Basic: Next Greater Element I

Problem: Given two arrays nums1 and nums2, return an array answer where answer[i] is the next greater element of nums1[i] in nums2. If no such element exists, return -1.

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

Output: [-1,3,-1]

Solution (Hash Map + Stack):

def nextGreaterElement(nums1, nums2):

    stack = []

    next_greater = {}


    for num in nums2:

        while stack and stack[-1] < num:

            next_greater[stack.pop()] = num

        stack.append(num)


    return [next_greater.get(num, -1) for num in nums1]

Why This Works: - We traverse nums2 once, using a monotonic stack to track the next greater element for each value. - The hash map stores the next greater element for O(1) lookups. - Time: O(n + m) (n = len(nums2), m = len(nums1)). - Space: O(n) (stack + hash map).

Example 2 – Medium: Next Greater Element II (Circular Array)

Problem: Given a circular array nums, return the next greater number for every element. The next greater number is the first number to its right that is greater. If it doesn’t exist, return -1.

Input: nums = [1,2,1]

Output: [2,-1,2]

Solution (Two-Pass Stack):

def nextGreaterElements(nums):

    n = len(nums)

    result = [-1]  n

    stack = []


    for i in range(2  n):

        idx = i % n

        while stack and nums[stack[-1]] < nums[idx]:

            result[stack.pop()] = nums[idx]

        stack.append(idx)


    return result

Why This Works: - We simulate a circular array by traversing 2n elements (modulo % n). - The monotonic stack ensures we find the next greater element in O(n) time. - Time: O(n) (each element pushed/popped at most twice). - Space: O(n) (stack + result array).

Example 3 – Hard/Follow-Up: Next Greater Element III (With Constraints)

Problem: Given a positive integer n, find the smallest integer greater than n with the same digits. If no such number exists, return -1.

Input: n = 12

Output: 21

Solution (Stack + Greedy):

def nextGreaterElement(n):

    digits = list(str(n))

    stack = []

    pivot = -1


    # Step 1: Find the pivot (first digit smaller than its successor)

    for i in range(len(digits)-1, 0, -1):

        if digits[i] > digits[i-1]:

            pivot = i-1

            break

    if pivot == -1:

        return -1


    # Step 2: Find the smallest digit > digits[pivot] to the right

    for i in range(len(digits)-1, pivot, -1):

        if digits[i] > digits[pivot]:

            digits[i], digits[pivot] = digits[pivot], digits[i]

            break


    # Step 3: Reverse the suffix after pivot

    digits[pivot+1:] = digits[pivot+1:][::-1]


    result = int(''.join(digits))

    return result if result < 231 else -1

Why This Works: - We use a stack-like approach to find the pivot (first digit that can be swapped). - Greedy swap ensures the smallest possible number. - Reverse the suffix to get the smallest lexicographical order. - Time: O(n) (n = number of digits). - Space: O(n) (digits array).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. The next greater element problem is all about monotonic stacks and hash maps. Here’s the playbook:

1. Clarify: Is the array circular? Are we returning indices or values?
2. Initialize: A stack, a result array filled with -1, and (if needed) a hash map.
3. Traverse: Forward for next greater to the right, backward for next greater to the left. For circular arrays, go 2n times with modulo.
4. Pop & Store: While the stack isn’t empty and the current element is greater, pop and record the result.
5. Edge Cases: Empty array? All equal? Single element? Handle them upfront.

This pattern shows up in LeetCode 496, 503, 556, 739—master it, and you’ll crush stack-based problems in interviews. Now go practice!

? FINAL TIPS

• Practice Variations: Try "Next Smaller Element" (just flip the inequality).
• Whiteboard First: Sketch the stack state at each step.
• Time Yourself: Aim for <15 minutes per problem.

You’ve got this! ?