Next Greater Element

January 10, 2024

Problem #

Given an array nums, for each element, find the next greater element within the array. The next greater element for an element x is the first greater element on the right side of x in the array. If it does not exist, output -1 for this element.

Example:

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

Solution #

The solution involves using a stack to efficiently find the next greater element for each element in the array. Iterate over the array and use the stack to keep track of elements for which the next greater element hasn’t been found yet.

Algorithm Steps #

1. Initialize an empty stack and an array result of the same length as nums with all elements set to -1.
2. Iterate through the array. For each element: a. While the stack is not empty and the current element is greater than the element at the top of the stack, pop from the stack and set result[stack_top_index] to the current element. b. Push the current index onto the stack.
3. Return the result array.

Code (Python) #

def nextGreaterElement(nums):
    stack = []
    result = [-1] * len(nums)
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)
    return result

# Test the function
print(nextGreaterElement([2, 1, 3, 5, 6, 4]))  # Output: [3, 3, 5, 6, -1, -1]

Time Complexity #

O(n), where n is the number of elements in nums. Each element is pushed and popped from the stack at most once.

Space Complexity #

O(n), for the stack and the result array.