Next Greater Element II (Circular Array)

▶

Steps

setup

Initialize variables

Determine the length of the input array, create a doubled array by concatenating the input with itself, initialize the answer array with -1s, and create an empty stack.

💡 This setup prepares the data structures needed to handle the circular nature of the problem and store results.

Line:

n = len(nums)
doubled = nums + nums
answer = [-1] * n
stack = []

💡 The doubled array allows us to simulate circular traversal without complex modular arithmetic.

traverse

Start iteration at index 0

Begin iterating over the doubled array at index 0, current element is 1. The stack is empty, so no popping occurs. Since index 0 is within the original array length, push it onto the stack.

💡 Pushing index 0 means we are waiting to find the next greater element for nums[0].

Line:

for i, num in enumerate(doubled):
    if i < n:
        stack.append(i)

💡 Stack now tracks index 0, representing element 1 waiting for a next greater element.

traverse

Iterate at index 1, element 2

At index 1, current element is 2. Compare it with the element at the top of the stack (index 0, value 1). Since 2 > 1, pop index 0 from the stack and update answer[0] to 2. Then, because index 1 < n, push 1 onto the stack.

💡 Popping index 0 means we found the next greater element for nums[0]. Pushing index 1 means we now wait for nums[1]'s next greater element.

Line:

while stack and doubled[stack[-1]] < num:
    idx = stack.pop()
    if idx < n:
        answer[idx] = num
if i < n:
    stack.append(i)

💡 The stack maintains indices of elements still waiting for their next greater element, and answer updates happen immediately upon popping.

traverse

Iterate at index 2, element 1

At index 2, current element is 1. The top of the stack is index 1 with value 2. Since 1 is not greater than 2, no popping occurs. Because index 2 < n, push 2 onto the stack.

💡 Pushing index 2 means we are now waiting for the next greater element for nums[2].

Line:

while stack and doubled[stack[-1]] < num:
    ...
if i < n:
    stack.append(i)

💡 Stack now holds indices [1, 2], representing elements 2 and 1 waiting for their next greater elements.

traverse

Iterate at index 3 (wrap-around), element 1

At index 3, current element is 1 (wrap-around). The top of the stack is index 2 with value 1. Since 1 is not greater than 1, no popping occurs. Index 3 is not less than n, so do not push it onto the stack.

💡 We only push indices from the original array, so indices beyond n are used only for popping comparisons.

Line:

while stack and doubled[stack[-1]] < num:
    ...
if i < n:
    stack.append(i)

💡 This step shows how the doubled array is used to find next greater elements for indices waiting in the stack without adding new indices.

traverse

Iterate at index 4 (wrap-around), element 2

At index 4, current element is 2. The top of the stack is index 2 with value 1. Since 2 > 1, pop index 2 and update answer[2] to 2. Next, the new top is index 1 with value 2. Since 2 is not greater than 2, stop popping. Index 4 is not less than n, so do not push it.

💡 Popping index 2 means we found the next greater element for nums[2].

Line:

while stack and doubled[stack[-1]] < num:
    idx = stack.pop()
    if idx < n:
        answer[idx] = num
if i < n:
    stack.append(i)

💡 This step shows how multiple pops can happen in one iteration to update answers for multiple indices.

traverse

Iterate at index 5 (wrap-around), element 1

At index 5, current element is 1. The top of the stack is index 1 with value 2. Since 1 is not greater than 2, no popping occurs. Index 5 is not less than n, so do not push it.

💡 No changes to stack or answer because current element does not exceed top stack element.

Line:

while stack and doubled[stack[-1]] < num:
    ...
if i < n:
    stack.append(i)

💡 This step confirms that only strictly greater elements cause popping and answer updates.

reconstruct

End of iteration, stack contains indices with no next greater element

Iteration over the doubled array is complete. The stack still contains index 1, which corresponds to element 2. Since no next greater element was found for it, answer[1] remains -1.

💡 Elements left in the stack have no next greater element in the circular array.

