Longest Valid Parentheses

▶

Steps

setup

Initialize counters and max_len

Initialize left, right, and max_len counters to zero before scanning the string left to right.

💡 Starting with zero counters ensures no leftover state affects the scan.

Line:

left = right = max_len = 0

💡 Counters start at zero to track '(' and ')' counts accurately.

traverse

Scan first character '(' from left to right

Process the first character '(' at index 0, increment left counter.

💡 Incrementing left counter tracks an opening parenthesis.

Line:

if ch == '(': left += 1

💡 Left counter counts how many '(' have been seen so far.

traverse

Scan second character '(' from left to right

Process the second character '(' at index 1, increment left counter again.

💡 Another '(' means more potential for valid substrings but no match yet.

Line:

if ch == '(': left += 1

💡 Left counter now 2, right still 0, so no valid substring yet.

traverse

Scan third character ')' from left to right

Process the third character ')' at index 2, increment right counter.

💡 Incrementing right counter tracks a closing parenthesis.

Line:

else: right += 1

💡 Right counter now 1, left is 2, so no equality yet.

compare

Check counters after third character

Compare left and right counters: left=2, right=1. Since right < left, continue scanning.

💡 Counters unequal means no valid substring ends here.

Line:

if left == right:
    max_len = max(max_len, 2 * right)
elif right > left:
    left = right = 0

💡 Valid substring length only updates when counters equal.

setup

Left to right scan complete, reset counters

Reset left and right counters to zero before scanning from right to left.

💡 Resetting counters is necessary to detect valid substrings from the other direction.

Line:

left = right = 0

💡 Counters must be reset to avoid mixing counts from both scans.

traverse

Scan last character ')' from right to left

Process character ')' at index 2 from right to left, increment right counter.

💡 Right counter tracks closing parentheses scanning backwards.

Line:

if ch == ')': right += 1

💡 Right counter now 1, left 0, no match yet.

traverse

Scan second character '(' from right to left

Process character '(' at index 1 from right to left, increment left counter.

💡 Left counter tracks opening parentheses scanning backwards.

Line:

else: left += 1

💡 Left and right counters both 1, indicating a valid substring.

compare

Update max_len after counters equal

Since left == right == 1, update max_len to max(0, 2*1) = 2.

💡 Updating max_len records the longest valid substring found so far.

Line:

if left == right:
    max_len = max(max_len, 2 * left)

💡 Max length reflects the longest balanced substring found scanning backwards.

traverse

Scan first character '(' from right to left

Process character '(' at index 0 from right to left, increment left counter to 2.

💡 Incrementing left counter again increases imbalance.

Line:

else: left += 1

💡 Left counter now 2, right 1, left > right triggers reset.

prune

Reset counters because left > right

Since left (2) > right (1), reset left and right counters to zero.

💡 Resetting counters discards invalid substring candidates.

Line:

elif left > right:
    left = right = 0

💡 Counters reset to avoid counting invalid substrings.

reconstruct

Right to left scan complete, return max_len

Return the maximum length found, which is 2.

💡 The max_len variable holds the length of the longest valid parentheses substring.

Line:

return max_len

💡 The algorithm successfully found the longest valid substring length.

def longestValidParentheses(s: str) -> int:
    left = right = max_len = 0  # STEP 1
    # Left to right scan
    for ch in s:  # STEP 2-5
        if ch == '(': left += 1  # STEP 2,3
        else: right += 1  # STEP 4
        if left == right:  # STEP 5
            max_len = max(max_len, 2 * right)
        elif right > left:
            left = right = 0
    left = right = 0  # STEP 6
    # Right to left scan
    for ch in reversed(s):  # STEP 7-11
        if ch == ')': right += 1  # STEP 7
        else: left += 1  # STEP 8,10
        if left == right:  # STEP 9
            max_len = max(max_len, 2 * left)
        elif left > right:  # STEP 11
            left = right = 0
    return max_len  # STEP 12

📊

Longest Valid Parentheses - Watch the Algorithm Execute, Step by Step

Watching each counter increment and reset helps you understand how the algorithm detects valid parentheses substrings without using a stack, and why two passes are necessary.

no_op

Stack (top→bottom)

empty

