Next Greater Element Using Stack in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Next Greater Element (NGE) for an element in an array?

The Next Greater Element for an element is the first element to the right of it in the array that is larger than it. If no such element exists, the NGE is -1.

intermediate

Why do we use a stack to solve the Next Greater Element problem efficiently?

A stack helps keep track of elements for which we haven't found the NGE yet. It allows us to process elements in one pass by comparing the current element with the top of the stack and popping smaller elements.

intermediate

In the Next Greater Element algorithm using a stack, what happens when the current element is greater than the top of the stack?

We pop elements from the stack while the current element is greater than the top. For each popped element, the current element is its Next Greater Element.

intermediate

What is the time complexity of the Next Greater Element algorithm using a stack?

The time complexity is O(n) because each element is pushed and popped at most once from the stack.

beginner

Show the output of Next Greater Element for the array [4, 5, 2, 25] using the stack method.

The Next Greater Elements are [5, 25, 25, -1]. Explanation: 4's NGE is 5, 5's NGE is 25, 2's NGE is 25, and 25 has no greater element to the right.

What does the stack store in the Next Greater Element algorithm?

A Only the largest element in the array

B Indices or values of elements waiting for their NGE

C All elements in sorted order

D Only the smallest element in the array

The stack stores elements (or their indices) for which we haven't found the Next Greater Element yet.

If the current element is smaller than the top of the stack, what should you do?

A Ignore the current element

B Pop the top element from the stack

C Replace the top element with the current element

D Push the current element onto the stack

Since the current element is smaller than the top, it cannot be the NGE for the top element, so we push it onto the stack.

What value is assigned if no Next Greater Element exists for an element?

A -1

B 0

C The element itself

D Infinity

We assign -1 to indicate no greater element exists to the right.

What is the main advantage of using a stack for the Next Greater Element problem?

A It sorts the array automatically

B It uses less memory than arrays

C It reduces time complexity to O(n)

D It finds the smallest element quickly

Using a stack allows us to find Next Greater Elements in a single pass, making the algorithm O(n).

For the array [13, 7, 6, 12], what is the Next Greater Element for 7?

A 12

B 13

C -1

D 6

7's Next Greater Element is 12, the first greater element to its right.

Explain how the stack helps find the Next Greater Element for each item in an array.

Think about how you keep track of elements that still need their next bigger number.

Describe the step-by-step process of finding Next Greater Elements for the array [2, 1, 3].

Walk through the array left to right, using the stack to track waiting elements.

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