Next Greater Element Using Stack in DSA Python

Mental Model

We want to find the next bigger number for each number in a list by looking ahead efficiently using a stack.

Analogy: Imagine standing in a line of people with different heights. For each person, you want to find the next taller person standing to their right without checking everyone one by one.

Array: [4] [5] [2] [25] [7]
Stack: empty
Result: [-1, -1, -1, -1, -1]

Dry Run Walkthrough

Input: list: [4, 5, 2, 25, 7]

Goal: Find the next greater element for each number in the list

Step 1: Push 4 onto stack

Stack: [4]
Result: [-1, -1, -1, -1, -1]

Why: Start with first element, no previous elements to compare

Step 2: 5 is greater than top of stack (4), pop 4 and set result[0] = 5, then push 5

Stack: [5]
Result: [5, -1, -1, -1, -1]

Why: 5 is next greater for 4, update result and keep 5 for next comparisons

Step 3: 2 is not greater than top of stack (5), push 2

Stack: [5, 2]
Result: [5, -1, -1, -1, -1]

Why: 2 has no next greater found yet, keep it for future checks

Step 4: 25 is greater than top of stack (2), pop 2 and set result[2] = 25; 25 is also greater than 5, pop 5 and set result[1] = 25; push 25

Stack: [25]
Result: [5, 25, 25, -1, -1]

Why: 25 is next greater for both 2 and 5, update results accordingly

Step 5: 7 is not greater than top of stack (25), push 7

Stack: [25, 7]
Result: [5, 25, 25, -1, -1]

Why: 7 has no next greater found yet, keep it for future checks

Result:

Result array: [5, 25, 25, -1, -1]

Annotated Code

DSA Python

class NextGreaterElement:
    def next_greater(self, arr):
        n = len(arr)
        result = [-1] * n  # Initialize all with -1
        stack = []  # Stack to keep indexes

        for i in range(n):
            # While current element is greater than element at stack top index
            while stack and arr[i] > arr[stack[-1]]:
                index = stack.pop()  # Pop index
                result[index] = arr[i]  # Update result for popped index
            stack.append(i)  # Push current index

        return result


if __name__ == '__main__':
    arr = [4, 5, 2, 25, 7]
    nge = NextGreaterElement()
    res = nge.next_greater(arr)
    print(res)

while stack and arr[i] > arr[stack[-1]]:

Check if current element is next greater for elements indexed in stack

index = stack.pop()

Remove index from stack to update its next greater element

result[index] = arr[i]

Assign current element as next greater for popped index

stack.append(i)

Add current index to stack to find its next greater later

Output

[5, 25, 25, -1, -1]

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once from the stack

Space: O(n) for the stack and result array to store next greater elements

vs Alternative: Naive approach is O(n^2) by checking every element to the right; stack reduces it to O(n)

Edge Cases

Empty array

Returns empty result list immediately

DSA Python

n = len(arr)

All elements in descending order

All elements have no next greater, result remains all -1

DSA Python

while stack and arr[i] > arr[stack[-1]]:

All elements equal

No next greater element for any, result all -1

DSA Python

while stack and arr[i] > arr[stack[-1]]:

When to Use This Pattern

When you need to find the next bigger element for each item in a list efficiently, use the stack pattern to track candidates and update results in one pass.

Common Mistakes

Mistake: Comparing values directly without using indexes, losing track of positions
Fix: Store indexes in stack to update result array correctly

Mistake: Not popping all smaller elements from stack when a bigger element is found
Fix: Use a while loop to pop all smaller elements before pushing current

Summary

Finds the next greater element for each item in a list using a stack.

Use when you want to efficiently find the next bigger number to the right for each element.

The key insight is to keep indexes of elements in a stack and pop them when a bigger element appears.