LeetCode 456 - 132 Pattern

LeetCode Problem 456

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Stack, Monotonic Stack, Ordered Set

Solution

Problem Understanding

The problem asks us to determine whether an array contains a specific ordering pattern called a "132 pattern".

A valid 132 pattern consists of three indices i, j, and k such that:

• i < j < k
• nums[i] < nums[k] < nums[j]

The name "132" comes from the relative ordering of the values:

• nums[i] is the smallest value, representing 1
• nums[j] is the largest value, representing 3
• nums[k] lies between them, representing 2

The indices must appear in increasing order, but the values follow the 1 < 2 < 3 relationship with the middle value appearing last.

For example, in the array [3,1,4,2]:

• 1 is the smallest value
• 4 is the largest value
• 2 lies between them

The indices are ordered correctly, so [1,4,2] forms a valid 132 pattern.

The input is an integer array nums with length up to 2 * 10^5. This constraint is extremely important because it immediately rules out expensive cubic or even quadratic solutions in practice. An O(n^3) brute force solution would require checking billions of combinations for large inputs, which is far too slow.

The values themselves can range from -10^9 to 10^9, which means:

• We cannot rely on counting sort or bounded-value techniques
• Comparisons are the only meaningful operations
• Negative numbers and duplicates must be handled correctly

Several edge cases are important:

• Arrays with fewer than three elements can never contain a 132 pattern
• Strict inequalities matter, equal values do not qualify
• Monotonically increasing arrays cannot contain the pattern
• Monotonically decreasing arrays also cannot contain the pattern
• Duplicate values can easily break naive logic if strict comparisons are not handled carefully

The challenge is to efficiently track candidate values for the three positions while preserving index ordering.

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet (i, j, k).

We iterate through all combinations where i < j < k and check whether:

nums[i] < nums[k] < nums[j]

If any triplet satisfies the condition, we return true. Otherwise, after exhausting all possibilities, we return false.

This approach is correct because it explicitly checks every valid subsequence of length three. If a 132 pattern exists, we are guaranteed to find it.

However, the time complexity is extremely poor. There are O(n^3) triplets in the worst case, which becomes infeasible for n = 2 * 10^5.

Even a partially optimized double-loop approach still struggles because we need a fast way to determine whether a valid middle value exists between two elements.

Key Insight for the Optimal Solution

The main challenge is efficiently finding:

nums[i] < nums[k] < nums[j]

while preserving index ordering.

A very important observation is that the pattern can be searched from right to left.

Suppose we fix nums[j] as the potential largest element in the pattern. Then we want:

• a smaller value to its left, nums[i]
• a middle value to its right, nums[k]

The optimal solution uses a monotonic decreasing stack while scanning from right to left.

The stack stores candidate values for the 3 element, meaning potential nums[j] values.

At the same time, we maintain another variable representing the best candidate for the 2 element, meaning nums[k].

The reasoning works like this:

• While scanning from right to left, every element naturally has access to everything to its right
• If we encounter a value smaller than the current nums[k], we have found:

nums[i] < nums[k]

• Since nums[k] was previously extracted from a larger stack element, we already know:

nums[k] < nums[j]

This creates the full pattern.

The monotonic stack allows us to maintain these relationships in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every triplet explicitly
Optimal	O(n)	O(n)	Uses a decreasing monotonic stack scanned from right to left

Algorithm Walkthrough

Optimal Monotonic Stack Algorithm

1. Initialize an empty stack.

The stack will store candidate values for the 3 element in decreasing order. 2. Initialize a variable called second.

This variable represents the best candidate for the 2 element in the 132 pattern. Initially, set it to negative infinity because no candidate has been found yet. 3. Traverse the array from right to left.

Scanning from right to left is critical because the pattern requires:

i < j < k

Looking backward allows us to treat everything to the right as potential future elements. 4. For each number num, first check whether:

num < second

If this is true, we found:

nums[i] = num
nums[k] = second

Since second was previously popped from the stack by a larger element, we also know:

second < nums[j]

Therefore, the complete 132 pattern exists. 5. While the stack is not empty and:

num > stack[-1]

pop elements from the stack.

Every popped value becomes a candidate for second.

This works because:

• the current num is larger
• the popped value is smaller
• therefore:

popped < num

which matches the required relationship:

nums[k] < nums[j]

6. Push the current number onto the stack.

It may serve as a future nums[j] candidate for elements farther left. 7. If the traversal finishes without finding a valid pattern, return false.

Why it works

The stack maintains decreasing values, ensuring that whenever a value is popped, we have found a larger value to its left.

The variable second always stores a valid candidate for the middle value nums[k] such that some larger element already exists to its left in traversal order.

When we later encounter a value smaller than second, we automatically satisfy:

nums[i] < nums[k] < nums[j]

with correct index ordering guaranteed by the right-to-left traversal.

Python Solution

from typing import List

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        second = float('-inf')

        for num in reversed(nums):
            if num < second:
                return True

            while stack and num > stack[-1]:
                second = stack.pop()

            stack.append(num)

        return False

The implementation follows the exact logic described in the algorithm walkthrough.

The stack stores decreasing values representing candidate nums[j] elements. Because the stack is decreasing, smaller values remain near the top and can be popped when a larger value appears.

The variable second tracks the best candidate for nums[k]. Every time we pop from the stack, we know the popped value is smaller than the current number, which means it can legally serve as the middle element of a 132 pattern.

The traversal uses reversed(nums) so that every element naturally sees all values to its right.

The condition:

if num < second:

is the key detection step. At that moment:

• num acts as nums[i]
• second acts as nums[k]
• some previously processed larger number acts as nums[j]

Once this happens, the function immediately returns True.

If the loop finishes without success, no valid pattern exists.