pushElement[0]: (

Stack (top→bottom)

(

↑ pushed: (

pushElement[1]: (

Stack (top→bottom)

(

(

↑ pushed: (

pushElement[2]: )

Stack (top→bottom)

)

(

(

↑ pushed: )

no_opElement[2]: )

Stack (top→bottom)

)

(

(

no_op

Stack (top→bottom)

)

(

(

pushElement[2]: )

Stack (top→bottom)

)

)

(

(

↑ pushed: )

pushElement[1]: (

Stack (top→bottom)

(

)

)

(

(

↑ pushed: (

Contributes: 2

no_opElement[1]: (

Stack (top→bottom)

(

)

)

(

(

Contributes: 2

pushElement[0]: (

Stack (top→bottom)

(

(

)

)

(

(

↑ pushed: (

Contributes: 2

no_opElement[0]: (

Stack (top→bottom)

(

(

)

)

(

(

Contributes: 2

no_op

Stack (top→bottom)

(

(

)

)

(

(

Contributes: 2

Key Takeaways

✓ The two-pass scanning with counters effectively detects valid parentheses substrings without using a stack.

This insight is hard to see from code alone because the counters' role is subtle and requires watching how they increment and reset.

✓ Counters reset when invalid sequences are detected, which prunes impossible substrings and ensures correctness.

Seeing the reset visually clarifies why the algorithm doesn't count invalid sequences.

✓ Max length updates only when left and right counters are equal, indicating balanced parentheses.

Watching this decision helps understand how the algorithm identifies valid substring boundaries.

Practice

1. 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

2. You are given a circular array of integers and need to find, for each element, the next greater element when traversing the array circularly. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking each element's next greater by scanning forward twice

B. Greedy approach selecting next greater element by local comparisons only

C. Dynamic programming with memoization of next greater elements

D. Monotonic stack with explicit circular array copy to simulate circular traversal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the next greater element for each item in a circular array, which means elements after the end wrap around to the start.

2. Step 2: Identify algorithmic pattern

   Brute force is O(n²), greedy/local comparisons fail on circular wrap, and DP is not naturally suited. Monotonic stack with explicit circular array copy simulates circular traversal efficiently in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Monotonic stack with doubled array -> O(n) time [OK]

Hint: Circular array + next greater -> monotonic stack with doubling [OK]

Common Mistakes:

• Assuming greedy local comparisons suffice for circular arrays
• Thinking DP applies directly without circular simulation
• Believing brute force is optimal for large inputs

3. Suppose the calculator must now support expressions where numbers can be reused multiple times (e.g., "2*2*2") and the input length can be very large. Which modification to the optimal approach is necessary to handle this efficiently?

hard

A. Switch to a brute force left-to-right evaluation ignoring precedence to reduce complexity.

B. Implement memoization to cache results of subexpressions to avoid recomputation.

C. Use a stack to immediately evaluate multiplication and division, but keep track of last_num to handle repeated operations efficiently.

D. Use recursion with backtracking to explore all possible reuse combinations.

Solution

1. Step 1: Understand reuse impact

   Repeated multiplication/division requires immediate evaluation to maintain precedence and efficiency.

2. Step 2: Identify suitable approach

   Using a stack or stack-like variables to immediately compute * and / handles repeated operations efficiently without extra overhead.

3. Step 3: Reject alternatives

   Brute force ignores precedence, memoization is unnecessary for linear evaluation, recursion/backtracking is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Immediate evaluation with stack variables handles reuse and large inputs efficiently [OK]

Hint: Immediate evaluation with stack variables handles repeated ops efficiently [OK]

Common Mistakes:

• Ignoring precedence in reuse
• Using recursion unnecessarily
• Trying brute force for efficiency

4. Suppose the decoding problem is extended so that the repeat counts can be zero or negative, and substrings can be reused multiple times in different parts of the string. Which modification to the stack-based decoding algorithm correctly handles these new constraints?

hard

A. Ignore zero or negative counts and treat them as 1; reuse substrings by caching decoded results in a dictionary

B. Modify the algorithm to skip substrings with zero or negative counts and use memoization to reuse decoded substrings efficiently

C. Use recursion only, as stack-based approach cannot handle zero or negative counts or reuse

D. Preprocess the string to remove zero or negative counts and decode normally without caching

Solution

1. Step 1: Handle zero or negative counts

   Zero or negative repeats mean skipping or reversing substrings; algorithm must explicitly check counts and skip or handle accordingly.

2. Step 2: Implement substring reuse

   Memoization caches decoded substrings to avoid recomputation when reused multiple times, improving efficiency.

3. Step 3: Combine skipping invalid repeats and memoization

   Stack-based approach extended with memoization and count checks correctly handles new constraints.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization plus count validation handles reuse and zero/negative repeats [OK]

Hint: Memoize decoded substrings and skip invalid repeats [OK]

Common Mistakes:

• Ignoring zero/negative counts
• Failing to cache repeated substrings

5. Suppose the stock prices can be negative and you want to compute the span as before. Which modification to the monotonic stack approach correctly handles negative prices without breaking the algorithm?

hard

A. Store pairs of (price, span) in the stack and accumulate spans when popping

B. Change the while condition to pop only when top price is strictly less than current price

C. Use a balanced binary search tree instead of a stack to handle negative values

D. No change needed; the existing monotonic stack approach works for negative prices

Solution

1. Step 1: Understand impact of negative prices

   Negative prices do not affect the monotonic stack logic, but to handle spans correctly, storing spans with prices helps accumulate consecutive spans efficiently.

2. Step 2: Why storing (price, span) pairs works

   When popping smaller or equal prices, their spans can be added to the current span, allowing correct span calculation even with negative or mixed values.

3. Step 3: Why other options fail

   Changing while condition to strict less breaks equal price handling. Balanced BST is unnecessary overhead. No change ignores span accumulation needed for correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Storing spans with prices is a known robust solution [OK]

Hint: Store (price, span) pairs to accumulate spans correctly [OK]

Common Mistakes:

• Assuming no change needed
• Using strict less instead of less or equal