Next Greater Element Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Greater Element for a given array

What is the output of the following Go code that finds the next greater element for each element in the array?

DSA Go

package main
import "fmt"
func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }
    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = nums[i]
        }
        stack = append(stack, i)
    }
    return res
}
func main() {
    arr := []int{4, 5, 2, 25}
    result := nextGreaterElements(arr)
    fmt.Println(result)
}

A [25 25 25 -1]

B [5 25 -1 -1]

C [5 25 25 -1]

D [5 2 25 -1]

💡 Hint

Think about how the stack helps track indices waiting for a greater element.

The code uses a stack to keep indices of elements for which the next greater element is not found yet. When a bigger element is found, it updates the result for those indices. For the input [4, 5, 2, 25], the next greater elements are [5, 25, 25, -1].

🧠 Conceptual

intermediate

Understanding the role of stack in Next Greater Element

Why is a stack used in the Next Greater Element algorithm instead of a simple nested loop?

A Because stack stores all elements in sorted order to find next greater element quickly.

B Because stack duplicates the array elements to compare them twice.

C Because stack reverses the array to find next greater elements from the end.

D Because stack helps keep track of indices whose next greater element is not found yet, allowing O(n) time complexity.

💡 Hint

Think about how the algorithm avoids checking every pair of elements.

The stack stores indices of elements waiting for their next greater element. When a bigger element comes, it pops from the stack and updates results. This avoids nested loops and achieves O(n) time.

❓ Predict Output

advanced

Output of Next Greater Element for circular array

What is the output of this Go code that finds the next greater element for each element in a circular array?

DSA Go

package main
import "fmt"
func nextGreaterElementsCircular(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }
    stack := []int{}
    for i := 0; i < 2*n; i++ {
        for len(stack) > 0 && nums[i%n] > nums[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = nums[i%n]
        }
        if i < n {
            stack = append(stack, i)
        }
    }
    return res
}
func main() {
    arr := []int{1, 2, 1}
    result := nextGreaterElementsCircular(arr)
    fmt.Println(result)
}

A [2 -1 2]

B [2 1 -1]

C [-1 2 -1]

D [2 2 2]

💡 Hint

Remember the array is circular, so elements after the end wrap around to the start.

The code simulates a circular array by iterating twice the length. For input [1, 2, 1], the next greater elements are [2, -1, 2].

🔧 Debug

advanced

Identify the error in Next Greater Element code

What error will this Go code produce when finding next greater elements?

DSA Go

package main
import "fmt"
func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = nums[i]
        }
        stack = append(stack, i)
    }
    return res
}
func main() {
    arr := []int{2, 1, 3}
    result := nextGreaterElements(arr)
    fmt.Println(result)
}

A Compilation error due to missing return statement

B Index out of range runtime error

C Output: [3 3 -1]

D Output: [-1 -1 -1]

💡 Hint

Check the stack index usage inside the inner loop condition.

The code uses stack[len(stack)] which is out of range because valid indices go up to len(stack)-1. This causes a runtime panic: index out of range.

🚀 Application

expert

Number of elements with no next greater element

Given the array [13, 7, 6, 12], how many elements have no next greater element using the Next Greater Element algorithm?

A 2

B 1

C 3

D 0

💡 Hint

Find the next greater element for each and count how many are -1.

For [13, 7, 6, 12], next greater elements are [-1, 12, 12, -1]. Two elements (13 and 12) have no next greater element.

Practice

1. What does the Next Greater Element (NGE) problem using a stack find for each element in an array?

easy

A. The first greater element to the right of each element

B. The first smaller element to the left of each element

C. The sum of all elements greater than the current element

D. The last 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 track elements for which we haven't found a greater element yet, efficiently finding the next greater element to the right.

3. Final Answer:

   The first greater element to the right of each element -> Option A

4. Quick Check:

   NGE = first greater element on right [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 sums elements instead of finding one

2. Which Go code snippet correctly initializes an empty stack to use for Next Greater Element logic?

easy

A. stack := 0

B. stack := make(map[int]int)

C. stack := new(int)

D. stack := []int{}

Solution

1. Step 1: Identify stack data structure in Go

   Stacks can be implemented using slices in Go. An empty stack is an empty slice of ints: []int{}.

2. Step 2: Check other options

   stack := make(map[int]int) is a map, not a stack. stack := new(int) is a pointer to int, not a stack. stack := 0 is an int variable, not a stack.

3. Final Answer:

   stack := []int{} -> Option D

4. Quick Check:

   Stack as slice = []int{} [OK]

Hint: Use empty int slice for stack in Go [OK]

Common Mistakes:

• Using map instead of slice for stack
• Using pointer instead of slice
• Initializing stack as int variable

3. What is the output of the Next Greater Element function for the input array [4, 5, 2, 25]?

medium

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

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

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

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

Solution

1. Step 1: Trace the array elements with stack

   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: Form the output array

   Output is [5, 25, 25, -1].

3. Final Answer:

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

4. Quick Check:

   Next greater elements found correctly [OK]

Hint: Check each element's right side for bigger number [OK]

Common Mistakes:

• Assigning -1 too early
• Mixing up indices in output
• Ignoring last element's -1

4. Given the following Go code snippet for Next Greater Element, what is the bug?

func nextGreater(arr []int) []int {
  stack := []int{}
  result := make([]int, len(arr))
  for i := len(arr) - 1; i >= 0; i-- {
    for len(stack) > 0 && stack[len(stack)-1] <= arr[i] {
      stack = stack[:len(stack)-1]
    }
    if len(stack) == 0 {
      result[i] = 0
    } else {
      result[i] = stack[len(stack)-1]
    }
    stack = append(stack, arr[i])
  }
  return result
}

medium

A. Stack is not initialized properly

B. Loop iterates in wrong direction

C. Result uses 0 instead of -1 for no greater element

D. Comparison operator should be >= instead of <=

Solution

1. Step 1: Identify the no greater element marker

   The code assigns 0 when no greater element is found, but the standard is to use -1.

2. Step 2: Check other parts

   Stack initialization and loop direction are correct. Comparison operator <= is correct for popping smaller or equal elements.

3. Final Answer:

   Result uses 0 instead of -1 for no greater element -> Option C

4. Quick Check:

   No greater element should be -1 [OK]

Hint: Use -1 for no next greater element, not 0 [OK]

Common Mistakes:

• Returning 0 instead of -1 for no greater element
• Changing loop direction incorrectly
• Wrong comparison operator causing wrong pops

5. You have an array [13, 7, 6, 12]. Using the Next Greater Element stack approach, what is the output array?

hard

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

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

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

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

Solution

1. Step 1: Find next greater for each element

   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 output array

   Output is [-1, 12, 12, -1].

3. Final Answer:

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

4. Quick Check:

   Check right side for bigger numbers [OK]

Hint: Check each element's right side for bigger number [OK]

Common Mistakes:

• Assigning wrong next greater for 7 and 6
• Confusing output with input order
• Using 0 instead of -1 for no greater element