Next Greater Element Using Stack in DSA Rust - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Iterate over array from right to left

↓

While stack not empty and top <= current element

↓

Pop stack top

↓

If stack empty -> No greater element, assign -1

↓

Else top of stack is next greater element

↓

Push current element onto stack

↓

Move to next element left

↓

Repeat until all elements processed

↓

Result array with next greater elements ready

We scan the array from right to left, using a stack to keep track of candidates for the next greater element. For each element, we pop smaller or equal elements from the stack until we find a greater one or the stack is empty.

Execution Sample

DSA Rust

let arr = [4, 5, 2, 25];
let mut stack = Vec::new();
let mut result = vec![-1; arr.len()];
for i in (0..arr.len()).rev() {
    while let Some(&top) = stack.last() {
        if top <= arr[i] { stack.pop(); } else { break; }
    }
    result[i] = *stack.last().unwrap_or(&-1);
    stack.push(arr[i]);
}
println!("{:?}", result);

This code finds the next greater element for each item in the array [4,5,2,25] using a stack scanning from right to left.

Execution Table

Step	Operation	Current Index i	Current Element	Stack Before	Stack After	Result Array	Visual State
1	Start	-	-	[]	[]	[-1, -1, -1, -1]	Stack empty, result initialized with -1
2	Process element	3	25	[]	[25]	[-1, -1, -1, -1]	No greater element to right, result[3] = -1
3	Process element	2	2	[25]	[25, 2]	[-1, -1, 25, -1]	Top 25 > 2, result[2] = 25
4	Process element	1	5	[25, 2]	[25, 5]	[-1, 25, 25, -1]	Pop 2 (<=5), top 25 > 5, result[1] = 25
5	Process element	0	4	[25, 5]	[25, 5, 4]	[5, 25, 25, -1]	Top 5 > 4, result[0] = 5
6	End	-	-	[25, 5, 4]	[25, 5, 4]	[5, 25, 25, -1]	All elements processed, final result ready

💡 All elements processed from right to left, stack used to find next greater elements, result array completed.

Variable Tracker

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

Key Moments - 3 Insights

Why do we scan the array from right to left instead of left to right?

Because we want to find the next greater element to the right of each element. Scanning from right to left allows us to use the stack to keep track of candidates efficiently, as shown in execution_table rows 2 to 5.

Why do we pop elements from the stack while they are less than or equal to the current element?

Because those elements cannot be the next greater element for the current or any earlier elements. This is shown in step 4 where 2 is popped before pushing 5.

What does it mean when the stack is empty during processing?

It means there is no greater element to the right, so we assign -1 in the result array, as seen in step 2 for element 25.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What happens to the stack before pushing the current element 5?

A The entire stack is cleared.

B The stack remains unchanged.

C The top element 2 is popped from the stack.

D The current element 5 is popped from the stack.

💡 Hint

Check the 'Stack Before' and 'Stack After' columns at step 4 in execution_table.

At which step does the result array first get a value other than -1 assigned?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Result Array' column in execution_table rows to see when values change from -1.

If the input array was [2, 2, 2], what would the result array look like after processing?

A [2, 2, -1]

B [-1, -1, -1]

C [-1, 2, -1]

D [2, -1, -1]

💡 Hint

Consider that no element has a strictly greater element to its right, so result entries remain -1.

Concept Snapshot

Next Greater Element Using Stack:
- Scan array from right to left
- Use stack to track next greater candidates
- Pop smaller or equal elements from stack
- If stack empty, assign -1
- Else top of stack is next greater element
- Push current element onto stack
- Result array stores next greater elements

Full Transcript

This concept shows how to find the next greater element for each item in an array using a stack. We start scanning from the right end of the array. For each element, we remove smaller or equal elements from the stack because they cannot be the next greater element. If the stack is empty, it means no greater element exists to the right, so we assign -1. Otherwise, the top of the stack is the next greater element. Then we push the current element onto the stack and move left. This process continues until all elements are processed. The final result array contains the next greater elements or -1 if none exists. The execution table and variable tracker show each step and how the stack and result array change. Key moments clarify why we scan right to left and why we pop elements from the stack. The visual quiz tests understanding of stack changes and result assignments.

Practice

1. What is the main purpose of using a stack in the Next Greater Element problem?

easy

A. To keep track of elements for which we haven't found the next greater element yet

B. To sort the array elements in ascending order

C. To store the final output of next greater elements

D. To reverse the array elements before processing

Solution

1. Step 1: Understand the role of stack in the problem

   The stack stores elements that are waiting to find their next greater element as we scan the array.

2. Step 2: Clarify what the stack does not do

   The stack does not sort or store final output; it only helps track elements pending next greater element discovery.

3. Final Answer:

   To keep track of elements for which we haven't found the next greater element yet -> Option A

4. Quick Check:

   Stack tracks pending elements = A [OK]

Hint: Stack holds candidates waiting for next greater element [OK]

Common Mistakes:

• Thinking stack sorts the array
• Confusing stack with output storage
• Assuming stack reverses the array

