LeetCode 456: 132 Pattern Solution in Python – A Step-by-Step Guide

What Is LeetCode 456: 132 Pattern?

In LeetCode 456: 132 Pattern, you’re given an integer array nums, and your task is to determine if there exists a subsequence of three indices (i, j, k) where i < j < k and nums[i] < nums[k] < nums[j]—the “132 pattern.” For example, in [3, 1, 4, 2], the subsequence 1, 4, 2 fits (1 < 2 < 4), so you return True. It’s like finding a trio in the array where the first number dips low, the second peaks high, and the third lands in between.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: bool—True if a 132 pattern exists, False otherwise.
• Rules:
• Find i < j < k with nums[i] < nums[k] < nums[j].
• Subsequence, not necessarily contiguous.

Constraints

• n == nums.length.
• 1 <= n <= 2 * 10^5.
• -10^9 <= nums[i] <= 10^9.

Examples to Get Us Started

• Input: nums = [1,2,3,4]
• Output: False (No dip-peak-middle pattern).
• Input: nums = [3,1,4,2]
• Output: True (1 < 2 < 4 at indices 1, 2, 3).
• Input: nums = [-1,3,2,0]
• Output: True (-1 < 0 < 3).

Understanding the Problem: Hunting the Pattern

To solve LeetCode 456: 132 Pattern in Python, we need to find three indices i < j < k where nums[i] < nums[k] < nums[j]. A naive check of all triplets is O(n³)—too slow for n = 2 * 10^5. The 132 pattern’s structure suggests a smarter approach: track minimums and peaks efficiently. We’ll explore:

• Best Solution (Stack-Based with Minimum Tracking): O(n) time, O(n) space—fast and brilliant.
• Alternative Solution (Brute Force): O(n³) time, O(1) space—simple but impractical.

Let’s dive into the stack-based solution—it’s the treasure map we need.

Best Solution: Stack-Based Approach with Minimum Tracking

Why This Is the Best Solution

The stack-based approach with minimum tracking is the top pick because it’s O(n) time and O(n) space, efficiently finding the 132 pattern in one pass. It uses a stack to track potential “3” values (peaks) and a minimum array to ensure a smaller “1” exists, then checks for a “2” that fits. It’s like scanning the array with a metal detector, keeping peaks in reserve and pinging when the pattern clicks—ingenious and swift!

How It Works

Here’s the strategy:

• Step 1: Compute a left_min array where left_min[i] is the minimum value up to i (for “1”).
• Step 2: Iterate from right to left with a stack:
• Pop stack if current num ≥ stack top (keep decreasing order).
• If num < stack top, check if num > left_min[i] (potential 132).
• Push num onto stack.
• Step 3: Return True if found, False otherwise.
• Why It Works:
• Left_min ensures a smaller “1” before i.
• Stack keeps potential “3”s, num as “2” fits between.

Step-by-Step Example

Example: nums = [3,1,4,2]

• Left Min: [3, 1, 1, 1] (min up to each index).
• From Right:
• i=3 (2): stack = [2].
• i=2 (4): 4 > 2, pop 2, stack = [], 4 > left_min[2]=1, no stack to check, push 4, stack = [4].
• i=1 (1): 1 < 4, 1 > left_min[1]=1 (false), push 1, stack = [4, 1].
• i=0 (3): 3 < 4, 3 > left_min[0]=3 (false), pop 1 (3 > 1), stack = [4], check 1 < 3 < 4, True.
• Result: True (1, 4, 2).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False

        # Step 1: Compute left minimums
        left_min = [0] * len(nums)
        left_min[0] = nums[0]
        for i in range(1, len(nums)):
            left_min[i] = min(left_min[i-1], nums[i])

        # Step 2: Scan right to left with stack
        stack = []
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] > left_min[i]:  # Potential "2" > "1"
                while stack and stack[-1] <= nums[i]:
                    stack.pop()  # Keep stack in decreasing order
                if stack and stack[-1] > nums[i]:  # "3" > "2"
                    return True  # Found 132: left_min[i] < nums[i] < stack[-1]
                stack.append(nums[i])

        return False

• Line 3-4: Early exit for small arrays.
• Line 7-9: Build left_min (e.g., [3,1,1,1]).
• Line 12-18: Right-to-left scan:
• If nums[i] > left_min[i], possible “2” > “1”.
• Pop stack until top > nums[i] (keep decreasing).
• If stack top > nums[i], found “3” > “2” > “1”, return True.
• Push nums[i].
• Line 20: Return False if no pattern.
• Time Complexity: O(n)—single pass with stack ops.
• Space Complexity: O(n)—stack and left_min.

It’s like a pattern-sniffing treasure detector!

Alternative Solution: Brute Force with Three Nested Loops

Why an Alternative Approach?

The brute force method checks all triplets—O(n³) time, O(1) space—looking for i < j < k with nums[i] < nums[k] < nums[j]. It’s slow but crystal-clear, like combing the array inch-by-inch for the pattern. Good for small n or building intuition!

How It Works

• Step 1: Three nested loops for i, j, k.
• Step 2: Check if nums[i] < nums[k] < nums[j].
• Step 3: Return True if found, False otherwise.

Step-by-Step Example

Example: nums = [3,1,4,2]

• Triplets:
• (0,1,2): 3,1,4 → 3 < 4 < 1 (false).
• (0,1,3): 3,1,2 → 3 < 2 < 1 (false).
• (0,2,3): 3,4,2 → 3 < 2 < 4 (false).
• (1,2,3): 1,4,2 → 1 < 2 < 4 (true).
• Result: True.

Code for Brute Force

Copy codeclass Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False

        # Check all triplets
        for i in range(len(nums) - 2):
            for j in range(i + 1, len(nums) - 1):
                for k in range(j + 1, len(nums)):
                    if nums[i] < nums[k] < nums[j]:
                        return True
        return False

• Line 3-4: Early exit.
• Line 7-10: Triple loop, check 132 condition.
• Time Complexity: O(n³)—all triplets.
• Space Complexity: O(1)—no extra space.

It’s a slow pattern comb!

Comparing the Two Solutions

• Stack-Based (Best):
• Pros: O(n), fast, scalable.
• Cons: O(n) space, trickier.
• Brute Force (Alternative):
• Pros: O(n³), simple, O(1) space.
• Cons: Impractical for large n.

Stack wins for efficiency.

Edge Cases and More Examples

• Input: [1,2] → False.
• Input: [1,2,3] → False.
• Input: [3,5,0,3,4] → True (0,3,4).

Stack handles all smoothly.

Complexity Recap

• Stack-Based: Time O(n), Space O(n).
• Brute Force: Time O(n³), Space O(1).

Stack’s the champ.

Key Takeaways

• Stack: Track peaks smartly.
• Brute Force: Check every trio.
• Python Tip: Stacks find patterns—see [Python Basics](/python/basics).

Final Thoughts: Unearth That Pattern

LeetCode 456: 132 Pattern in Python is a pattern-hunting adventure. The stack-based solution is your fast treasure map, while brute force is a slow shovel. Want more pattern fun? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 503: Next Greater Element II. Ready to spot some 132s? Head to Solve LeetCode 456 on LeetCode and dig in today—your coding skills are pattern-perfect!