Problem

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and 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.

Examples

Example 1:

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

Example 2:

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

Example 3:

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].

Solution

Method 1 - Naive

The naive O(n^3) solution is straightforward — just examine every (i, j, k) combination to determine if a 132 pattern exists.

Code

Java
public class Solution {
    public boolean find132pattern(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] < nums[k] && nums[k] < nums[j]) return true;
                }
            }
        }
        return false;
    }
}
Python
 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

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(1)

Method 2 - Using Kind of Two Pointer and precomputed min

If we can keep track of min so far, and then deal with indices j and k such that nums[k] < nums[j] and k > j.

Basically:

Since we are scanning index j from the beginning of the input array nums, we can keep track of the minimum element of the subarray from index 0 up to j - 1 without needing to rescan it. This combines the first two loops of the naive solution into one, achieving an O(n^2) time complexity.

Code

Java
class Solution {
    public boolean find132pattern(int[] nums) {
        for (int j = 0, min = Integer.MAX_VALUE; j < nums.length; j++) {
            min = Math.min(nums[j], min);
            if (min == nums[j]) {
                continue;
            }

            for (int k = nums.length - 1; k > j; k--) {
                if (min < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }

        return false;
    }
}
Python
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        
        min_val = float('inf')
        
        for j in range(n):
            min_val = min(min_val, nums[j])
            if min_val == nums[j]:
                continue
            
            for k in range(n - 1, j, -1):
                if min_val < nums[k] and nums[k] < nums[j]:
                    return True
                
        return False

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 3 - Using Monotonic Decreasing Stack and scanning from left to right 🏆

Building on the previous solution, we are tracking min from 1 .. j-1, what we then see is we 2 numbers nums[j] and nums[k] which are higher than min but are in decreasing order given j and k. Which DS comes to mind? - that is Monotonic decreasing stack.

The key idea is to find the pattern by iterating through the list from right to left while maintaining a possible candidate for nums[k] in the 132 pattern.

Here is the approach:

  1. Iterate through the array from right to left.
  2. Maintain a stack to keep track of possible nums[k] values.
  3. Keep a variable third to store a valid nums[k] candidate that satisfies nums[i] < nums[k].
  4. For each element in the array:
    • Check if the current element is less than third (which implies a valid 132 pattern).
    • Update third each time a new value is popped from the stack.

Code

Java
public class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums == null || nums.length < 3) return false;
        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;
    }
}
Python
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        stack = []
        third = float('-inf')
        
        for x in reversed(nums):
            if x < third:
                return True
            while stack and x > stack[-1]:
                third = stack.pop()
            stack.append(x)
        
        return False

Complexity

  • ⏰ Time complexity: O(n) as each element is pushed and popped from the stack at most once.
  • 🧺 Space complexity: O(n) for the stack.

Method 4 - Using Monotonic Decreasing Stack and scanning from right to Left

Here is the approach:

  • Initialise a stack and a variable thirdElement with Integer.MIN_VALUE.
  • Traverse the array from right to left.
  • Check if the current element is less than thirdElement. If true, then the 132 pattern exists because the stack handles the 32 part of the pattern and the current element completes the sequence. Return true.
  • Otherwise, update the top value of the stack, continuously popping elements until the stack is empty or its top value is greater than the current element.
  • Push the current element onto the stack.
  • If no pattern is found in the array, return false.

This is how the code looks:

Code

Java
class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int third = Integer.MIN_VALUE;
        
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < third) {
                return true;
            }
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                third = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }
}
Python
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        third = float('-inf')
        
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < third:
                return True
            while stack and stack[-1] < nums[i]:
                third = stack.pop()
            stack.append(nums[i])
        
        return False

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)