LeetCode 456: 132 Pattern

Problem Restatement

We are given an integer array nums.

We need to determine whether there exists a subsequence of three elements:

nums[i], nums[j], nums[k]

such that:

i < j < k

and:

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

This is called a 132 pattern.

The order of indices is 1 -> 3 -> 2.

The values must look like:

small < middle < large

but they appear in the array as:

small, large, middle

The official statement defines a 132 pattern exactly as a subsequence nums[i], nums[j], nums[k] with i < j < k and nums[i] < nums[k] < nums[j].

Input and Output

Function shape:

def find132pattern(nums: list[int]) -> bool:
    ...

Examples

Example 1:

nums = [1, 2, 3, 4]

The numbers are increasing.

There is no way to choose i < j < k such that the third chosen value lies between the first and second chosen values.

Answer:

False

Example 2:

nums = [3, 1, 4, 2]

Choose:

nums[1] = 1
nums[2] = 4
nums[3] = 2

The indices satisfy:

1 < 2 < 3

The values satisfy:

1 < 2 < 4

So the array contains a 132 pattern.

Answer:

True

Example 3:

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

One valid pattern is:

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

The values satisfy:

-1 < 2 < 3

Answer:

True

First Thought: Brute Force

The most direct solution is to check every triplet.

class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] < nums[k] < nums[j]:
                        return True

        return False

This is correct because it checks every possible choice of i, j, and k.

Problem With Brute Force

The brute force solution has three nested loops.

If n = len(nums), the time complexity is:

O(n^3)

This is too slow for large inputs.

We need to avoid testing every triplet directly.

Key Insight

The pattern is:

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

Think of the three values as:

The hard part is preserving the index order:

i < j < k

A clean way is to scan from right to left.

When scanning from right to left, we can maintain information about values to the right of the current index.

The algorithm keeps:

third

where third means the best candidate for nums[k], the 2 in the 132 pattern.

It also keeps a decreasing stack of possible nums[j] values, the 3 in the pattern.

If we later find a number smaller than third, then we have:

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

and the index order is correct because nums[i] is to the left of both values that created third.

Algorithm

Initialize:

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

Scan nums from right to left.

For each number x:

1. If x < third, return True.

   This means x can be the 1, and third can be the 2.

2. While the stack is not empty and the top of the stack is smaller than x, pop it.

   Each popped value can be a valid 2, because it is smaller than x.

3. Update third to the popped value.

4. Push x onto the stack as a possible future 3.

If the loop finishes, return False.

Walkthrough

Use:

nums = [3, 1, 4, 2]

Start:

third = -inf
stack = []

Scan from right to left.

First, x = 2.

There is no smaller stack value to pop.

Push 2.

third = -inf
stack = [2]

Next, x = 4.

The stack top 2 is smaller than 4, so pop it.

Now 2 becomes a candidate for the 2 in the 132 pattern:

third = 2
stack = []

Push 4 as a possible 3.

third = 2
stack = [4]

Next, x = 1.

Now:

x < third
1 < 2

So we found:

1 < 2 < 4

The pattern exists.

Return:

True

Correctness

The stack stores possible nums[j] values from the right side of the current scan position.

When processing a value x, every stack value smaller than x can serve as nums[k] with x serving as nums[j], because that popped value appears to the right of x and is smaller than x.

The variable third stores the largest popped value seen so far. This gives the strongest possible candidate for nums[k], because a larger nums[k] makes it easier to find a smaller nums[i].

If at some later point we find a value x such that:

x < third

then x appears to the left of the nums[j] and nums[k] pair that created third.

So the indices satisfy:

i < j < k

and the values satisfy:

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

Therefore, a valid 132 pattern exists.

If the algorithm never finds x < third, then no value to the left can complete any valid nums[j], nums[k] pair. Thus no 132 pattern exists.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        third = float("-inf")
        stack = []

        for x in reversed(nums):
            if x < third:
                return True

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

            stack.append(x)

        return False

Code Explanation

We use:

third = float("-inf")

This stores the best known candidate for nums[k], the middle value in the 132 pattern.

At the start, we have not found any candidate, so it is negative infinity.

The stack stores possible nums[j] values:

stack = []

Then we scan from right to left:

for x in reversed(nums):

If:

if x < third:

then x can be nums[i], and third can be nums[k].

Since third was created by popping a value below some larger nums[j], we already know there is a valid nums[j] to complete the pattern.

The loop:

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

means that every smaller value to the right of x can become the 2 in the pattern, while x becomes the 3.

Finally:

stack.append(x)

adds x as a possible future 3.

If no pattern is found:

return False

Testing

def run_tests():
    s = Solution()

    assert s.find132pattern([1, 2, 3, 4]) is False
    assert s.find132pattern([3, 1, 4, 2]) is True
    assert s.find132pattern([-1, 3, 2, 0]) is True
    assert s.find132pattern([1, 0, 1, -4, -3]) is False
    assert s.find132pattern([3, 5, 0, 3, 4]) is True
    assert s.find132pattern([1, 2]) is False
    assert s.find132pattern([1, 4, 0, -1, -2, -3, -1, -2]) is True

    print("all tests passed")

run_tests()

Test meaning: