Next Greater Element Using Stack in DSA Rust

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 again and again.

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

Dry Run Walkthrough

Input: array: [4, 5, 2, 25, 7, 8]

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

Step 1: Push 4 onto stack

Array: [4, 5, 2, 25, 7, 8]
Stack: [4]
Result: [-1, -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

Array: [4, 5, 2, 25, 7, 8]
Stack: [5]
Result: [5, -1, -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

Array: [4, 5, 2, 25, 7, 8]
Stack: [5, 2]
Result: [5, -1, -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

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

Why: 25 is next greater for 2 and 5, update results and keep 25 for next comparisons

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

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

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

Step 6: 8 is greater than top of stack (7), pop 7 and set result[4] = 8; 8 is not greater than 25, push 8

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

Why: 8 is next greater for 7, update result and keep 8 for next comparisons

Step 7: End of array reached, pop remaining stack elements and set their results to -1

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

Why: No next greater elements for remaining stack items

Result:

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

Annotated Code

DSA Rust

fn next_greater_element(arr: &[i32]) -> Vec<i32> {
    let n = arr.len();
    let mut result = vec![-1; n];
    let mut stack: Vec<usize> = Vec::new();

    for i in 0..n {
        while let Some(&top) = stack.last() {
            if arr[i] > arr[top] {
                result[top] = arr[i];
                stack.pop();
            } else {
                break;
            }
        }
        stack.push(i);
    }

    result
}

fn main() {
    let arr = vec![4, 5, 2, 25, 7, 8];
    let result = next_greater_element(&arr);
    for val in result {
        print!("{} ", val);
    }
    println!();
}

while let Some(&top) = stack.last() {

Check top index of stack to compare with current element

if arr[i] > arr[top] {

If current element is greater, it is next greater for element at top

result[top] = arr[i];

Update result for popped element with next greater

stack.pop();

Remove element from stack after updating result

stack.push(i);

Push current index to stack to find its next greater later

Output

5 25 25 -1 8 -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 without error

DSA Rust

let n = arr.len();

All elements in descending order

All results are -1 because no next greater element exists

DSA Rust

while let Some(&top) = stack.last() { if arr[i] > arr[top] { ... } else { break; } }

All elements equal

All results are -1 because no strictly greater element exists

DSA Rust

if arr[i] > arr[top]

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 keep track of candidates and update results in one pass.

Common Mistakes

Mistake: Pushing values instead of indices onto the stack
Fix: Push indices to access and update the result array correctly

Mistake: Not popping all smaller elements before pushing current element
Fix: Use a while loop to pop all smaller elements to find their next greater

Summary

Finds the next greater element for each item in an array 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 use a stack to remember indices of elements waiting for their next greater element.

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