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.