Problem Description

You are given an array of n integers called nums. Your task is to determine if there exists a 132 pattern in this array.

A 132 pattern is defined as a subsequence of three integers nums[i], nums[j], and nums[k] that satisfy the following conditions:

• The indices must follow the order: i < j < k
• The values must follow the pattern: nums[i] < nums[k] < nums[j]

In other words, you need to find three numbers where:

• The first number (at position i) is the smallest
• The second number (at position j) is the largest
• The third number (at position k) is in the middle value-wise
• These three numbers appear in this specific order in the array (though not necessarily consecutively)

The name "132 pattern" comes from the relative ordering of the values: if we label them as 1 (smallest), 3 (largest), and 2 (middle), they appear in the sequence as 1-3-2.

Return true if such a pattern exists in the array, otherwise return false.

For example:

• In the array [1, 2, 3, 4], there is no 132 pattern
• In the array [3, 1, 4, 2], there is a 132 pattern: nums[1]=1, nums[2]=4, nums[3]=2 where 1 < 2 < 4

Intuition

The key insight is to traverse the array from right to left while keeping track of potential candidates for the middle value (the "2" in the 132 pattern).

Think about it this way: if we're looking for a pattern where nums[i] < nums[k] < nums[j] with i < j < k, we can fix our position and look for what comes before. When we traverse from right to left, we're essentially looking at potential nums[j] values and trying to find if there's a valid nums[i] that would complete the pattern.

The brilliant idea here is to maintain a variable vk that represents the maximum possible value for nums[k] (the middle value in our 132 pattern). As we traverse backwards:

1. If we encounter a value smaller than vk, we've found our nums[i]! Why? Because vk already represents a valid nums[k] that came after some nums[j] that's larger than it. So we have nums[i] < vk (nums[k]) < some previous nums[j].

2. We use a stack to keep track of potential nums[k] values. When we see a new element x:

   • All stack elements smaller than x can potentially be nums[k] values (with x being their corresponding nums[j])
   • We pop these smaller elements and update vk to the maximum among them
   • This ensures vk always holds the best (largest possible) middle value for any 132 pattern we've seen so far

3. The stack maintains elements in decreasing order from bottom to top, which helps us efficiently find and update potential nums[k] values.

By processing from right to left, we ensure that when we find a valid nums[i] (a value less than vk), we already know that there exists a valid nums[j] and nums[k] to its right that form the 132 pattern.

Solution Approach

The implementation uses a monotonic stack approach with a clever backwards traversal:

1. Initialize variables:

   • vk = -inf: Represents the maximum valid nums[k] (middle value) we've found so far
   • stk = []: A stack to maintain potential nums[j] values (the peak values)

2. Traverse the array backwards using nums[::-1]:

   • We process each element x from right to left

3. For each element x, check if we've found a 132 pattern:

   • If x < vk, we return True immediately
   • Why? Because x is our nums[i], and we already know vk is a valid nums[k] that has a corresponding nums[j] > nums[k] to its right

4. Update potential nums[k] values:

   • While the stack is not empty and stk[-1] < x:
     • Pop elements from the stack
     • Update vk to the popped value
   • This step identifies that x can be a nums[j] (peak), and all popped elements can be potential nums[k] values for this peak
   • We keep the maximum such value in vk

5. Maintain the stack:

   • Append x to the stack
   • The stack maintains elements in non-increasing order (larger or equal elements on top)

6. Return result:

   • If we complete the traversal without finding a pattern, return False

Example walkthrough with [3, 1, 4, 2]:

• Start: vk = -inf, stk = []
• Process 2: 2 > -inf, no elements to pop, stk = [2]
• Process 4: 4 > -inf, pop 2 (since 2 < 4), vk = 2, stk = [4]
• Process 1: 1 < 2 (our vk), return True!

The algorithm efficiently finds the 132 pattern in O(n) time and O(n) space complexity.

Example Walkthrough

Let's trace through the algorithm with the array [6, 12, 3, 4, 6, 11, 20].

Initial Setup:

• vk = -inf (tracks the maximum valid middle value "2" in 132 pattern)
• stk = [] (stack for potential peak values "3")
• We'll traverse backwards: [20, 11, 6, 4, 3, 12, 6]

Step-by-step traversal:

Process 20 (index 6):

• Check: Is 20 < -inf? No
• Stack is empty, nothing to pop
• Push 20 onto stack: stk = [20]
• vk = -inf

Process 11 (index 5):

• Check: Is 11 < -inf? No
• Is stk[-1]=20 < 11? No, don't pop
• Push 11 onto stack: stk = [20, 11]
• vk = -inf

Process 6 (index 4):

