Next Greater Element II

LeetCode 503 | Difficulty: Medium

Medium

Problem Description

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

Constraints:

- `1 <= nums.length <= 10^4`

- `-10^9 <= nums[i] <= 10^9`

Topics: Array, Stack, Monotonic Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

---

Solutions

Solution 1: C# (Best: 152 ms)

Metric	Value
Runtime	152 ms
Memory	47.7 MB
Date	2022-01-18

Solution

public class Solution {
    public int[] NextGreaterElements(int[] nums) {
        int n = nums.Length;
    Stack<int> s = new Stack<int>();
    int[] result = new int[nums.Length];
    for (int i = 0; i < n; i++)
    {
        result[i] = -1;
    }
    
    for (int i = 0; i < n*2; i++)
    {
        while(s.Count != 0 && nums[s.Peek()] < nums[i%n])
        result[s.Pop()] = nums[i%n];
        s.Push(i%n);
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?