Valid Parentheses

▶

Steps

setup

Initialize stack and pairs dictionary

Create an empty stack to hold opening brackets and a dictionary mapping closing brackets to their matching opening brackets.

💡 This setup is essential to track unmatched opening brackets and quickly verify matches for closing brackets.

Line:

stack = []
pairs = {')': '(', ']': '[', '}': '{'}

💡 The stack starts empty, ready to collect opening brackets, and pairs provide a quick lookup for matching.

traverse

Process first character '('

Read the first character '(' which is an opening bracket, so push it onto the stack.

💡 Pushing opening brackets onto the stack delays matching until a closing bracket is found.

Line:

for char in s:
    if char in pairs.values():
        stack.append(char)

💡 Opening brackets are stored to be matched later in correct order.

traverse

Process second character ')'

Read the character ')' which is a closing bracket. Check if the stack top matches its corresponding opening bracket.

💡 Matching closing brackets must correspond to the last unmatched opening bracket on the stack.

Line:

elif char in pairs:
    if not stack or stack[-1] != pairs[char]:
        return False
    stack.pop()

💡 A matching pair is found, so the opening bracket is removed from the stack.

traverse

Process third character '['

Read the character '[' which is an opening bracket, so push it onto the stack.

💡 Opening brackets are pushed to wait for their matching closing brackets.

Line:

if char in pairs.values():
    stack.append(char)

💡 Stack now holds '[' waiting for a match.

traverse

Process fourth character ']'

Read the character ']' which is a closing bracket. Check if it matches the top of the stack.

💡 Closing brackets must match the last opening bracket to maintain validity.

Line:

elif char in pairs:
    if not stack or stack[-1] != pairs[char]:
        return False
    stack.pop()

💡 The pair '[]' is matched and removed from the stack.

traverse

Process fifth character '{'

Read the character '{' which is an opening bracket, so push it onto the stack.

💡 Opening brackets are stored to be matched later.

Line:

if char in pairs.values():
    stack.append(char)

💡 Stack now contains '{' waiting for a closing match.

traverse

Process sixth character '}'

Read the character '}' which is a closing bracket. Check if it matches the top of the stack.

💡 Matching closing brackets remove the corresponding opening bracket from the stack.

Line:

elif char in pairs:
    if not stack or stack[-1] != pairs[char]:
        return False
    stack.pop()

💡 The pair '{}' is matched and popped from the stack.

traverse

Move pointer beyond last character

Move the pointer beyond the last character to indicate end of input processing.

💡 This step shows the pointer moving past the last character before final validation.

Line:

for char in s:  # pointer moves beyond last character

💡 Pointer has processed all characters in the string.

prune

End of string reached, check stack emptiness

All characters processed. Check if the stack is empty to determine if the string is valid.

💡 An empty stack means all opening brackets were matched correctly.

Line:

return not stack

💡 Stack empty means valid parentheses string.

def isValid(s: str) -> bool:
    stack = []  # STEP 1
    pairs = {')': '(', ']': '[', '}': '{'}  # STEP 1
    for char in s:  # STEP 2 to 7
        if char in pairs.values():  # STEP 2,4,6
            stack.append(char)  # push opening bracket
        elif char in pairs:  # STEP 3,5,7
            if not stack or stack[-1] != pairs[char]:  # check match
                return False
            stack.pop()  # pop matched opening bracket
        else:
            return False
    return not stack  # STEP 9

📊

Valid Parentheses - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation on the stack reveals how the algorithm ensures every opening bracket is properly closed in order, which is the core logic behind validating parentheses.

no_op

Stack (top→bottom)

empty

