Next Greater Element Using Stack in DSA Rust - Build from Scratch

Next Greater Element Using Stack

📖 Scenario: Imagine you have a list of daily temperatures, and you want to find for each day the next day when the temperature will be higher. This helps you plan your activities better.

🎯 Goal: You will build a program that finds the next greater element for each number in a list using a stack. The next greater element for a number is the first number to the right that is bigger than it. If there is none, we use -1.

📋 What You'll Learn

Create a vector called nums with the exact values [4, 5, 2, 25]

Create a mutable vector called result with the same length as nums filled with -1

Use a stack (vector) called stack to help find the next greater elements

Use a for loop with variable i to iterate over the indices of nums

Inside the loop, use a while loop to compare current number with the top of the stack

Update the result vector with the next greater element where found

Print the result vector at the end

💡 Why This Matters

🌍 Real World

Finding the next greater element is useful in stock price analysis, weather forecasting, and many other areas where you want to know when a bigger value appears next.

💼 Career

Understanding stack-based algorithms is important for technical interviews and for solving real-world problems efficiently in software development.

1

Create the input vector

Create a vector called nums with the exact values [4, 5, 2, 25]

DSA Rust

# Create the vector nums with values [4, 5, 2, 25]
# Your code here

Hint

Use let nums = vec![4, 5, 2, 25]; to create the vector.

2

Prepare the result vector and stack

Create a mutable vector called result with the same length as nums filled with -1. Also create an empty vector called stack to use as a stack.

DSA Rust

fn main() {
    let nums = vec![4, 5, 2, 25];
    // Create result vector filled with -1
    // Create empty stack vector
    # Your code here
}

Hint

Use vec![-1; nums.len()] to create the result vector and Vec::new() for the stack.

3

Find next greater elements using stack

Use a for loop with variable i to iterate over the indices of nums. Inside the loop, use a while loop to compare nums[i] with nums[stack.last().unwrap()]. While nums[i] is greater, pop from stack and update result at that popped index with nums[i]. After the while loop, push i onto stack.

DSA Rust

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

    // Loop over indices i in nums
    // While stack is not empty and nums[i] > nums[stack last element]
    // Pop from stack and update result
    // Push i onto stack
    # Your code here
}

Hint

Use for i in 0..nums.len() and inside it a while loop checking !stack.is_empty() and comparing nums[i] with nums[*stack.last().unwrap()].

4

Print the result vector

Print the result vector using println!("{:?}", result) to show the next greater elements.

DSA Rust

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

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

    // Print the result vector
    # Your code here
}

Hint

Use println!("{:?}", result); to print the vector.

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