Problem Statement

• 456. 132 Pattern

Given an array of n integers nums, 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 there is a 132 pattern in nums, otherwise, return false.

Example:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

• n == nums.length
• 1 ≤ n ≤ 2 × 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹

Algorithm Overview

The key insight is to find three indices i < j < k where nums[i] < nums[k] < nums[j]. We can approach this by fixing different elements and searching for the pattern.

Optimal Approach: Stack + Monotonic Stack

Strategy: Traverse from right to left, maintaining a stack of potential "middle" values (nums[k]) and tracking the largest valid "middle" value we've seen.

Core Idea:

1. Fix nums[j] as we traverse from right to left
2. Use stack to maintain potential nums[k] values in decreasing order
3. Track the largest valid nums[k] that is smaller than current nums[j]
4. Check if current element can be nums[i] (smaller than the tracked nums[k])

Steps:

1. Traverse the array from right to left
2. For each element (potential nums[j]):
   • While stack is not empty and top element ≤ current element, pop and update third (potential nums[k])
   • If we have a valid third and current element < third, return true (found 132 pattern)
   • Push current element to stack
3. Return false if no pattern found

Implementation:

public boolean find132pattern(int[] nums) {
    if (nums.length < 3) return false;

    Stack<Integer> stack = new Stack<>();
    int third = Integer.MIN_VALUE; // This will be our nums[k]

    // Traverse from right to left
    for (int i = nums.length - 1; i >= 0; i--) {
        // If current number is smaller than third, we found 132 pattern
        if (nums[i] < third) return true;

        // While stack top is smaller than current number,
        // pop and update third (these could be our nums[k])
        while (!stack.isEmpty() && stack.peek() < nums[i]) {
            third = stack.pop();
        }

        // Push current number (potential nums[j])
        stack.push(nums[i]);
    }

    return false;
}

Why this works:

• Stack maintains decreasing sequence of potential nums[j] values
• third tracks the largest nums[k] that is smaller than some nums[j] to the right
• When nums[i] < third, we have found nums[i] < nums[k] < nums[j] with proper indices

Tracing example [3,1,4,2]:

1. i=3, nums[3]=2: stack=[2], third=MIN_VALUE
2. i=2, nums[2]=4: 4>2, so pop 2, third=2, stack=[4]
3. i=1, nums[1]=1: 1<2 (third), return true

Alternative O(n²) Approach:

public boolean find132pattern(int[] nums) {
    int n = nums.length;
    if (n < 3) return false;

    // Precompute minimum to the left for each position
    int[] minLeft = new int[n];
    minLeft[0] = nums[0];
    for (int i = 1; i < n; i++) {
        minLeft[i] = Math.min(minLeft[i-1], nums[i]);
    }

    // For each j, find if there exists valid k
    for (int j = 1; j < n - 1; j++) {
        for (int k = j + 1; k < n; k++) {
            if (minLeft[j] < nums[k] && nums[k] < nums[j]) {
                return true;
            }
        }
    }

    return false;
}

Complexity Analysis

Optimal Stack Solution

Time Complexity: O(n)

• Single pass through the array: O(n)
• Each element is pushed and popped from stack at most once: O(n) total
• Overall: O(n)

Space Complexity: O(n)

• Stack can store at most n elements in worst case
• Additional variables use O(1) space

Alternative O(n²) Solution

Time Complexity: O(n²)

• Preprocessing minLeft array: O(n)
• Nested loops: O(n²) in worst case
• Overall: O(n²)

Space Complexity: O(n)

• minLeft array: O(n)
• Additional variables: O(1)

Key Insights:

• Stack approach is optimal because it efficiently maintains the relationship between nums[j] and nums[k]
• Traversing right to left allows us to build up potential nums[k] values as we find larger nums[j] values
• Monotonic stack property ensures we always have the best candidates for the pattern
• The problem demonstrates how stack data structures can optimize pattern detection in arrays