Next Greater Element I

▶

Steps

setup

Initialize stack, map, and nums1 set

Create an empty stack, an empty map for next greater elements, and a set from nums1 to track which elements still need answers.

💡 Initializing these structures sets up the data needed to efficiently find next greater elements and track progress.

Line:

stack = []
next_greater_map = {}
nums1_set = set(nums1)

💡 The set allows quick membership checks to know when all nums1 elements have been resolved.

traverse

Process first element in nums2: 1

Start iterating nums2; current number is 1. Stack is empty, so push 1 onto the stack.

💡 Pushing the first element initializes the stack and starts the process of finding next greater elements.

Line:

for num in nums2:
    # num = 1
    stack.append(num)

💡 Stack now holds 1, waiting for a greater number to appear.

traverse

Process second element in nums2: 3, pop smaller elements

Current number is 3. Since 3 > top of stack (1), pop 1 and record next greater element 3 for 1. Remove 1 from nums1_set because it is in nums1.

💡 Popping smaller elements reveals their next greater element, which is the current number.

Line:

while stack and num > stack[-1]:
    smaller = stack.pop()
    next_greater_map[smaller] = num
    if smaller in nums1_set:
        nums1_set.remove(smaller)

💡 1's next greater element is 3, so it can be removed from the set of unresolved nums1 elements.

traverse

Push 3 onto stack after popping smaller elements

After popping smaller elements, push current number 3 onto the stack to find its next greater element later.

💡 Pushing 3 maintains the stack's decreasing order and tracks unresolved elements.

Line:

stack.append(num)

💡 Stack now holds 3, waiting for a greater number.

traverse

Process third element in nums2: 4, pop smaller elements

Current number is 4. Since 4 > top of stack (3), pop 3 and record next greater element 4 for 3. 3 is not in nums1_set, so no removal.

💡 Popping 3 shows 4 is its next greater element, but since 3 is not in nums1, no set update needed.

Line:

while stack and num > stack[-1]:
    smaller = stack.pop()
    next_greater_map[smaller] = num
    if smaller in nums1_set:
        nums1_set.remove(smaller)

💡 3's next greater element is 4, but it is not in nums1 so no effect on set.

traverse

Push 4 onto stack after popping smaller elements

Push current number 4 onto the stack to track its next greater element.

💡 Pushing 4 keeps the stack ready for future comparisons.

Line:

stack.append(num)

💡 Stack now contains 4, waiting for a greater number.

traverse

Process fourth element in nums2: 2, no pop needed

Current number is 2. Since 2 is not greater than top of stack (4), push 2 onto the stack.

💡 No smaller elements to pop means 2 waits on stack for a future greater number.

Line:

stack.append(num)

💡 Stack now has [4, 2], maintaining decreasing order.

traverse

Check if all nums1 elements resolved

After processing 2, check if nums1_set is empty. It contains {4,2}, so continue processing.

💡 We only break early if all nums1 elements have their next greater elements found.

Line:

if not nums1_set:
    break

💡 Still need to find next greater elements for 4 and 2.

prune

No more elements in nums2, assign -1 to remaining stack elements

Pop remaining elements 2 and 4 from stack and assign -1 as their next greater element since none exists.

💡 Assigning -1 finalizes next greater elements for unresolved numbers.

Line:

while stack:
    next_greater_map[stack.pop()] = -1

💡 2 and 4 have no next greater elements in nums2.

prune

Pop last element 4 and assign -1

Pop 4 from stack and assign -1 as its next greater element.

💡 Completes the mapping for all elements in nums1.

Line:

while stack:
    next_greater_map[stack.pop()] = -1

💡 4 has no next greater element in nums2.

reconstruct

Construct final answer for nums1 using next_greater_map

Build the result list by mapping each element in nums1 to its next greater element from the map.

💡 This step extracts the answers for the original query elements in nums1.

Line:

return [next_greater_map[x] for x in nums1]

💡 The final answer is [-1, 3, -1] matching the problem's expected output.

from typing import List

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    stack = []  # STEP 1: Initialize stack
    next_greater_map = {}  # STEP 1: Initialize map
    nums1_set = set(nums1)  # STEP 1: Initialize set
    for num in nums2:  # STEP 2-7: Traverse nums2
        while stack and num > stack[-1]:  # STEP 3,5: Pop smaller elements
            smaller = stack.pop()  # STEP 3,5: Pop
            next_greater_map[smaller] = num  # STEP 3,5: Record next greater
            if smaller in nums1_set:  # STEP 3,5: Check if in nums1
                nums1_set.remove(smaller)  # STEP 3,5: Remove from set
                if not nums1_set:  # STEP 8: Early exit
                    break
        stack.append(num)  # STEP 2,4,6,7: Push current num
        if not nums1_set:  # STEP 8: Early exit
            break
    while stack:  # STEP 9,10: Assign -1 to remaining
        next_greater_map[stack.pop()] = -1
    return [next_greater_map[x] for x in nums1]  # STEP 11: Construct answer

📊

Next Greater Element I - 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)

1

↑ pushed: 1

popElement[1]: 3

Stack (top→bottom)

empty

↓ popped: [1]

Contributes: {"1":3}

pushElement[1]: 3

Stack (top→bottom)

3

↑ pushed: 3

popElement[2]: 4

Stack (top→bottom)

empty

↓ popped: [3]

Contributes: {"3":4}

pushElement[2]: 4

Stack (top→bottom)

4

↑ pushed: 4

pushElement[3]: 2

Stack (top→bottom)

