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 IV

Number: 2549

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed array of non-negative integers, for each element you must find its "second greater" integer. For an element nums[i], its second greater integer is defined as the first element nums[j] (with j > i) that is greater than nums[i] such that there is exactly one index k (with i < k < j) for which nums[k] > nums[i]. If no such element exists, return -1 for that index.

Key Insights

  • Use a two-phase scanning technique with monotonic stacks.
  • Maintain one stack (stack1) for elements waiting to find their first greater element.
  • Maintain a second stack (stack2) for indices that have already found the first greater element and are awaiting the second.
  • When processing a new element, pop from stack2 while the current element is greater than the top, assigning it as the second greater.
  • Meanwhile, pop eligible indices from stack1, push them to stack2 (since the current element becomes their first greater), and then add the current index to stack1.
  • This method processes each index efficiently in one pass.

Space and Time Complexity

Time Complexity: O(n) in average case, because each element is pushed and popped at most once. Space Complexity: O(n) for the stacks used.

Solution

We use two monotonic stacks to track the indices of numbers waiting for their first and second greater elements. As we iterate over nums:

  1. For every new number, check the stack for indices waiting for the second greater element (stack2). If the current number is greater than the top of stack2, then assign it as the answer for that index.
  2. Then process indices in stack1 (waiting for the first greater element). If the current number is greater than the number at the top index in stack1, pop that index and record it temporarily.
  3. Those popped indices now have their first greater element found, so push them into stack2 to wait for the second greater element.
  4. Finally, push the current index into stack1 as a candidate awaiting its first greater element.

This approach leverages the properties of a monotonic decreasing stack to efficiently determine, in a single pass, both the first and second greater elements for each index.

Code Solutions

# Python code for Next Greater Element IV

def secondGreaterElement(nums):
    n = len(nums)
    answer = [-1] * n  # Initialize answer array with -1
    stack1 = []  # Stack for indices waiting to find the first greater element
    stack2 = []  # Stack for indices that already have a first greater element, waiting for the second

    # Iterate over each element with its index
    for i, num in enumerate(nums):
        # Process the second greater element candidates in stack2
        while stack2 and num > nums[stack2[-1]]:
            idx = stack2.pop()
            answer[idx] = num

        # Temporary list to hold indices from stack1 that now found the first greater element
        temp = []
        while stack1 and num > nums[stack1[-1]]:
            temp.append(stack1.pop())
        # Move them to stack2 to await their second greater element
        for idx in temp:
            stack2.append(idx)

        # Push the current index into stack1
        stack1.append(i)

    return answer

# Example usage:
print(secondGreaterElement([2,4,0,9,6]))  # Output: [9,6,6,-1,-1]
← Back to All Questions