132 Pattern

▶

Steps

setup

Initialize stack and third

We start by creating an empty stack and setting 'third' to negative infinity to represent no '2' candidate found yet.

💡 Initializing 'third' to -∞ ensures any real number will be greater, allowing us to update it correctly during popping.

Line:

stack = []
third = float('-inf')

💡 The stack and 'third' are the core data structures for tracking the 132 pattern.

traverse

Start traversal from right: index 3, element 4

We begin traversing the array from the rightmost element, which is 4 at index 3.

💡 Starting from the right allows us to find the '3' and '2' values before the '1' in the pattern.

Line:

for num in reversed(nums):
    # num = 4 first

💡 The first element processed is the largest index, setting the stage for stack operations.

compare

Check if current element < third

We check if 4 is less than 'third' (-∞). It is not, so we continue.

💡 This check detects if a 132 pattern is found; since 'third' is -∞, no pattern is possible yet.

Line:

if num < third:
    return True

💡 No pattern found at this step because 'third' is still at initial value.

shrink

Pop elements smaller than current (4) from stack

Stack is empty, so no elements are popped.

💡 Popping smaller elements updates 'third' to track the '2' value in the pattern.

Line:

while stack and stack[-1] < num:
    third = stack.pop()

💡 No update to 'third' because stack is empty.

push

Push current element (4) onto stack

We push 4 onto the stack as a candidate '3' value.

💡 Pushing the current number maintains the stack of potential '3's in decreasing order.

Line:

stack.append(num)

💡 Stack now contains [4], representing a potential '3' for future elements.

traverse

Move to next element: index 2, element 3

We move left to the next element, 3 at index 2.

💡 Processing elements from right to left allows us to find the pattern efficiently.

Line:

for num in reversed(nums):
    # num = 3 next

💡 We will compare 3 against stack and 'third' to detect pattern.

compare

Check if current element (3) < third (-∞)

3 is not less than 'third' (-∞), so no pattern found yet.

💡 This check is the key condition to detect the 132 pattern.

Line:

if num < third:
    return True

💡 No pattern detected at this step.

shrink

Pop elements smaller than current (3) from stack

Top of stack is 4, which is not smaller than 3, so no pop occurs.

💡 Popping updates 'third' to track the '2' value, but here no update is needed.

Line:

while stack and stack[-1] < num:
    third = stack.pop()

💡 Stack remains unchanged, 'third' stays -∞.

push

Push current element (3) onto stack

We push 3 onto the stack, which now holds [4, 3].

💡 Stack is maintained in decreasing order from bottom to top.

Line:

stack.append(num)

💡 Stack now has two candidates for '3' in the pattern.

traverse

Move to next element: index 1, element 2

We move left to element 2 at index 1.

💡 Continuing traversal to check for pattern with smaller elements.

Line:

for num in reversed(nums):
    # num = 2 next

💡 We will check if 2 < third and update stack accordingly.

compare

Check if current element (2) < third (-∞)

2 is not less than 'third' (-∞), so no pattern found yet.

💡 Pattern detection depends on 'third' being updated first.

Line:

if num < third:
    return True

💡 No pattern detected at this step.

shrink

Pop elements smaller than current (2) from stack

Top of stack is 3, which is not smaller than 2, so no pop occurs.

💡 No update to 'third' because stack top is larger than current element.

Line:

while stack and stack[-1] < num:
    third = stack.pop()

💡 Stack remains [4, 3], 'third' stays -∞.

push

Push current element (2) onto stack

We push 2 onto the stack, which now holds [4, 3, 2].

💡 Stack continues to hold candidate '3' values in decreasing order.

Line:

stack.append(num)

💡 Stack grows with each element processed from right to left.

traverse

Move to last element: index 0, element 1

We move to the leftmost element, 1 at index 0.

💡 This is the last element to check for the 132 pattern.

Line:

for num in reversed(nums):
    # num = 1 last

💡 We will check if 1 < third and update stack accordingly.

compare

Check if current element (1) < third (-∞)

1 is not less than 'third' (-∞), so no pattern found yet.

💡 Pattern detection depends on 'third' being updated first.

Line:

if num < third:
    return True

💡 No pattern detected at this step.

shrink

Pop elements smaller than current (1) from stack

Top of stack is 2, which is not smaller than 1, so no pop occurs.

💡 No update to 'third' because stack top is larger than current element.

Line:

while stack and stack[-1] < num:
    third = stack.pop()

💡 Stack remains [4, 3, 2], 'third' stays -∞.

push

Push current element (1) onto stack

We push 1 onto the stack, which now holds [4, 3, 2, 1].

💡 Stack continues to hold candidate '3' values in decreasing order.

Line:

stack.append(num)

💡 Stack now contains all elements in decreasing order from bottom to top.

reconstruct

Traversal complete, return false

No 132 pattern was found after processing all elements, so we return false.

💡 Returning false confirms the input does not contain the pattern.

Line:

return False

💡 The algorithm correctly identifies absence of the pattern.

def find132pattern(nums):
    stack = []  # STEP 1: initialize stack
    third = float('-inf')  # STEP 1: initialize third
    for num in reversed(nums):  # STEP 2: traverse from right
        if num < third:  # STEP 3: check pattern
            return True  # STEP 3: pattern found
        while stack and stack[-1] < num:  # STEP 4: pop smaller elements
            third = stack.pop()  # STEP 4: update third
        stack.append(num)  # STEP 5: push current num
    return False  # STEP 6: no pattern found

📊

132 Pattern - Watch the Algorithm Execute, Step by Step

Watching each stack operation and comparison live helps you understand how the algorithm efficiently tracks the '2' in the 132 pattern and why certain elements are pushed or popped.

no_op

Stack (top→bottom)

empty

no_opElement[3]: 4

