132 Pattern

Medium
384.

132 Pattern

132 Pattern is a medium coding problem on arrays, binary search and stack, asked in Amazon, Google, Bloomberg and Sprinklr interviews.

A 132 pattern is a subsequence nums[i], nums[j], nums[k] with i < j < k and nums[i] < nums[k] < nums[j].

Given an integer array nums, return true if such a pattern exists.

Example 1

Input
nums = [1,2,3,4]
Output
false
Explanation
The array is increasing.

Example 2

Input
nums = [3,1,4,2]
Output
true
Explanation
1, 4, 2 is a 132 pattern.

Example 3

Input
nums = [-1,3,2,0]
Output
true

Constraints

  • 1 <= nums.length <= 40
  • -1000000000 <= nums[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

132 Pattern — Solution in Python, Java & C++

132 Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

132 Pattern is a medium coding problem on arrays, binary search and stack, asked in Amazon, Google, Bloomberg and Sprinklr interviews.

Problem statement

A 132 pattern is a subsequence nums[i], nums[j], nums[k] with i < j < k and nums[i] < nums[k] < nums[j].

Given an integer array nums, return true if such a pattern exists.

Example 1

Input: nums = [1,2,3,4]
Output: false
Explanation: The array is increasing.

Example 2

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

Example 3

Input: nums = [-1,3,2,0]
Output: true

Constraints

  • 1 <= nums.length <= 40
  • -1000000000 <= nums[i] <= 1000000000

Hints for 132 Pattern

  1. Hint 1

    Scan from the right and maintain a decreasing stack of candidates for the 3.

  2. Hint 2

    Whenever a value pops elements off the stack, those popped values are valid candidates for the 2 — keep the largest one seen.

  3. Hint 3

    If the current element is smaller than that best 2, you have found the 1 and the pattern exists.

How to solve 132 Pattern

Scan from the right with a decreasing stack of candidates for the 3; values popped by a larger element are candidates for the 2 — keep the largest — and any element smaller than that is the 1.

Approach

  1. For x from right to left: if x < third, return true.
  2. While the stack top is less than x, pop it into third.
  3. Push x.

Why it works

third is always the largest value that has a larger element to its right (the 3 that popped it), so the first x below third completes a 1 < 2 < 3 pattern with i < j < k.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Initialise third to -∞ so nothing matches before a real 2 exists.

Reference solution

Python

def find132pattern(nums) -> bool:
    stack = []
    third = float("-inf")
    for x in reversed(nums):
        if x < third:
            return True
        while stack and stack[-1] < x:
            third = stack.pop()
        stack.append(x)
    return False

Java

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

C++

bool find132pattern(vector<int>& nums) {
    vector<int> stack;
    bool hasThird = false;
    int third = 0;
    for (int i = (int) nums.size() - 1; i >= 0; i--) {
        if (hasThird && nums[i] < third) return true;
        while (!stack.empty() && stack.back() < nums[i]) {
            third = stack.back();
            stack.pop_back();
            hasThird = true;
        }
        stack.push_back(nums[i]);
    }
    return false;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search