algoadvance

Leetcode 503. Next Greater Element II

Problem Statement

You are given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]). You need to return the next greater number for each 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:

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`.

Strategy

  1. Understanding Circular Nature: Since the array is circular, when we reach the end, we need to continue the search from the beginning.
  2. Monotonic Decreasing Stack: We use a stack to keep track of indices where the next greater element hasn’t been found yet. This stack will help keep track of elements in a decreasing manner.
  3. Two-pass Simulation: By simulating a circular array by iterating twice over the array, we ensure that all elements are properly considered for their next greater elements.

Time Complexity

The time complexity of this approach is O(n) because each element is pushed and popped from the stack at most once.

Code

#include <vector>
#include <stack>
#include <iostream>

using namespace std;

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk;

    // We iterate twice over the array to simulate circular behavior
    for (int i = 0; i < 2 * n; ++i) {
        while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
            result[stk.top()] = nums[i % n];
            stk.pop();
        }
        if (i < n) {
            stk.push(i);
        }
    }
    
    return result;
}

int main() {
    vector<int> nums = {1, 2, 1};
    vector<int> result = nextGreaterElements(nums);

    for (int i : result) {
        cout << i << " ";
    }
    return 0;
}

Explanation:

  1. Stack Initialization: A stack is used to keep the indices of elements for which we’re trying to find the next greater element.
  2. Two-Pass Loop: We iterate the array twice using i % n to handle the circular nature.
  3. Stack Operations: Inside the loop, if nums[i % n] is greater than the element at the index stored at the top of the stack, we assign that value to the result for the element at that index, and continue until the condition breaks.
  4. Push Indices: Push current index i to the stack only during the first pass to prevent duplicate processing.

This ensures the correct next greater element is found for each index in the circular array or returns -1 if no such element exists.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI