Next Greater Element Using Stack in DSA Python - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Pick next element from array

↓

Is stack empty or top >= current element?

No→Pop from stack and assign current as next greater

↓

Repeat pop while condition holds

↓

Push current element index to stack

↓

Move to next element

↓

Repeat until all elements processed

↓

Assign -1 to remaining stack elements (no next greater)

↓

End

We scan the array from left to right, using a stack to keep indexes of elements waiting for their next greater element. When a bigger element appears, we pop smaller ones and assign their next greater.

Execution Sample

DSA Python

arr = [4, 5, 2, 25]
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)
while stack:
    result[stack.pop()] = -1
print(result)  # [5, 25, 25, -1]

This code finds the next greater element for each item in the array using a stack to track indexes.

Execution Table

Step	Operation	Current Index (i)	Stack (indexes)	Action	Result Array	Visual State
1	Start	-	[]	Initialize empty stack and result array [-1, -1, -1, -1]	[-1, -1, -1, -1]	Stack: [] Result: [-1, -1, -1, -1]
2	Process element	0 (4)	[]	Stack empty, push index 0	[-1, -1, -1, -1]	Stack: [0] Result: [-1, -1, -1, -1]
3	Process element	1 (5)	[0]	arr[0]=4 < 5, pop 0, set result[0]=5; stack empty, push 1	[5, -1, -1, -1]	Stack: [1] Result: [5, -1, -1, -1]
4	Process element	2 (2)	[1]	arr[1]=5 > 2, push 2	[5, -1, -1, -1]	Stack: [1, 2] Result: [5, -1, -1, -1]
5	Process element	3 (25)	[1, 2]	arr[2]=2 < 25, pop 2, set result[2]=25; arr[1]=5 < 25, pop 1, set result[1]=25; stack empty, push 3	[5, 25, 25, -1]	Stack: [3] Result: [5, 25, 25, -1]
6	End	-	[3]	No more elements; pop remaining index 3, set result[3]=-1	[5, 25, 25, -1]	Stack: [] Result: [5, 25, 25, -1]

💡 All elements processed; remaining stack elements have no next greater, assigned -1

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
stack	[]	[0]	[1]	[1, 2]	[3]	[]	[]
result	[-1, -1, -1, -1]	[-1, -1, -1, -1]	[5, -1, -1, -1]	[5, -1, -1, -1]	[5, 25, 25, -1]	[5, 25, 25, -1]	[5, 25, 25, -1]
i	-	0	1	2	3	-	-

Key Moments - 3 Insights

Why do we pop from the stack when the current element is greater than the element at the stack's top?

Because the current element is the next greater element for the popped index. This is shown in steps 3 and 5 where popping happens and result is updated.

Why do we push the current index onto the stack after popping smaller elements?

We push the current index because it might have a next greater element later. This is seen in steps 3, 4, and 5 where after popping, the current index is pushed.

Why do remaining elements in the stack get -1 in the result array at the end?

Because no greater element was found to their right. Step 6 shows assigning -1 to remaining indexes in the stack.

Visual Quiz - 3 Questions

Look at the execution table, what is the content of the stack after processing element at index 2?

A [1, 2]

B [0, 2]

C [2]

D [1]

💡 Hint

Check the 'Stack (indexes)' column at Step 4 in the execution_table.

At which step does the result for index 1 get updated to 25?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Result Array' column in execution_table rows where result changes for index 1.

If the array was [4, 3, 2, 1], what would be the final result array after processing?

A [3, 2, 1, -1]

B [-1, -1, -1, -1]

C [4, 4, 4, -1]

D [5, 5, 5, -1]

💡 Hint

Since no element has a greater element to its right, all remain -1 as per the exit_note.

Concept Snapshot

Next Greater Element Using Stack:
- Use a stack to store indexes of elements waiting for next greater.
- Iterate array left to right.
- While stack top element < current element, pop and assign current as next greater.
- Push current index to stack.
- After iteration, assign -1 to remaining stack indexes.
- Time: O(n), Space: O(n).

Full Transcript

This concept finds the next greater element for each item in an array using a stack. We start with an empty stack and a result array filled with -1. We scan the array from left to right. For each element, we pop from the stack all indexes whose elements are smaller than the current element and assign the current element as their next greater. Then we push the current index onto the stack. After processing all elements, any indexes left in the stack have no next greater element, so their result remains -1. This method efficiently finds next greater elements in one pass.

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