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.

Practice

1. What does the Next Greater Element problem using a stack help you find for each element in an array?

easy

A. The first smaller element to the left of each element

B. The first greater element to the right of each element

C. The sum of all elements greater than the current element

D. The index of the largest element in the array

Solution

1. Step 1: Understand the problem goal

   The Next Greater Element problem asks to find, for each element, the first element to its right that is greater than it.

2. Step 2: Recognize the stack usage

   A stack helps efficiently track elements waiting for their next greater element to appear on the right.

3. Final Answer:

   The first greater element to the right of each element -> Option B

4. Quick Check:

   Next Greater Element = first bigger right element [OK]

Hint: Look right for first bigger number using stack [OK]

Common Mistakes:

• Confusing next greater with next smaller element
• Looking to the left instead of right
• Thinking it finds the largest element overall

2. Which of the following is the correct way to initialize an empty stack in Python for solving Next Greater Element?

easy

A. stack = []

B. stack = {}

C. stack = ()

D. stack = None

Solution

1. Step 1: Identify stack data structure in Python

   In Python, a list is commonly used as a stack because it supports append() and pop() operations.

2. Step 2: Check initialization syntax

   An empty list is created with square brackets []. Curly braces {} create a dictionary, parentheses () create a tuple, and None is a null value.

3. Final Answer:

   stack = [] -> Option A

4. Quick Check:

   Empty stack = empty list [] [OK]

Hint: Use list [] for stack in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Using () which creates a tuple
• Assigning None instead of a list

3. What is the output of the Next Greater Element for the array [4, 5, 2, 25]?

medium

A. [25, 25, -1, -1]

B. [5, -1, 25, -1]

C. [5, 25, 25, -1]

D. [-1, -1, -1, -1]

Solution

1. Step 1: Find next greater for each element

   For 4, next greater is 5; for 5, next greater is 25; for 2, next greater is 25; for 25, no greater element, so -1.

2. Step 2: Write the output array

   The output array is [5, 25, 25, -1].

3. Final Answer:

   [5, 25, 25, -1] -> Option C

4. Quick Check:

   Check each element's next bigger right = output [OK]

Hint: Scan right for bigger number or -1 if none [OK]

Common Mistakes:

• Putting -1 too early for elements that have bigger right
• Confusing order of output elements
• Missing last element's -1

4. Given the code snippet below, what is the error?

def next_greater(arr):
    stack = []
    result = [-1] * len(arr)
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

print(next_greater([2, 7, 3, 5, 4, 6, 8]))

medium

A. No error, code runs correctly

B. IndexError due to wrong stack usage

C. SyntaxError because of missing colon

D. TypeError due to wrong list initialization

Solution

1. Step 1: Analyze the code logic

   The code uses a stack to store indices and updates the result list with next greater elements correctly.

2. Step 2: Check for syntax and runtime errors

   All syntax is correct, stack usage is proper, and list initialization is valid.

3. Final Answer:

   No error, code runs correctly -> Option A

4. Quick Check:

   Stack and result used correctly, no errors [OK]

Hint: Trace stack push/pop carefully to spot errors [OK]

Common Mistakes:

• Assuming index errors without checking stack conditions
• Confusing syntax errors with logic errors
• Misreading list initialization syntax

5. You have an array [13, 7, 6, 12]. Using the Next Greater Element approach with a stack, what will be the final output array?

hard

A. [7, 12, 12, -1]

B. [13, 12, 12, -1]

C. [-1, -1, 12, -1]

D. [-1, 12, 12, -1]

Solution

1. Step 1: Find next greater element for each index

   For 13, no greater element to right, so -1; for 7, next greater is 12; for 6, next greater is 12; for 12, no greater element, so -1.

2. Step 2: Write the output array

   The output is [-1, 12, 12, -1].

3. Final Answer:

   [-1, 12, 12, -1] -> Option D

4. Quick Check:

   Check each element's next bigger right = output [OK]

Hint: Remember last element always -1 if no bigger right [OK]

Common Mistakes:

• Assuming first element has a bigger next element incorrectly
• Mixing values with indices in output
• Forgetting to put -1 when no greater element exists