Line:

return answer

💡 The algorithm correctly leaves -1 for elements without a next greater element.

reconstruct

Final answer array

The final answer array is [2, -1, 2], representing the next greater elements for each index in the original array.

💡 This array is the output of the algorithm, showing the next greater element or -1 if none exists.

Line:

return answer

💡 The algorithm successfully computed the next greater elements for the circular array.

reconstruct

Final stack and answer summary

The algorithm ends with the stack containing index 1 and the final answer array [2, -1, 2]. This confirms the correctness and completeness of the solution.

💡 This final step summarizes the state of the stack and the answer array after all iterations.

Line:

return answer

💡 The stack contains indices with no next greater element, and the answer array reflects all computed next greater elements.

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)  # STEP 1
    doubled = nums + nums  # STEP 1
    answer = [-1] * n  # STEP 1
    stack = []  # STEP 1
    for i, num in enumerate(doubled):  # STEP 2 to 8
        while stack and doubled[stack[-1]] < num:  # STEP 3,6
            idx = stack.pop()  # STEP 3,6
            if idx < n:  # STEP 3,6
                answer[idx] = num  # STEP 3,6
        if i < n:  # STEP 2,3,4
            stack.append(i)  # STEP 2,3,4
    return answer  # STEP 9

if __name__ == '__main__':
    print(nextGreaterElements([1,2,1]))  # Output: [2, -1, 2]

📊

Next Greater Element II (Circular Array) - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation on the stack reveals how the algorithm efficiently finds next greater elements without redundant comparisons.

no_op

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

0

↑ pushed: 0

pop_pushElement[1]: 2

Stack (top→bottom)

1

↓ popped: [0]

Contributes: {"index":0,"value":2}

pushElement[2]: 1

Stack (top→bottom)

2

1

↑ pushed: 2

no_opElement[3]: 1

Stack (top→bottom)

2

1

popElement[4]: 2

Stack (top→bottom)

1

↓ popped: [2]

Contributes: {"index":2,"value":2}

no_opElement[5]: 1

Stack (top→bottom)

1

no_op

Stack (top→bottom)

1

no_op

Stack (top→bottom)

1

Contributes: [2,-1,2]

no_op

Stack (top→bottom)

1

Contributes: [2,-1,2]

Key Takeaways

✓ The monotonic stack efficiently tracks indices waiting for their next greater element, enabling O(n) time complexity.

This insight is hard to see from code alone because the stack operations and their effect on answer updates happen implicitly.

✓ Doubling the array simulates the circular nature, allowing a linear scan instead of complex modular arithmetic.

Visualizing the doubled array clarifies how wrap-around comparisons are handled seamlessly.

✓ Only indices from the original array are pushed onto the stack, while the doubled part is used solely for comparisons and popping.

This distinction is subtle in code but critical for correctness and efficiency.

Practice

1. Given the following Python code for the Basic Calculator, what is the value of result immediately after processing the character ')' at index 6 in the input string "(1+(2-3))"?

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Add last number and combine
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
    result += sign * num
    return result

easy

A. 0

B. 0

C. 0

D. 0

Solution

1. Step 1: Trace characters up to index 6

   Input: "(1+(2-3))" - i=0:'(' push 0 and 1, result=0, sign=1 - i=1:'1' num=1 - i=2:'+' result=0+1*1=1, num=0, sign=1 - i=3:'(' push 1 and 1, result=0, sign=1 - i=4:'2' num=2 - i=5:'-' result=0+1*2=2, num=0, sign=-1 - i=6:'3' num=3

2. Step 2: Process character at index 6 (')')

   At ')': result += sign*num = 2 + (-1)*3 = -1 num=0 result *= stack.pop() -> result *= 1 -> -1 result += stack.pop() -> -1 + 1 = 0

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Result after popping stack is 0 [OK]

Hint: Remember to apply sign*num before popping stack [OK]

Common Mistakes:

• Forgetting to add last number before popping stack

