132 Pattern

📋

Problem

Imagine you are analyzing stock prices to detect a specific pattern that might indicate a profitable trading opportunity - the 132 pattern.

Given an array of n integers nums, determine if there exists a 132 pattern in the sequence. A 132 pattern is a subsequence of three integers nums[i], nums[j], nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. Return true if such a pattern exists, otherwise return false.

1 ≤ n ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

Edge cases: Array of length less than 3 → falseAll elements equal → falseStrictly increasing array → false

</>

IDE

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

def find132pattern(nums):
    # Write your solution here
    pass

class Solution {
    public boolean find132pattern(int[] nums) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool find132pattern(vector<int>& nums) {
    // Write your solution here
    return false;
}

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

Common Bugs to Avoid

Wrong: true on strictly increasing arrayIncorrectly allowing non-strict inequalities or not checking all triples properly.✅ Enforce strict inequalities nums[i] < nums[k] < nums[j] and verify all triples.

Wrong: false on input with valid 132 patternFailing to update or track the '2' candidate correctly in the monotonic stack approach.✅ Use a stack to track potential '2' values and update them when popping from the stack.

Wrong: crash or error on empty or single element inputNo base case handling for arrays with length less than 3.✅ Add a guard clause to return false immediately if len(nums) < 3.

Wrong: true on all equal elementsUsing <= instead of < in comparisons allowing equal elements to form pattern.✅ Use strict inequality comparisons only.

Wrong: TLE on large inputUsing brute force or O(n^2) approach instead of O(n) monotonic stack.✅ Implement the O(n) monotonic stack algorithm scanning from right to left.

✓

Test Cases

Make sure your solution handles small and empty inputs gracefully before moving on.

Focus on tricky cases that break greedy or naive stack implementations.

Optimize your solution to linear time using a monotonic stack to handle large inputs efficiently.

t1_01basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

No 132 pattern exists because the sequence is strictly increasing.

💡 Look for a subsequence where nums[i] < nums[k] < nums[j] with i < j < k.

💡 Check if any triple forms the 132 pattern by comparing all pairs.

💡 Try iterating through the array and tracking possible '3' and '2' values with a stack.

Why it failed: Returned true incorrectly - failed to detect no 132 pattern in strictly increasing array. Fix by ensuring the condition nums[i] < nums[k] < nums[j] is strictly checked.

✓ Correctly identified no 132 pattern in strictly increasing sequence.

t1_02basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

132 pattern exists: nums[1]=1 < nums[3]=2 < nums[2]=4 with indices 1 < 2 < 3.

💡 Try to find a '3' and '2' pair where '2' is less than '3' but greater than some earlier '1'.

💡 Use a stack to track candidates for the '2' value while scanning from right to left.

💡 Maintain a variable for the '2' value and update it when popping from the stack.

Why it failed: Returned false incorrectly - missed the 132 pattern present. Fix by correctly updating and checking the '2' candidate using a monotonic stack.

✓ Correctly detected the 132 pattern in the input.

t2_01edge

Input{"nums":[]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty array cannot contain any 132 pattern.

💡 Consider what happens when the input array is empty.

💡 Check if your code handles n=0 without errors and returns false.

💡 Add a base case to return false immediately if array length < 3.

Why it failed: Code crashes or returns true on empty input. Fix by adding a guard clause for arrays with length less than 3.

✓ Correctly returns false for empty input.

t2_02edge

Input{"nums":[5]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element array cannot form a 132 pattern.

💡 Check behavior when array length is 1.

💡 Ensure code returns false for arrays with fewer than 3 elements.

💡 Add explicit length check before main logic.

Why it failed: Returns true or crashes on single element input. Fix by returning false if length < 3.

✓ Correctly returns false for single element input.

t2_03edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

All elements equal means no strictly increasing or decreasing subsequence for 132 pattern.

💡 Consider if equal elements can form a 132 pattern.

💡 Remember the pattern requires strict inequalities: nums[i] < nums[k] < nums[j].

💡 Check that your code enforces strict inequality, not <=.

Why it failed: Returns true incorrectly on all equal elements. Fix by enforcing strict inequalities in comparisons.

✓ Correctly returns false for all equal elements.

t3_01corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

132 pattern exists: nums[2]=0 < nums[3]=3 < nums[4]=4 with indices 2 < 3 < 4.

💡 Beware of greedy approaches that pick the first '3' and '2' without checking all possibilities.

💡 Use a monotonic stack to track potential '2' values from right to left.

💡 Update the '2' candidate when popping from the stack to catch the correct pattern.

Why it failed: Greedy approach fails by not updating '2' candidate correctly, missing the pattern. Fix by using a stack to track and update '2' values properly.

✓ Correctly detects 132 pattern despite tricky ordering.

t3_02corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

132 pattern exists: nums[0]=1 < nums[3]=2 < nums[1]=4 with indices 0 < 1 < 3.

💡 Check if your solution confuses 0/1 knapsack style unbounded vs 0/1 constraints in pattern detection.

💡 Ensure you do not reuse elements incorrectly or skip valid subsequences.

💡 Use a monotonic stack scanning from right to left to maintain correct order and values.

Why it failed: Incorrectly returns false due to mismanagement of indices or reuse of elements. Fix by enforcing strict index ordering and using stack-based approach.

✓ Correctly identifies 132 pattern with proper index and value checks.

t3_03corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

No 132 pattern exists despite presence of smaller and larger values; pattern conditions not met.

💡 Beware off-by-one errors in index comparisons that might falsely detect a pattern.

💡 Verify that i < j < k strictly holds in your checks.

💡 Double-check that nums[i] < nums[k] < nums[j] is strictly enforced.

Why it failed: Returns true incorrectly due to off-by-one or incorrect index ordering. Fix by strictly enforcing i < j < k and value inequalities.

✓ Correctly returns false with proper index and value checks.

t4_01performance

Input{"nums":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with strictly decreasing values to test O(n) monotonic stack solution within 2 seconds.

💡 Brute force O(n^3) or O(n^2) will time out on large inputs.

💡 Use a monotonic stack to achieve O(n) time complexity.

💡 Track the '2' value while scanning from right to left to avoid nested loops.

Why it failed: TLE due to using brute force or quadratic approach. Fix by implementing O(n) monotonic stack algorithm.

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

Practice

1. Given the following code for finding the first unique character in a stream, what is the output after processing the input stream ['a', 'b', 'a']?

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26
    q = deque()
    result = []
    for ch in stream:
        idx = ord(ch) - ord('a')
        freq[idx] += 1
        if freq[idx] == 1:
            q.append(ch)
        while q and freq[ord(q[0]) - ord('a')] > 1:
            q.popleft()
        result.append(q[0] if q else '#')
    return result

print(first_unique_stream(['a', 'b', 'a']))

easy

A. ['a', 'b', '#']

B. ['a', 'a', '#']

C. ['a', 'a', 'b']

D. ['a', 'b', 'b']

Solution

1. Step 1: Trace first iteration with 'a'

   freq['a'] = 1, queue = ['a'], first unique = 'a'

2. Step 2: Trace second iteration with 'b'

   freq['b'] = 1, queue = ['a', 'b'], first unique still 'a' since freq['a'] = 1

3. Step 3: Trace third iteration with 'a'

   freq['a'] = 2, queue front 'a' freq > 1, pop 'a', queue now ['b'], first unique = 'b'

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Queue updates correctly remove duplicates [OK]

Hint: Queue front always holds current first unique or empty [OK]

Common Mistakes:

• Not popping duplicates from queue front
• Appending duplicates to queue multiple times
• Returning wrong character after duplicates

2. Given the following Python function to find previous smaller elements, what is the output when the input array is [3, 7, 1]?

def previous_smaller_element_indexes(arr):
    stack = []
    result = []
    for i, num in enumerate(arr):
        while stack and arr[stack[-1]] >= num:
            stack.pop()
        if stack:
            result.append(arr[stack[-1]])
        else:
            result.append(-1)
        stack.append(i)
    return result

print(previous_smaller_element_indexes([3, 7, 1]))

easy

A. [-1, -1, -1]

B. [-1, 3, -1]

C. [-1, 3, 3]

D. [3, -1, -1]

Solution

1. Step 1: Trace iteration i=0, num=3

   Stack empty, append -1 to result, push index 0 -> stack=[0], result=[-1]

2. Step 2: Trace iteration i=1, num=7

   Stack top index 0 -> arr[0]=3 < 7, so append 3 to result, push index 1 -> stack=[0,1], result=[-1,3]

3. Step 3: Trace iteration i=2, num=1

   Pop while arr[stack[-1]] >= 1: arr[1]=7 >=1 pop, arr[0]=3 >=1 pop, stack empty, append -1, push index 2 -> stack=[2], result=[-1,3,-1]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Output matches expected previous smaller elements for each position [OK]

Hint: Pop all >= current to find closest smaller on left [OK]

Common Mistakes:

• Not popping equal or greater elements leads to wrong result
• Appending wrong element from stack top
• Off-by-one errors in indexing

3. Consider the following buggy code for the basic calculator. Which line contains the subtle bug that causes incorrect results on multi-digit numbers?

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for i, c in enumerate(s):
        if c.isdigit():
            num = int(c)  # Bug here
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Add last number and combine
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
    result += sign * num
    return result

medium

A. Line with 'result += sign * num' inside the '+' or '-' check

B. Line with 'num = int(c)' inside the digit check

C. Line with 'stack.append(result)' inside the '(' check

D. Line with 'result *= stack.pop()' inside the ')' check

Solution

1. Step 1: Analyze digit processing

   Bug is in 'num = int(c)' which resets num instead of accumulating digits for multi-digit numbers.

2. Step 2: Effect of bug

   Multi-digit numbers are treated as single digits, causing incorrect calculation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code uses 'num = num * 10 + int(c)' [OK]

Hint: Multi-digit numbers require accumulation, not reset [OK]

Common Mistakes:

• Resetting num instead of accumulating digits

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

5. Suppose the problem is modified so that the input string may contain wildcard characters '*' that can represent either an opening bracket, a closing bracket, or an empty string. Which of the following approaches correctly adapts the stack-based solution to handle this variant efficiently?

hard

A. Use a brute force approach to try all replacements of '*' and check validity

B. Replace all '*' with empty strings and run the original stack-based validation

C. Use two stacks to track possible opening and closing brackets positions and validate ranges

D. Ignore '*' characters and validate only the remaining brackets with the original stack approach

Solution

1. Step 1: Understand wildcard impact

   Wildcards can represent multiple bracket types or empty, so a single stack is insufficient to track all possibilities.

2. Step 2: Use two stacks approach

   One stack tracks positions of opening brackets, another tracks positions of '*'. This allows matching '*' as needed to balance brackets efficiently in one pass.

3. Step 3: Reject invalid sequences

   After processing, ensure all unmatched opening brackets can be matched by '*' positions appearing after them.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two stacks track brackets and wildcards to handle all cases [OK]

Hint: Two stacks track brackets and wildcards for flexible matching [OK]

Common Mistakes:

• Replacing '*' blindly or ignoring them causes incorrect results