Next Greater Element II (Circular Array)

📋

Problem

Imagine you have a circular conveyor belt with numbers on packages, and you want to find the next bigger package for each one as the belt keeps rotating endlessly.

Given a circular array nums (the next element of the last element is the first element), return an array answer where answer[i] is the next greater number of nums[i]. If it doesn't exist, set answer[i] to -1.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

Edge cases: Single element array → output [-1]All elements equal → output all -1Strictly decreasing array → all -1 except wrap-around

</>

IDE

def nextGreaterElements(nums: list[int]) -> list[int]:public int[] nextGreaterElements(int[] nums)vector<int> nextGreaterElements(vector<int>& nums)function nextGreaterElements(nums)

def nextGreaterElements(nums: list[int]) -> list[int]:
    # Write your solution here
    pass

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // Write your solution here
        return new int[nums.length];
    }
}

#include <vector>
using namespace std;

vector<int> nextGreaterElements(vector<int>& nums) {
    // Write your solution here
    return vector<int>(nums.size(), -1);
}

function nextGreaterElements(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [2, 2, 2]Incorrectly treating equal elements as next greater instead of strictly greater.✅ Change comparison from nums[curr] >= nums[stack_top] to nums[curr] > nums[stack_top].

Wrong: [2, -1, -1]Missing circular wrap-around logic, so last element's next greater is not found.✅ Iterate over the array twice (2*n) to simulate circular behavior.

Wrong: [2, 3, 4, 5, -1]Greedy approach stops early without checking wrap-around elements.✅ Use monotonic stack with double iteration to find next greater for all elements.

Wrong: Timeout or no outputUsing brute force O(n^2) approach for large inputs.✅ Implement O(n) monotonic stack solution with circular iteration.

✓

Test Cases

Focus on handling small and boundary inputs correctly before moving on.

Review your algorithm for common pitfalls like greedy mistakes and indexing errors.

Optimize your solution to O(n) time complexity using a monotonic stack and circular iteration.

t1_01basic

Input{"nums":[1,2,1]}

Expected[2,-1,2]

⏱ Performance - must finish in 2000ms

For nums[0] = 1, next greater is 2; for nums[1] = 2, no greater element; for nums[2] = 1, next greater is 2 (wraps around).

💡 Think about using a stack to track indices of elements waiting for their next greater.

💡 Use a monotonic decreasing stack and simulate circular array by iterating twice.

💡 Push indices and pop when current element is greater; assign popped indices their next greater.

Why it failed: Output incorrect - likely missed circular wrap-around or stack logic. Fix by iterating over array twice and using monotonic stack properly.

✓ Correctly handles circular array and monotonic stack logic.

t1_02basic

Input{"nums":[3,8,4,1,2]}

Expected[8,-1,8,2,3]

⏱ Performance - must finish in 2000ms

Next greater for 3 is 8; for 8 none; for 4 is 8 (wraps); for 1 is 2; for 2 is 3 (wraps).

💡 Remember to consider elements after the current index and wrap around.

💡 Maintain a stack of indices with decreasing values to find next greater efficiently.

💡 Iterate twice over nums length to simulate circular behavior and update answers.

Why it failed: Wrong output due to missing wrap-around or incorrect stack updates. Fix by simulating circular array with double iteration.

✓ Correctly finds next greater elements including wrap-around.

t2_01edge

Input{"nums":[5]}

Expected[-1]

⏱ Performance - must finish in 2000ms

Single element has no next greater element, so output is [-1].

💡 Check behavior when array length is 1.

💡 Stack should handle single element without errors.

💡 Return [-1] since no greater element exists.

Why it failed: Fails single element case by returning wrong value or error. Fix by handling n=1 and returning [-1].

✓ Correctly returns [-1] for single element input.

t2_02edge

Input{"nums":[7,7,7,7]}

Expected[-1,-1,-1,-1]

⏱ Performance - must finish in 2000ms

All elements equal, so no strictly greater element exists; all outputs are -1.

💡 Consider arrays where all elements are identical.

💡 Next greater requires strictly greater, so none exist here.

💡 Stack should not assign any next greater; all remain -1.

Why it failed: Incorrectly assigns next greater for equal elements. Fix by using strict greater comparison (nums[curr] > nums[stack_top]).

✓ Correctly returns all -1 for identical elements.

t2_03edge

Input{"nums":[5,4,3,2,1]}

Expected[-1,5,5,5,5]

⏱ Performance - must finish in 2000ms

Strictly decreasing array; only wrap-around elements are next greater (5 for all except first).

💡 Test strictly decreasing sequences and wrap-around logic.

💡 Stack should pop smaller elements and assign next greater from wrap-around.

💡 Ensure circular iteration covers all elements.

Why it failed: Fails wrap-around logic for decreasing array. Fix by iterating twice and updating answers correctly.

✓ Correctly handles strictly decreasing array with wrap-around next greater.

t3_01corner

Input{"nums":[1,2,3,4,3]}

Expected[2,3,4,-1,4]

⏱ Performance - must finish in 2000ms

Greedy approach fails here; next greater for last 3 is 4 (wrap-around).

💡 Beware greedy approach that stops at first greater found without circular check.

💡 Use monotonic stack with double iteration to find correct next greater.

💡 Ensure last element's next greater is found by wrapping around.

Why it failed: Greedy approach fails by missing wrap-around next greater. Fix by simulating circular array with double pass and stack.

✓ Correctly finds next greater elements including wrap-around for tricky cases.

t3_02corner

Input{"nums":[2,2,2,3,2]}

Expected[3,3,3,-1,3]

⏱ Performance - must finish in 2000ms

Duplicates with next greater present; must not confuse equal with greater.

💡 Check that next greater is strictly greater, not equal.

💡 Stack must pop only when current element is strictly greater.

💡 Handle duplicates carefully to avoid wrong assignments.

Why it failed: Confuses equal elements as next greater. Fix by using strict comparison nums[curr] > nums[stack_top].

✓ Correctly handles duplicates and finds next greater.

t3_03corner

Input{"nums":[1,2,1,2,1]}

Expected[2,-1,2,-1,2]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors and correct circular indexing for multiple repeats.

💡 Verify indices wrap correctly when searching next greater.

💡 Stack must maintain correct order and update answers properly.

💡 Double iteration ensures all elements get correct next greater.

Why it failed: Off-by-one or indexing errors cause wrong output. Fix by using modulo indexing and iterating twice over 2*n.

✓ Correctly handles circular indexing and repeated elements.

t4_01performance

Input{"nums":[1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991,999990,999989,999988,999987,999986,999985,999984,999983,999982,999981,999980,999979,999978,999977,999976,999975,999974,999973,999972,999971,999970,999969,999968,999967,999966,999965,999964,999963,999962,999961,999960,999959,999958,999957,999956,999955,999954,999953,999952,999951,999950,999949,999948,999947,999946,999945,999944,999943,999942,999941,999940,999939,999938,999937,999936,999935,999934,999933,999932,999931,999930,999929,999928,999927,999926,999925,999924,999923,999922,999921,999920,999919,999918,999917,999916,999915,999914,999913,999912,999911,999910,999909,999908,999907,999906,999905,999904,999903,999902,999901]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, strictly decreasing sequence; O(n) monotonic stack solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out for n=100.

💡 Use O(n) monotonic stack with double iteration for circular array.

💡 Avoid nested loops; push/pop indices efficiently.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) monotonic stack with circular simulation.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following code for a circular queue of capacity 3. After executing these operations in order: enQueue(1), enQueue(2), enQueue(3), deQueue(), enQueue(4), what is the value of the tail pointer?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace enQueue(1), enQueue(2), enQueue(3)

   Initially, head=0, tail=0, size=0. After enQueue(1): tail=1, size=1; enQueue(2): tail=2, size=2; enQueue(3): tail=0 (wrap-around), size=3.

2. Step 2: Trace deQueue() and enQueue(4)

   deQueue() moves head from 0 to 1, size=2. enQueue(4) inserts at tail=0, then tail=1, size=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tail pointer wraps modulo capacity, final tail=1 after last enQueue [OK]

Hint: Tail pointer increments modulo capacity [OK]

Common Mistakes:

• Forgetting modulo wrap-around
• Off-by-one tail position
• Confusing head and tail pointers

2. What is the time and space complexity of the optimal stack-less solution for evaluating a Basic Calculator II expression of length n?

medium

A. O(n) time and O(1) space because it processes the string once and uses only a few variables.

B. O(n^2) time and O(n) space due to repeated string slicing and stack usage.

C. O(n) time and O(n) space because it uses a stack to store intermediate results.

D. O(n log n) time due to sorting operators by precedence and O(1) space.

Solution

1. Step 1: Identify time complexity

   The algorithm scans the input string once, performing constant-time operations per character, so time is O(n).

2. Step 2: Identify space complexity

   Only a fixed number of variables are used (total, last_num, current_num, current_op), so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant variables confirm O(n) time and O(1) space [OK]

Hint: Single pass with fixed vars means O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming stack usage means O(n) space
• Confusing recursion stack with iteration
• Thinking sorting operators is needed

3. What is the time complexity of the optimal monotonic stack solution for the Largest Rectangle in Histogram problem, and why?

medium

A. O(n) because each bar is pushed and popped at most once from the stack

B. O(n) but with O(n^2) worst-case due to stack operations

C. O(n^2) because nested loops are used to find boundaries

D. O(n log n) because each element is pushed and popped multiple times

Solution

1. Step 1: Analyze stack operations

   Each bar is pushed once and popped at most once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops over all elements

   Loops run linearly, no repeated scanning of all elements inside inner loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time complexity due to amortized stack operations [OK]

Hint: Each element pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming stack operations cause O(n log n) or O(n^2)
• Confusing nested loops in brute force with stack approach

4. What is the time complexity of the optimal Remove K Digits algorithm using a monotonic stack on an input string of length n?

medium

A. O(n * k), because each digit can be popped up to k times

B. O(n), because each digit is pushed and popped at most once

C. O(n log n), due to sorting or priority queue operations inside the stack

D. O(n^2), because nested loops remove digits repeatedly

Solution

1. Step 1: Analyze push and pop operations

   Each digit is pushed exactly once onto the stack. Each digit can be popped at most once when a smaller digit arrives.

2. Step 2: Conclude overall complexity

   Since each digit is pushed and popped at most once, total operations are O(n), linear in input size.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack ensures linear time by amortized analysis [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Thinking sorting or nested loops are involved

5. Suppose the calculator expression can contain multiplication '*' and division '/' operators in addition to plus, minus, and parentheses. Which modification to the stack-based approach correctly handles operator precedence and parentheses?

hard

A. Use two stacks: one for numbers and one for operators, applying operators with higher precedence immediately before pushing lower precedence operators

B. Continue using a single stack and apply all operators in the order they appear, ignoring precedence

C. Convert the expression to postfix notation first, then evaluate using a stack

D. Evaluate recursively without any stack, relying on Python's eval() function

Solution

1. Step 1: Understand operator precedence

   Multiplication and division have higher precedence than addition and subtraction, so evaluation order matters.

2. Step 2: Modify stack approach

   Using two stacks (numbers and operators) allows applying higher precedence operators immediately, preserving correct order.

3. Step 3: Why other options fail

   Single stack ignoring precedence leads to wrong results; postfix conversion is valid but more complex; relying on eval() is unsafe and not interview-appropriate.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two-stack approach is standard for precedence and parentheses [OK]

Hint: Two stacks handle precedence and parentheses correctly [OK]

Common Mistakes:

• Ignoring precedence or relying on single stack only