2. Which of the following Rust code snippets correctly initializes an empty stack to use for Next Greater Element?

easy

A. let mut stack = Vec::empty();

B. let mut stack: Vec<i32> = Vec::new();

C. let stack = new Vec<i32>();

D. let stack = Vec<i32>;

Solution

1. Step 1: Identify correct Rust syntax for empty vector

   In Rust, an empty vector is created with Vec::new() and mutable if we want to push elements.

2. Step 2: Check each option

   let mut stack: Vec<i32> = Vec::new(); uses correct syntax with mut and Vec::new(). Options A, B, and C are invalid Rust syntax.

3. Final Answer:

   let mut stack: Vec<i32> = Vec::new(); -> Option B

4. Quick Check:

   Vec::new() with mut = D [OK]

Hint: Use let mut stack: Vec<i32> = Vec::new(); to create empty stack [OK]

Common Mistakes:

• Omitting mut when pushing elements
• Using incorrect Vec initialization syntax
• Confusing Vec::new() with other methods

3. What is the output of the following Rust code for Next Greater Element?

let nums = vec![4, 5, 2, 25];
let mut stack: Vec<usize> = Vec::new();
let mut result = vec![-1; nums.len()];

for i in 0..nums.len() {
    while !stack.is_empty() && nums[*stack.last().unwrap()] < nums[i] {
        let idx = stack.pop().unwrap();
        result[idx] = nums[i];
    }
    stack.push(i);
}

println!("{:?}", result);

medium

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

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

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

D. [5, 2, 25, -1]

Solution

1. Step 1: Trace the loop and stack operations

   Start with empty stack and result [-1, -1, -1, -1]. - i=0: stack empty, push 0 (stack=[0]) - i=1: nums[0]=4 < nums[1]=5, pop 0, result[0]=5, push 1 (stack=[1]) - i=2: nums[1]=5 > nums[2]=2, push 2 (stack=[1,2]) - i=3: nums[2]=2 < nums[3]=25, pop 2, result[2]=25 nums[1]=5 < 25, pop 1, result[1]=25, push 3 (stack=[3])

2. Step 2: Finalize result array

   Stack has index 3 left, result[3] remains -1. Final result is [5, 25, 25, -1].

3. Final Answer:

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

4. Quick Check:

   Next greater elements = [5, 25, 25, -1] [OK]

Hint: Pop smaller indices until current is smaller, assign next greater [OK]

Common Mistakes:

• Not updating result when popping from stack
• Pushing indices instead of values
• Confusing indices and values in comparisons

4. Identify the bug in this Rust code snippet for Next Greater Element and select the fix:

let nums = vec![2, 7, 3, 5, 4, 6, 8];
let mut stack: Vec<i32> = Vec::new();
let mut result = vec![-1; nums.len()];

for i in 0..nums.len() {
    while !stack.is_empty() && nums[stack.last().unwrap()] < nums[i] {
        let idx = stack.pop().unwrap();
        result[idx] = nums[i];
    }
    stack.push(i as i32);
}

println!("{:?}", result);

medium

A. Change stack type to Vec<usize> and remove i32 casts

B. Change result vector to Vec<i32> with zeros instead of -1

C. Replace while loop with if statement

D. Push nums[i] instead of index i into stack

Solution

1. Step 1: Identify type mismatch in stack usage

   The stack stores indices to access nums. Indices are usize, but stack is Vec<i32> and i is cast to i32. This causes type mismatch and indexing errors.

2. Step 2: Fix by using correct type for stack

   Change stack to Vec<usize> and push i directly without casting. This matches indexing type and avoids errors.

3. Final Answer:

   Change stack type to Vec<usize> and remove i32 casts -> Option A

4. Quick Check:

   Stack indices must be usize = A [OK]

Hint: Use usize for indices in stack to match array indexing [OK]

Common Mistakes:

• Using i32 for indices causing type errors
• Pushing values instead of indices
• Replacing while with if losing multiple pops

5. Given the array [13, 7, 6, 12], apply the Next Greater Element using stack approach and provide the final output array.

hard

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

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

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

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

Solution

1. Step 1: Initialize stack and result

   Start with empty stack and result = [-1, -1, -1, -1]. Process elements left to right.

2. Step 2: Process each element and update result

   - i=0 (13): stack empty, push 0 (stack=[0]) - i=1 (7): 13 > 7, push 1 (stack=[0,1]) - i=2 (6): 7 > 6, push 2 (stack=[0,1,2]) - i=3 (12): 6 < 12, pop 2, result[2]=12 7 < 12, pop 1, result[1]=12 13 > 12, push 3 (stack=[0,3])

3. Step 3: Finalize result

   Stack has indices 0 and 3 left, their result remains -1. Final result: [-1, 12, 12, -1]

4. Final Answer:

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

5. Quick Check:

   Next greater elements = [-1, 12, 12, -1] [OK]

Hint: Pop smaller elements until current is smaller, assign next greater [OK]

Common Mistakes:

• Assigning wrong next greater for first element
• Not popping all smaller elements before pushing
• Confusing values and indices in stack