Go Solution

func find132pattern(nums []int) bool {
	stack := []int{}
	second := -(1 << 60)

	for i := len(nums) - 1; i >= 0; i-- {
		num := nums[i]

		if num < second {
			return true
		}

		for len(stack) > 0 && num > stack[len(stack)-1] {
			second = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, num)
	}

	return false
}

The Go implementation mirrors the Python solution closely.

Slices are used as stacks. The last element of the slice acts as the top of the stack.

Since Go does not provide negative infinity for integers directly, the implementation initializes second using a very small integer:

second := -(1 << 60)

This safely fits within Go's integer range and behaves like negative infinity for the problem constraints.

The algorithm otherwise remains identical:

• traverse from right to left
• maintain a decreasing stack
• update second when popping
• detect the pattern using num < second

Worked Examples

Example 1

nums = [1,2,3,4]

Expected output:

false

Step	Current num	Stack	second	Action
Start	-	[]	-inf	Initialize
1	4	[]	-inf	Push 4
2	3	[4]	-inf	Push 3
3	2	[4,3]	-inf	Push 2
4	1	[4,3,2]	-inf	Push 1

No element ever satisfies:

num < second

So no 132 pattern exists.

Example 2

nums = [3,1,4,2]

Expected output:

true

Step	Current num	Stack Before	second Before	Action	Stack After	second After
1	2	[]	-inf	Push	[2]	-inf
2	4	[2]	-inf	Pop 2	[]	2
		[]	2	Push 4	[4]	2
3	1	[4]	2	1 < 2, pattern found	-	-

The pattern is:

1 < 2 < 4

which corresponds to [1,4,2].

Example 3

nums = [-1,3,2,0]

Expected output:

true

Step	Current num	Stack Before	second Before	Action	Stack After	second After
1	0	[]	-inf	Push	[0]	-inf
2	2	[0]	-inf	Pop 0	[]	0
		[]	0	Push 2	[2]	0
3	3	[2]	0	Pop 2	[]	2
		[]	2	Push 3	[3]	2
4	-1	[3]	2	-1 < 2, pattern found	-	-

One valid pattern is:

-1 < 2 < 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped at most once
Space	O(n)	The stack may contain up to n elements

The linear runtime comes from the monotonic stack behavior.

Although there is a nested while loop, each element can only be popped once after being pushed once. Therefore, the total number of stack operations across the entire algorithm is proportional to n.

The auxiliary space complexity is O(n) because the stack can grow to contain the entire array in strictly decreasing cases.

Test Cases

from typing import List

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        second = float('-inf')

        for num in reversed(nums):
            if num < second:
                return True

            while stack and num > stack[-1]:
                second = stack.pop()

            stack.append(num)

        return False

sol = Solution()

assert sol.find132pattern([1, 2, 3, 4]) is False  # strictly increasing
assert sol.find132pattern([3, 1, 4, 2]) is True   # standard valid pattern
assert sol.find132pattern([-1, 3, 2, 0]) is True # multiple valid patterns

assert sol.find132pattern([1]) is False           # single element
assert sol.find132pattern([1, 2]) is False        # fewer than 3 elements
assert sol.find132pattern([3, 2, 1]) is False     # strictly decreasing

assert sol.find132pattern([1, 3, 2]) is True      # smallest valid case
assert sol.find132pattern([1, 0, 1, -4, -3]) is False  # tricky negative values

assert sol.find132pattern([3, 5, 0, 3, 4]) is True     # non-adjacent pattern
assert sol.find132pattern([6, 12, 3, 4, 6, 11, 20]) is True  # larger mixed case

assert sol.find132pattern([1, 1, 1, 1]) is False  # duplicates only
assert sol.find132pattern([1, 4, 4, 2]) is True   # duplicates with valid pattern

assert sol.find132pattern([-10**9, 10**9, 0]) is True  # extreme values

Test	Why
[1,2,3,4]	Validates increasing arrays
[3,1,4,2]	Standard example with clear 132 pattern
[-1,3,2,0]	Multiple possible patterns
[1]	Minimum input size
[1,2]	Array too small for pattern
[3,2,1]	Decreasing array case
[1,3,2]	Smallest valid pattern
[1,0,1,-4,-3]	Negative values without pattern
[3,5,0,3,4]	Complex ordering with valid subsequence
[6,12,3,4,6,11,20]	Larger realistic example
[1,1,1,1]	Duplicate values with strict inequality
[1,4,4,2]	Duplicate large values but valid pattern
[-10^9,10^9,0]	Extreme constraint values

Edge Cases

Arrays With Fewer Than Three Elements

A 132 pattern requires exactly three indices:

i < j < k

Therefore, arrays of size 0, 1, or 2 can never contain a valid pattern.

Naive implementations sometimes forget this and accidentally access invalid indices or perform unnecessary work. The stack-based solution handles this naturally because the traversal simply finishes without ever finding a valid relationship.

Duplicate Values

The inequalities in the problem are strict:

nums[i] < nums[k] < nums[j]

Equal values do not count.

For example:

[1,1,1,1]

does not contain a valid pattern even though there are multiple repeated numbers.

This is a common source of bugs if non-strict comparisons like <= are used accidentally. The implementation correctly uses:

num > stack[-1]

and:

num < second

which preserves the strict inequality requirements.

Strictly Increasing or Decreasing Arrays

Arrays like:

[1,2,3,4]

or:

[4,3,2,1]

cannot contain a 132 pattern.

Increasing arrays lack a middle value smaller than the largest element.

Decreasing arrays lack the required ordering relationship entirely.

These cases are important because they stress the monotonic stack structure:

• increasing arrays grow the stack continuously
• decreasing arrays rarely pop from the stack

The algorithm handles both efficiently in linear time.