# 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**:

- 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 #

- Initialize an empty stack and an array
`result`

of the same length as`nums`

with all elements set to -1. - 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. - 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.