Problem Description

You are given an array of n integers, nums. Your task is to determine whether there exists a subsequence of three integers nums[i], nums[j], and nums[k] such that:

• i < j < k (the indices are in increasing order)
• nums[i] < nums[k] < nums[j]

This pattern is called a 132 pattern: the first number is less than the third, which is less than the second. You must not reuse elements (each index is unique and in order). If such a pattern exists, return true; otherwise, return false.

Constraints:

• n is between 1 and 2 × 10⁵
• Each element of nums is an integer in the range [-10⁹, 10⁹]

Thought Process

At first glance, the problem asks us to check for a specific ordering among any three elements in the array. The most straightforward way is to check all possible triplets, but this quickly becomes infeasible for large arrays due to the cubic time complexity.

We need to find three numbers with indices i < j < k such that nums[i] < nums[k] < nums[j]. The challenge is to efficiently search for this pattern without checking every possible combination.

The key insight is to fix one of the elements (for example, nums[j] as the "2" in the pattern) and try to find suitable "1" and "3" elements before and after it, respectively. We also need to optimize our search by using data structures that allow us to efficiently keep track of the minimum and possible candidates for the "3" value.

As we move from brute-force to optimization, we look for ways to keep track of the minimum value to the left and efficiently search for a valid "3" to the right. Stacks and reverse traversal can help us maintain these efficiently.

Solution Approach

Let's break down the optimized approach step-by-step:

1. Reverse Traversal:
   • We process the array from right to left (from n-1 to 0).
   • This allows us to keep track of possible "3" candidates for the 132 pattern as we go.
2. Using a Stack:
   • We use a stack to store potential "3" values (the middle value in the pattern).
   • We also keep a variable (let's call it third) to remember the largest "3" value we've seen so far that could form a valid pattern.
3. Algorithm Steps:
   • Initialize third as negative infinity (or a very small number).
   • Iterate from the end of the array to the beginning:
   • If nums[i] < third, we have found a valid 132 pattern and can return true.
   • While the stack is not empty and nums[i] > stack[-1]:
     • Pop from the stack and update third to be the value popped.
   • Push nums[i] onto the stack.
4. Why does this work?
   • The stack keeps track of possible "2" values, and third is the "3". If we find a smaller "1", we've found our pattern.
   • By popping from the stack, we ensure that third always represents a value less than the current "2", maintaining the 132 order.

This approach efficiently finds the 132 pattern in linear time using a stack.

Example Walkthrough

Let's use the input nums = [3, 1, 4, 2].

1. Start from the end: i = 3, nums[3] = 2
   • Stack is empty, push 2 onto the stack.
   • third = -∞
2. i = 2, nums[2] = 4
   • 4 > 2 (stack top), so pop 2. Now, third = 2.
   • Stack is empty, push 4 onto the stack.
3. i = 1, nums[1] = 1
   • 1 < third (2), so we've found a 132 pattern: 1, 4, 2.
   • Return true.

The function returns true as expected, since the subsequence [1, 4, 2] forms a 132 pattern.

Time and Space Complexity

• Brute-force approach:
  • Check all possible triplets: O(n³) time.
  • Not feasible for large n (>10⁴).
• Optimized stack approach:
  • Each element is pushed and popped from the stack at most once: O(n) time.
  • The stack and third variable use O(n) space in the worst case.
• Why?
  • Stack operations are amortized O(1), so the total is linear in the size of the input.

Summary

The 132 pattern problem can be solved efficiently by observing that the "3" in the pattern can be tracked using a stack as we process the array from right to left. By maintaining the largest "3" candidate seen so far, and checking for a smaller "1" as we go, we avoid unnecessary checks and achieve linear time complexity. This approach is elegant because it leverages stack properties and reverse traversal to efficiently solve a problem that would otherwise require an impractical brute-force search.

Code Implementation

class Solution:
    def find132pattern(self, nums):
        stack = []
        third = float('-inf')
        for num in reversed(nums):
            if num < third:
                return True
            while stack and num > stack[-1]:
                third = stack.pop()
            stack.append(num)
        return False
      

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> st;
        int third = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] < third)
                return true;
            while (!st.empty() && nums[i] > st.top()) {
                third = st.top();
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};
      

class Solution {
    public boolean find132pattern(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int third = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] < third) return true;
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                third = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }
}
      

var find132pattern = function(nums) {
    let stack = [];
    let third = -Infinity;
    for (let i = nums.length - 1; i >= 0; --i) {
        if (nums[i] < third) return true;
        while (stack.length && nums[i] > stack[stack.length - 1]) {
            third = stack.pop();
        }
        stack.push(nums[i]);
    }
    return false;
};