pushElement[0]: (

Stack (top→bottom)

(

↑ pushed: (

popElement[1]: )

Stack (top→bottom)

empty

↓ popped: [(]

pushElement[2]: [

Stack (top→bottom)

[

↑ pushed: [

popElement[3]: ]

Stack (top→bottom)

empty

↓ popped: [[]

pushElement[4]: {

Stack (top→bottom)

{

↑ pushed: {

popElement[5]: }

Stack (top→bottom)

empty

↓ popped: [{]

no_op

Stack (top→bottom)

empty

no_op

Stack (top→bottom)

empty

Contributes: true

Key Takeaways

✓ The stack data structure perfectly models the nested and ordered nature of parentheses matching.

This insight is difficult to grasp from code alone because the stack's LIFO behavior directly corresponds to the nesting order, which is clearer when visualized.

✓ Each push corresponds to an opening bracket waiting for a match, and each pop corresponds to a successful match with a closing bracket.

Seeing these operations step-by-step clarifies how the algorithm maintains correctness incrementally.

✓ Early exit occurs if a closing bracket does not match the stack top or if the stack is empty when a closing bracket appears.

This decision prevents unnecessary processing and is easier to understand when watching the stack state fail to match.

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. Given the following code for sliding window maximum, what is the returned list when nums = [2, 1, 3] and k = 2?

easy

A. [3, 3]

B. [2, 1]

C. [1, 3]

D. [2, 3]

Solution

1. Step 1: Trace iteration i=0

   dq empty, append index 0 (value 2). No output yet since i < k-1.

2. Step 2: Trace iteration i=1

   nums[1]=1 < nums[0]=2, so append index 1. Window size reached, max is nums[dq[0]]=2.

3. Step 3: Trace iteration i=2

   nums[2]=3 > nums[1]=1 pop index 1, nums[2]=3 > nums[0]=2 pop index 0, append index 2. Max is nums[2]=3.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Output matches expected sliding window max [OK]

Hint: Pop smaller elements before appending new index [OK]

Common Mistakes:

• Forgetting to remove out-of-window indices
• Appending max too early or late

3. What is the time complexity of the optimized monotonic stack solution for the Next Greater Element I problem, where m = length of nums1 and n = length of nums2?

medium

A. O(m * n) because for each element in nums1, we scan nums2 to find the next greater element.

B. O(n) because only nums2 is processed with a stack; nums1 lookup is constant time.

C. O(n + m) because each element in nums2 is pushed and popped at most once, and mapping results for nums1 is O(m).

D. O(n log n) due to sorting nums2 before processing.

Solution

1. Step 1: Analyze stack operations on nums2

   Each element in nums2 is pushed once and popped at most once, so stack operations are O(n).

2. Step 2: Analyze mapping and lookup for nums1

   Mapping next greater elements for nums1 uses a hashmap and set lookups, each O(1), done m times, total O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Combined complexity is O(n + m), not O(m*n) or O(n log n) [OK]

Hint: Stack operations are linear; hashmap lookups are constant [OK]

Common Mistakes:

• Assuming nested loops cause O(m*n) complexity
• Confusing sorting-based approaches with stack-based ones
• Ignoring the cost of hashmap lookups

4. What is the time complexity of the optimal monotonic stack solution that uses an explicit circular array copy (doubling the array) for the Next Greater Element II problem, and why?

medium

A. O(n) because each element is pushed and popped at most once despite doubling

B. O(n²) because the doubled array doubles the iterations

C. O(n log n) due to sorting implicit in stack operations

D. O(2n) which simplifies to O(n) but requires extra space

Solution

1. Step 1: Identify loop iterations

   The loop runs over doubled array of length 2n, so 2n iterations.

2. Step 2: Analyze stack operations

   Each element index is pushed once and popped once at most, so total stack operations are O(n). The doubling does not cause repeated pushes for the same index.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubling array length does not multiply complexity beyond linear [OK]

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

Common Mistakes:

• Assuming doubling array doubles complexity to O(n²)
• Confusing stack operations with sorting complexity
• Ignoring that indices are pushed only once

5. Suppose you want to extend the Minimum Stack to support a new operation getMinK(k) that returns the k-th smallest element in the stack in O(1) time. Which modification to the single stack with encoded minimums approach is most appropriate?

hard

A. Maintain a balanced binary search tree alongside the stack to track all elements for quick k-th minimum queries.

B. Modify the encoding to store differences for all k smallest elements in the single stack.

C. Use multiple auxiliary stacks, each tracking the minimum for a different k value.

D. Store all elements in a sorted array and update it on every push and pop to answer getMinK in O(1).

Solution

1. Step 1: Understand getMinK(k) requirement

   Retrieving the k-th smallest element in O(1) requires a data structure supporting order statistics efficiently.

2. Step 2: Evaluate options

   Encoding differences only tracks minimum, not order statistics. Multiple stacks or sorted arrays are inefficient for updates. Balanced BST or order-statistics tree supports O(log n) updates and O(1) k-th minimum retrieval with augmentation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with order statistics is standard for k-th minimum queries [OK]

Hint: Order statistics require balanced tree, not simple stack encoding [OK]

Common Mistakes:

• Trying to encode multiple mins in one stack
• Using multiple stacks without order info
• Sorting array on every update is inefficient