• Check: Is 6 < -inf? No
• Is stk[-1]=11 < 6? No, don't pop
• Push 6 onto stack: stk = [20, 11, 6]
• vk = -inf

Process 4 (index 3):

• Check: Is 4 < -inf? No
• Is stk[-1]=6 < 4? No, don't pop
• Push 4 onto stack: stk = [20, 11, 6, 4]
• vk = -inf

Process 3 (index 2):

• Check: Is 3 < -inf? No
• Is stk[-1]=4 < 3? No, don't pop
• Push 3 onto stack: stk = [20, 11, 6, 4, 3]
• vk = -inf

Process 12 (index 1):

• Check: Is 12 < -inf? No
• Is stk[-1]=3 < 12? Yes! Pop 3, set vk = 3
• Is stk[-1]=4 < 12? Yes! Pop 4, set vk = 4
• Is stk[-1]=6 < 12? Yes! Pop 6, set vk = 6
• Is stk[-1]=11 < 12? Yes! Pop 11, set vk = 11
• Is stk[-1]=20 < 12? No, stop popping
• Push 12 onto stack: stk = [20, 12]
• Now vk = 11 (this represents a valid middle value with 12 as its peak)

Process 6 (index 0):

• Check: Is 6 < 11? YES!
• Return True

Pattern found:

• nums[0] = 6 (the "1" - smallest)
• nums[1] = 12 (the "3" - largest/peak)
• nums[5] = 11 (the "2" - middle)
• The pattern is: 6 < 11 < 12 with indices 0 < 1 < 5 ✓

The algorithm correctly identifies that when we process element 6, it's smaller than our tracked middle value (vk = 11). Since vk was set when we processed 12 as a peak, we know there exists a valid 132 pattern.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm iterates through the array once in reverse order using nums[::-1], which takes O(n) time to create the reversed view. Then, for each element in the reversed array:

• The comparison x < vk takes O(1) time
• The while loop might pop elements from the stack, but each element can be pushed and popped at most once throughout the entire execution
• The append operation takes O(1) amortized time

Since each element is processed at most twice (once when pushed, once when popped), the total time complexity is O(n).

Space Complexity: O(n) in the worst case.

The space is used for:

• The stack stk which can contain at most n elements when all elements are in increasing order (when traversed in reverse)
• The reversed array slice nums[::-1] creates a new list that requires O(n) additional space
• The variable vk uses O(1) space

Therefore, the overall space complexity is O(n).

Common Pitfalls

1. Incorrect Initialization of max_k_value

A common mistake is initializing max_k_value to 0 or some arbitrary number instead of negative infinity. This can cause false positives when the array contains negative numbers.

Incorrect:

max_k_value = 0  # Wrong! Will fail for arrays like [-2, 1, -2]

Correct:

max_k_value = float('-inf')  # Ensures no valid comparison until we have a real nums[k]

2. Traversing in Forward Direction

Some might attempt to traverse the array from left to right, which makes the problem significantly more complex and requires tracking multiple variables.

Incorrect Approach:

# Trying to find pattern while going forward
for i in range(len(nums)):
    # Complex logic needed to track all three elements simultaneously

Correct Approach:

for current_num in reversed(nums):
    # Backwards traversal simplifies the logic

3. Misunderstanding the Stack's Purpose

The stack doesn't store all previously seen elements; it maintains a monotonic decreasing sequence of potential nums[j] values. A common error is not properly maintaining this invariant.

Incorrect:

# Just pushing everything to stack without maintaining order
stack.append(current_num)  # Without the popping logic

Correct:

while stack and stack[-1] < current_num:
    max_k_value = stack.pop()
stack.append(current_num)

4. Wrong Comparison Order

When checking for the pattern, using <= instead of < or comparing with the wrong variable.

Incorrect:

if current_num <= max_k_value:  # Wrong! We need strict inequality
    return True

Correct:

if current_num < max_k_value:  # Strict inequality for valid 132 pattern
    return True

5. Not Understanding What max_k_value Represents

max_k_value is not just any popped value—it's specifically the maximum valid nums[k] that has a corresponding nums[j] to its right (in the original array). Updating it incorrectly can miss valid patterns.

Incorrect:

while stack and stack[-1] < current_num:
    stack.pop()  # Forgetting to update max_k_value

Correct:

while stack and stack[-1] < current_num:
    max_k_value = stack.pop()  # Must capture the popped value

Solution to Avoid These Pitfalls:

1. Always use float('-inf') for initialization when dealing with comparison-based algorithms
2. Carefully trace through the algorithm with small examples to understand the role of each variable
3. Remember that the backwards traversal means we're building the pattern from right to left
4. Maintain clear variable names that reflect their purpose in the 132 pattern
5. Test with edge cases including negative numbers, duplicates, and arrays of length less than 3