2. You need to implement a data structure that supports enqueue and dequeue operations using only stack operations (push and pop). Which approach guarantees an amortized O(1) time complexity per operation?

easy

A. Use two stacks: push elements onto one stack, and pop elements from the other stack, transferring elements only when the pop stack is empty.

B. Use a single stack and recursion to simulate dequeue by popping all elements and restoring them after retrieving the front.

C. Use two stacks and transfer elements from push stack to pop stack on every push operation to keep pop stack always ready.

D. Use a queue internally and simulate stacks by reversing the order on every operation.

Solution

1. Step 1: Understand the problem constraints

   The goal is to implement a queue using stacks with efficient enqueue and dequeue operations.

2. Step 2: Analyze approaches for efficiency

   Approach A uses two stacks and transfers elements only when the pop stack is empty, achieving amortized O(1) per operation. Approach B uses recursion and is O(n) per pop. Approach C transfers on every push, causing O(n) per push. Approach D is unrelated and inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two stacks with lazy transfer -> amortized O(1) [OK]

Hint: Two stacks with lazy transfer gives amortized O(1) [OK]

Common Mistakes:

• Thinking transferring on every push is optimal
• Using recursion causing O(n) pop

3. You are given an array representing the heights of adjacent bars in a histogram. Your task is to find the largest rectangular area that can be formed within the bounds of the histogram bars. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Greedy approach expanding from each bar until a smaller bar is found

B. Dynamic programming with memoization over all sub-intervals

C. Monotonic stack to find the nearest smaller bars on left and right boundaries

D. Sorting bars by height and using binary search to find boundaries

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the largest rectangle in a histogram efficiently, which involves quickly determining boundaries for each bar.

2. Step 2: Identify the approach that finds boundaries in O(n)

   Monotonic stack efficiently finds nearest smaller bars on both sides in linear time, enabling calculation of max area.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is well-known for O(n) solution [OK]

Hint: Monotonic stack finds boundaries in linear time [OK]

Common Mistakes:

• Assuming greedy expansion is always optimal
• Thinking DP over all intervals is efficient here

4. You are given a binary matrix and need to find the largest rectangle containing only 1s. Which approach guarantees an optimal solution with O(rows * cols) time complexity?

easy

A. Use dynamic programming to store the largest rectangle ending at each cell without histogram transformation.

B. Use brute force to check all possible rectangles in the matrix.

C. Transform each row into a histogram of heights and apply a monotonic stack to find the largest rectangle in each histogram.

D. Apply a greedy approach by expanding rectangles from each cell until a zero is encountered.

Solution

1. Step 1: Understand the problem transformation

   The problem can be transformed row-wise into histograms where each element represents the height of consecutive 1s above it.

2. Step 2: Recognize the monotonic stack pattern

   For each histogram, the largest rectangle can be found efficiently using a monotonic stack that tracks indices of increasing heights.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Histogram + monotonic stack approach is standard for maximal rectangle [OK]

Hint: Transform rows to histograms and use monotonic stack [OK]

Common Mistakes:

• Trying brute force leads to O(n^4) time
• Greedy expansion fails on complex shapes
• DP without histogram misses efficient stack usage

5. What is the time complexity of the optimal stack-based solution for evaluating a basic calculator expression with parentheses and plus/minus operators, where n is the length of the input string?

medium

A. O(n log n) due to sorting tokens before evaluation

B. O(n) because each character is processed once with constant-time stack operations

C. O(n) but with O(n) auxiliary space for the stack to handle nested parentheses

D. O(n^2) due to nested parentheses requiring repeated rescanning

Solution

1. Step 1: Identify time complexity

   The algorithm processes each character once, so time complexity is O(n).

2. Step 2: Identify space complexity

   Stack stores intermediate results for each open parenthesis, worst case O(n) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time with linear auxiliary space for stack [OK]

Hint: Stack space grows with nesting depth, time linear [OK]

Common Mistakes:

• Assuming O(n^2) due to nested parentheses