We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Next Greater Element II

Number: 503

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Bloomberg, Apple, Microsoft, Intuit, Goldman Sachs, TikTok, Uber, Yahoo, Nvidia, Adobe

Problem Description

Given a circular integer array nums, for every element, find the next number in the traversal order that is greater than that element. If no such element exists, return -1 for that position.

Key Insights

  • Because the array is circular, we simulate the wrap-around by iterating over the array twice.
  • A monotonic stack (decreasing order) is used to efficiently track the next greater element.
  • Process elements in reverse order to handle dependencies correctly.
  • Each element is pushed and popped at most once, yielding an efficient solution.

Space and Time Complexity

Time Complexity: O(n), since each element is processed a constant number of times. Space Complexity: O(n), used for the result array and the stack.

Solution

This solution employs a monotonic stack to find the next greater element efficiently. We traverse the array twice (using modulo arithmetic to simulate circular behavior) from right to left. For each element, we pop elements from the stack until we find one that is greater than the current element. If such an element exists, it is the next greater element; otherwise, the result remains -1. Finally, we push the current index to the stack. This approach guarantees that every element is considered only a few times.

Code Solutions

# Python solution
def nextGreaterElements(nums):
    n = len(nums)
    result = [-1] * n  # Initialize result list with -1
    stack = []  # Stack to store indices

    # Traverse the list twice to account for circularity
    for i in range(2 * n - 1, -1, -1):
        current_index = i % n  # Get current index in circular manner
        # Remove elements that are less than or equal to nums[current_index]
        while stack and nums[stack[-1]] <= nums[current_index]:
            stack.pop()
        # If stack is not empty, the top element is the next greater element
        if stack:
            result[current_index] = nums[stack[-1]]
        # Push current index to the stack for future comparisons
        stack.append(current_index)
    
    return result

# Example usage:
# nums = [1, 2, 1]
# print(nextGreaterElements(nums))  # Output: [2, -1, 2]
← Back to All Questions