Stack (top→bottom)

empty

no_opElement[3]: 4

Stack (top→bottom)

empty

no_opElement[3]: 4

Stack (top→bottom)

empty

pushElement[3]: 4

Stack (top→bottom)

4

↑ pushed: 4

no_opElement[2]: 3

Stack (top→bottom)

4

no_opElement[2]: 3

Stack (top→bottom)

4

no_opElement[2]: 3

Stack (top→bottom)

4

pushElement[2]: 3

Stack (top→bottom)

3

4

↑ pushed: 3

no_opElement[1]: 2

Stack (top→bottom)

3

4

no_opElement[1]: 2

Stack (top→bottom)

3

4

no_opElement[1]: 2

Stack (top→bottom)

3

4

pushElement[1]: 2

Stack (top→bottom)

2

3

4

↑ pushed: 2

no_opElement[0]: 1

Stack (top→bottom)

2

3

4

no_opElement[0]: 1

Stack (top→bottom)

2

3

4

no_opElement[0]: 1

Stack (top→bottom)

2

3

4

pushElement[0]: 1

Stack (top→bottom)

1

2

3

4

↑ pushed: 1

no_op

Stack (top→bottom)

1

2

3

4

Contributes: false

Key Takeaways

✓ The 'third' variable tracks the '2' in the 132 pattern by storing the last popped element from the stack.

This insight is hard to see from code alone because 'third' updates happen inside a loop and affect pattern detection indirectly.

✓ The stack maintains a decreasing sequence of candidate '3' values from right to left.

Visualizing the stack state step-by-step clarifies how the algorithm efficiently narrows down potential '3's.

✓ If the current element is less than 'third', the 132 pattern is found immediately.

Seeing this condition fail repeatedly before 'third' updates helps understand why the algorithm continues processing.

Practice

1. You are given a string consisting of '(' and ')' characters. The task is to find the length of the longest substring that forms a valid parentheses sequence. Which of the following approaches guarantees an optimal O(n) time and O(1) space solution?

easy

A. Perform two passes over the string using counters for '(' and ')' to track valid substrings.

B. Use dynamic programming to store the length of valid substrings ending at each index.

C. Use a brute force approach checking all substrings and validating each with a stack.

D. Use a stack to store characters and pop when matching pairs are found.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the longest valid parentheses substring efficiently.

2. Step 2: Evaluate approaches for optimal time and space

   The two-pass counter approach scans left-to-right and right-to-left using counters, achieving O(n) time and O(1) space, unlike stack or DP which use extra space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pass counter approach is known for O(n) time and O(1) space [OK]

Hint: Two-pass counter approach uses constant space [OK]

Common Mistakes:

• Confusing stack approach as O(1) space
• Assuming DP is always optimal
• Believing brute force is feasible

2. You are given a stream of daily stock prices. For each new price, you must find how many consecutive previous days (including today) had prices less than or equal to the current price. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Using a monotonic stack that stores indices and precomputed spans to skip redundant checks

B. Greedy approach selecting the maximum price seen so far without backtracking

C. Dynamic programming with memoization of maximum spans for subproblems

D. Brute force nested loops checking all previous days for each price

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding the span of consecutive days with prices less than or equal to the current price, which suggests a need to efficiently skip over previous days that are dominated by the current price.

2. Step 2: Identify the optimal approach

   A monotonic stack storing indices allows popping all previous days with prices less or equal to the current price in O(1) amortized time per element, enabling O(n) total time. This approach precomputes spans by using index differences, avoiding nested loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known to solve stock span in linear time [OK]

Hint: Monotonic stack skips redundant comparisons efficiently [OK]

Common Mistakes:

• Assuming greedy or DP solves this optimally
• Using nested loops for each price

3. Identify the bug in the following circular queue implementation snippet:

medium

A. Line updating tail pointer should use modulo operation to wrap around.

B. Line checking if queue is full should compare head and tail pointers instead of size.

C. Line initializing queue should use an empty list instead of fixed-size array.

D. Line incrementing size should be before updating tail pointer.

Solution

1. Step 1: Examine tail pointer update

   Tail pointer increments by 1 but lacks modulo operation, so it can exceed array bounds.

2. Step 2: Understand consequences

   Without modulo, tail pointer goes out of range causing runtime errors or incorrect behavior.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modulo operation is essential for circular wrap-around [OK]

Hint: Tail pointer must wrap modulo capacity [OK]

Common Mistakes:

• Forgetting modulo wrap-around
• Using size incorrectly to check full
• Misordering size increment

4. If the input matrix can contain '2's representing cells that can be counted as either 0 or 1 (i.e., flexible cells), which modification to the maximalRectangle algorithm is correct to find the largest rectangle of 1s considering '2' as 1 or 0?

hard

A. Treat '2' as '1' in all rows and run the standard maximalRectangle algorithm once.

B. Use backtracking to try all combinations of '2' as '0' or '1' and find the maximal rectangle.

C. Modify the histogram update to count '2' as 0.5 height and adjust largestRectangleArea accordingly.

D. Run maximalRectangle twice: once treating '2' as '1' and once as '0', then take the max area.

Solution

1. Step 1: Understand the flexibility of '2' cells

   Each '2' can be either 0 or 1, so multiple configurations exist.

2. Step 2: Evaluate naive approaches

   Treating all '2's as 1 or 0 misses mixed configurations; running twice is insufficient.

3. Step 3: Correct approach

   Backtracking or bitmasking all combinations of '2' assignments is needed to find the true maximal rectangle.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Only exhaustive search guarantees correctness with flexible cells [OK]

Hint: Flexible cells require exploring all assignments [OK]

Common Mistakes:

• Assuming fixed assignment for '2'
• Partial runs miss mixed cases
• Fractional heights invalid for stack approach

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