Next Greater Element II: Two Approaches

First Solution

Brute force approach. Time complexity O(N²).

For each element, scan from the start and record indices of larger elements. When we’re to the left of the target element, always update. When we’re to the right, break once we find a match. Set to -1 if no match exists.

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res;
        for(int i=0;i<nums.size();++i) {
            int idx = -2;
            for(int j=0;j<nums.size();++j) {
                if (nums[j]>nums[i]) {
                    if (j < i && idx < 0) {
                        idx = j;
                    } else if (j > i) {
                        idx = j;
                        break;
                    }
                }
            }
            
            if (idx < 0)
                res.push_back(-1);
            else
                res.push_back(nums[idx]);
        }
        return res;
    }
};

Optimal Solution Using Stack

Time complexity: O(N) Space complexity: O(N)

#define MAX_NUMS 10000

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        bitset<MAX_NUMS> bs;
        stack<int> s;
        
        // Start from the right side
        for(int j=nums.size()-1;j>=0;--j) {
            // Scan from right to left, keep largest element at top
            while (!s.empty() && nums[s.top()] <= nums[j]) s.pop();

            if (!s.empty()) {
                res[j] = nums[s.top()];
                // Mark elements found in first pass
                bs[j] = 1;
            }
            
            s.push(j);
        }
        
        // Use existing stack to find remaining elements
        for(int j=nums.size()-1;j>0;--j) {
            // Only look for those not found yet
            if (bs[j] == 0) {
                while(!s.empty() && nums[j] >= nums[s.top()]) s.pop();
                
                if (!s.empty()) res[j] = nums[s.top()];
            }
        }
        
        return res;
    }
};

Think of the array as segmented. Circular search splits the array like this:

A….B element….C becomes B element ….C A…

Scanning from right to left saves computation.

Key Insight

I optimized space complexity beyond the standard solution by using a compact bitset to mark found elements, reducing memory overhead while maintaining optimal time performance.

#stack

Minimum Cost for Tickets: A Dynamic Programming Approach Palindrome Partitioning with Backtracking