Next Greater Element Using Stack in DSA Python - 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 code that finds the next greater element for each element in the array using a stack?

DSA Python

def next_greater_element(arr):
    stack = []
    result = [-1] * len(arr)
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

print(next_greater_element([4, 5, 2, 25]))

A [5, 25, 25, -1]

B [-1, -1, -1, -1]

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

D [5, 2, 25, -1]

💡 Hint

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

The stack stores indices of elements for which we haven't found a greater element yet. When a greater element is found, it updates the result for those indices.

🧠 Conceptual

intermediate

Understanding stack usage in Next Greater Element

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

A Because stack duplicates the array elements to compare each with every other element.

B Because stack sorts the array automatically to find the next greater element.

C Because stack stores all elements in sorted order to find the maximum element.

D Because stack helps keep track of elements for which we haven't found the next greater element yet, allowing O(n) time complexity.

💡 Hint

Think about how the stack helps avoid repeated comparisons.

Stack stores indices of elements waiting for their next greater element. When a greater element appears, it updates all smaller elements on the stack efficiently.

🔧 Debug

advanced

Identify the error in Next Greater Element code

What error does the following code produce when run, and why? ```python def next_greater_element(arr): stack = [] result = [-1] * len(arr) for i in range(len(arr)): while stack and arr[i] > arr[stack[-1]]: result[stack.pop()] = arr[i] stack.append(i) return result print(next_greater_element([13, 7, 6, 12])) ```

DSA Python

def next_greater_element(arr):
    stack = []
    result = [-1] * len(arr)
    for i in range(len(arr)):
        while stack and arr[i] > arr[stack[-1]]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

print(next_greater_element([13, 7, 6, 12]))

A Raises IndexError due to popping from empty stack

B Output: [ -1, 12, 12, -1 ]

C Output: [ 7, 6, 12, -1 ]

D Output: [ 12, -1, -1, -1 ]

💡 Hint

Trace the stack and result updates carefully for each element.

The code correctly finds the next greater element for each index: - 13 has no greater element after it, so -1 - 7's next greater is 12 - 6's next greater is 12 - 12 has no greater element after it, so -1

❓ Predict Output

advanced

Output of Next Greater Element for circular array

What is the output of the following code that finds the next greater element in a circular array using a stack?

DSA Python

def next_greater_circular(arr):
    n = len(arr)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        while stack and arr[stack[-1]] < arr[i % n]:
            result[stack.pop()] = arr[i % n]
        if i < n:
            stack.append(i)
    return result

print(next_greater_circular([1, 2, 1]))

A [1, 2, 1]

B [-1, -1, -1]

C [2, -1, 2]

D [2, 1, 2]

💡 Hint

Remember the array is treated as circular, so elements after the end wrap around.

For circular arrays, we simulate two passes. For [1,2,1]: - Next greater for 1 is 2 - Next greater for 2 is none (-1) - Next greater for last 1 is 2

🚀 Application

expert

Number of elements with no next greater element

Given the array [11, 13, 21, 3], how many elements have no next greater element to their right?

A 2

B 1

C 3

D 0

💡 Hint

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

Next greater elements are: - 11 -> 13 - 13 -> 21 - 21 -> none (-1) - 3 -> none (-1) So two elements have no next greater element to their right.

Practice

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

easy

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

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

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

D. The index of the largest 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 efficiently track elements waiting for their next greater element to appear on the right.

3. Final Answer:

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

4. Quick Check:

   Next Greater Element = first bigger right element [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 finds the largest element overall

2. Which of the following is the correct way to initialize an empty stack in Python for solving Next Greater Element?

easy

A. stack = []

B. stack = {}

C. stack = ()

D. stack = None

Solution

1. Step 1: Identify stack data structure in Python

   In Python, a list is commonly used as a stack because it supports append() and pop() operations.

2. Step 2: Check initialization syntax

   An empty list is created with square brackets []. Curly braces {} create a dictionary, parentheses () create a tuple, and None is a null value.

3. Final Answer:

   stack = [] -> Option A

4. Quick Check:

   Empty stack = empty list [] [OK]

Hint: Use list [] for stack in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Using () which creates a tuple
• Assigning None instead of a list

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

medium

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

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

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

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

Solution

1. Step 1: Find next greater for each element

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

   The output array is [5, 25, 25, -1].

3. Final Answer:

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

4. Quick Check:

   Check each element's next bigger right = output [OK]

Hint: Scan right for bigger number or -1 if none [OK]

Common Mistakes:

• Putting -1 too early for elements that have bigger right
• Confusing order of output elements
• Missing last element's -1

4. Given the code snippet below, what is the error?

def next_greater(arr):
    stack = []
    result = [-1] * len(arr)
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result

print(next_greater([2, 7, 3, 5, 4, 6, 8]))

medium

A. No error, code runs correctly

B. IndexError due to wrong stack usage

C. SyntaxError because of missing colon

D. TypeError due to wrong list initialization

Solution

1. Step 1: Analyze the code logic

   The code uses a stack to store indices and updates the result list with next greater elements correctly.

2. Step 2: Check for syntax and runtime errors

   All syntax is correct, stack usage is proper, and list initialization is valid.

3. Final Answer:

   No error, code runs correctly -> Option A

4. Quick Check:

   Stack and result used correctly, no errors [OK]

Hint: Trace stack push/pop carefully to spot errors [OK]

Common Mistakes:

• Assuming index errors without checking stack conditions
• Confusing syntax errors with logic errors
• Misreading list initialization syntax

5. You have an array [13, 7, 6, 12]. Using the Next Greater Element approach with a stack, what will be the final output array?

hard

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

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

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

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

Solution

1. Step 1: Find next greater element for each index

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

   The output is [-1, 12, 12, -1].

3. Final Answer:

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

4. Quick Check:

   Check each element's next bigger right = output [OK]

Hint: Remember last element always -1 if no bigger right [OK]

Common Mistakes:

• Assuming first element has a bigger next element incorrectly
• Mixing values with indices in output
• Forgetting to put -1 when no greater element exists