Next Greater Element

Problem Statement

Given an array, find the next greater element for each element in the array. If no greater exists, return -1.

Example: nums = [4,5,2,25] → Output: [5,25,25,-1]

Approach 1: Brute Force

Explanation: For each element, scan all elements to the right for a greater number.

Time Complexity: O(n²)

Space Complexity: O(n) for output

result = []
for i in 0..n-1:
    next = -1
    for j in i+1..n-1:
        if nums[j] > nums[i]:
            next = nums[j]
            break
    result.append(next)
return result

💡 Think: For each index, linearly search rightward for the first larger.

Approach 2: Stack (Better)

Explanation: Traverse array from end, use stack to keep track of next greater elements.

Time Complexity: O(n)

Space Complexity: O(n)

stack = empty
result = [-1]*n
for i in n-1..0:
    while stack not empty and stack.top() <= nums[i]:
        stack.pop()
    if stack not empty:
        result[i] = stack.top()
    stack.push(nums[i])
return result

💡 Think: Sweep backward, pop smaller/equal, top becomes the next greater.

Approach 3: Optimized for Circular Array

Explanation: Handle circular arrays by traversing twice using modulo index.

Time Complexity: O(n)

Space Complexity: O(n)

stack = empty
result = [-1]*n
for i in 2*n-1..0:
    index = i % n
    while stack not empty and stack.top() <= nums[index]:
        stack.pop()
    if stack not empty:
        result[index] = stack.top()
    stack.push(nums[index])
return result

💡 Think: Traverse twice with indices mod n to handle wraparound cases.

Solve on LeetCode