2

4

↑ pushed: 2

no_opElement[3]: 2

Stack (top→bottom)

2

4

pop

Stack (top→bottom)

4

↓ popped: [2]

Contributes: {"2":-1}

pop

Stack (top→bottom)

empty

↓ popped: [4]

Contributes: {"4":-1}

no_op

Stack (top→bottom)

empty

Contributes: [-1,3,-1]

Key Takeaways

✓ The stack maintains a decreasing sequence, allowing immediate identification of next greater elements when a larger number arrives.

This insight is difficult to see from code alone because the stack operations and their effect on order are implicit.

✓ Using a set for nums1 elements enables early termination of the iteration once all next greater elements are found.

This optimization avoids unnecessary processing and is clearer when watching the set shrink step-by-step.

✓ Elements remaining in the stack after processing nums2 have no next greater element, so they are assigned -1.

This final cleanup step is easy to overlook in code but critical for correctness.

Practice

1. Consider the following Python code implementing the optimal 132 pattern detection algorithm. What is the return value when the input is [3, 1, 4, 2]?

easy

A. None

B. False

C. Raises an error

D. True

Solution

1. Step 1: Trace the loop with input [3,1,4,2]

   Iterate reversed: 2,4,1,3. Initially, stack=[], third=-inf. - num=2: stack empty, append 2. - num=4: stack top 2 < 4, pop 2, third=2, append 4. - num=1: 1 < third(2), return True.

2. Step 2: Confirm early return

   At num=1, condition triggers return True, so output is True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Early return on detecting 132 pattern confirmed [OK]

Hint: Early return when num < third triggers True [OK]

Common Mistakes:

• Confusing iteration order
• Misunderstanding when third updates
• Off-by-one in stack operations

2. Consider the following buggy code snippet for the optimal calculator. Which line contains the subtle bug that causes incorrect results for expressions with negative division?

medium

A. Line with 'current_op = c' updating the operator

B. Line with 'last_num = last_num // current_num' (integer division without handling negatives)

C. Line with 'current_num = current_num * 10 + int(c)' parsing digits

D. Line with 'total += last_num' inside '+' case

Solution

1. Step 1: Identify division handling

   Integer division of negative numbers must truncate toward zero, not floor.

2. Step 2: Locate bug line

   The line 'last_num = last_num // current_num' does not handle negative last_num correctly, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct negative division requires special handling, missing here [OK]

Hint: Negative division truncation requires special code [OK]

Common Mistakes:

• Ignoring negative division truncation
• Forgetting to add last_num at end
• Misparsing digits

3. What is the time complexity of the push operation in the optimal one-queue implementation of a stack using queues, where the queue is rotated after each push to maintain stack order?

medium

A. O(1) amortized, because each element is enqueued once

B. O(log n), due to partial rotations of the queue

C. O(n^2), because rotations accumulate over multiple pushes

D. O(n), because after each push, the queue is rotated by dequeuing and enqueuing all previous elements

Solution

1. Step 1: Identify complexity of outer and inner loops

   Each push appends one element and then rotates the queue by moving all other elements (n-1) times.

2. Step 2: Check if rotations accumulate

   Each push costs O(n) individually, not O(n^2) overall, because rotations happen per push, not nested.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Rotation after push moves all existing elements once -> O(n) per push [OK]

Hint: Rotation moves all existing elements once per push -> O(n) [OK]

Common Mistakes:

• Assuming push is O(1) because enqueue is O(1)
• Confusing total cost over multiple pushes with single push cost
• Thinking rotations are partial and thus O(log n)

4. The following code attempts to find the longest valid parentheses substring using a stack-based approach. Identify the line containing the subtle bug that causes incorrect results for inputs starting with valid parentheses at index 0.

def longestValidParentheses(s: str) -> int:
    stack = []
    max_len = 0
    stack.append(-1)  # Initialize stack with -1
    for i, ch in enumerate(s):
        if ch == '(': 
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

medium

A. Line 4: stack initialized with -1

B. Line 9: popping from stack without checking if empty

C. Line 3: stack initialized as empty list

D. Line 12: resetting stack with current index when empty

Solution

1. Step 1: Analyze stack pop operation

   Line 9 pops from stack without checking if stack is empty, which can cause runtime error or incorrect behavior if stack is empty.

2. Step 2: Understand initialization and reset logic

   Stack initialized with -1 (line 4) is correct to handle valid substrings starting at index 0; resetting stack with current index (line 12) is also correct.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pop without empty check leads to subtle bugs on edge cases [OK]

Hint: Popping stack without empty check causes subtle bugs [OK]

Common Mistakes:

• Forgetting to initialize stack with -1
• Not checking stack emptiness before pop
• Incorrect reset of stack after imbalance

5. Consider this buggy code for the stock span problem. Which line contains the subtle bug that causes incorrect spans when prices are equal?

medium

A. Line 9: span calculation does not add 1 when stack is not empty

B. Line 11: appending price after appending index to stack

C. Line 6: while condition uses '<' instead of '<='

D. Line 7: popping from stack without checking if empty

Solution

1. Step 1: Identify the bug in while condition

   The condition uses '<' instead of '<=', so equal prices are not popped, causing incorrect spans.

2. Step 2: Confirm other lines are correct

   Span calculation correctly handles empty stack. Appending order is correct. Stack emptiness is checked before popping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using '<=' ensures equal prices are popped for correct spans [OK]

Hint: Use '<=' in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using '<' causes incorrect spans for equal prices
• Misplaced span calculation