Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

132 Pattern solution and explanation

MediumArrayBinary SearchMonotonic StackOrdered Set4 min read35.2% acceptanceUpdated 9 Apr 2026
Asked atDoorDashSprinklrAmazonBloombergGoogleMeta
+2 moreGoldman SachsMicrosoft
Practise 132 Pattern
12:02
132 Pattern - Leetcode 456 - PythonNeetCode · 12:02 · 80K viewsWatch on YouTube
9 more videos on this problem
  1. 132 Pattern - Leetcode 456 - PythonNeetCode · 12:02 · 80K views
  2. 132 Pattern | Leetcode 456Pepcoding · 29:50 · 20K views
  3. 132 Pattern | Intuition explained | Brute Force | Better | Optimal | META | AMAZON | Leetcode - 456codestorywithMIK · 31:38 · 20K views
  4. 132 Pattern | Leetcode 456 | Stack | Day-7Ayushi Sharma · 25:06 · 12K views
  5. 132 Pattern | Leetcode 456 | Montonic Stacks | Live coding sessionCoding Decoded · 12:28 · 5K views
  6. 132 Pattern | LeetCode 456 | October LeetCode Challenge | Day 23Learn Code Repeat · 14:17 · 2K views
  7. 132 Pattern | Leet code 456 | Theory explained + Python codeSai Anish Malla · 15:39 · 2K views
  8. 132 Pattern - Leetcode 456 - PythonTechError · 8:19 · 1K views
  9. Leetcode 456. 132 Pattern O(N) SolutionElite Code · 8:21 · 1K views
  10. 456. 132 Pattern - LeetCode Python tutorialCode with Carter · 11:24 · 1K views

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

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

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 105
  • -109 <= nums[i] <= 109

Approach overview

Problem Overview: The task is to determine whether an integer array contains a 132 pattern: three indices i < j < k such that nums[i] < nums[k] < nums[j]. You need to check if there exists a subsequence where the first value is the smallest, the second is the largest, and the third falls strictly between them.

Approach 1: Brute Force (O(n³) time, O(1) space)

The straightforward approach checks every possible triple (i, j, k). Use three nested loops: iterate i from the start, j after i, and k after j. For each combination, verify whether nums[i] < nums[k] < nums[j]. The logic is simple and mirrors the exact definition of the pattern. However, the algorithm performs roughly n³ comparisons, which becomes impractical for large arrays. This method mainly serves as a baseline to confirm understanding of the pattern definition before moving to an optimized approach using a array traversal strategy.

Approach 2: Stack Optimization (O(n) time, O(n) space)

The optimal solution uses a decreasing stack while scanning the array from right to left. The key idea is to track potential candidates for the nums[j] and nums[k] values while searching for a smaller nums[i]. Maintain a variable (often called third) that stores the best candidate for nums[k]. While iterating backward, if the current element is smaller than third, a valid 132 pattern exists.

Otherwise, pop elements from the stack while the current value is greater than the stack top. Each popped value becomes a stronger candidate for nums[k] because it lies between a future larger element and a smaller prefix element. After popping, push the current value onto the stack to maintain a decreasing order. This structure behaves like a monotonic stack, ensuring every element is pushed and popped at most once, giving linear time complexity.

This method works because scanning from the right naturally preserves valid ordering for j and k. The stack keeps possible nums[j] values, while the third variable tracks the largest valid nums[k] discovered so far. The moment you encounter a smaller number to the left, the pattern is confirmed.

Recommended for interviews: Interviewers typically expect the stack-based O(n) approach. The brute force method shows that you understand the pattern definition and constraints, but the optimized solution demonstrates familiarity with monotonic stack techniques and efficient array scanning strategies often used in advanced array problems.

Approach 1: Approach 1: Brute Force

This approach checks all possible triples (i, j, k) to determine if they form a 132 pattern. While straightforward, its complexity can be high for larger arrays due to the triple nested loop structure.

def find132pattern(nums):
    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
public class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[k] && nums[k] < nums[j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
#include <vector>
bool find132pattern(std::vector<int>& nums) {
    for (int i = 0; i < nums.size() - 2; ++i) {
        for (int j = i + 1; j < nums.size() - 1; ++j) {
            for (int k = j + 1; k < nums.size(); ++k) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }
    return false;
}
function find132pattern(nums) {
    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }
    return false;
}
#include <stdbool.h>
int has132Pattern(int* nums, int numsSize) {
    for (int i = 0; i < numsSize - 2; ++i) {
        for (int j = i + 1; j < numsSize - 1; ++j) {
            for (int k = j + 1; k < numsSize; ++k) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }
    return false;
}
public class Solution {
    public bool Find132pattern(int[] nums) {
        int n = nums.Length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[k] && nums[k] < nums[j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

This Python solution examines all potential triplets via triple nested loops and checks if they fulfill the 132 pattern.

Complexity

Time complexity: O(n^3).
Space complexity: O(1).

Try this approach in the editor

Approach 2: Approach 2: Stack Optimization

This approach uses a clever stack-based strategy by scanning the array from right to left. It keeps track of potential '2' and '3' candidates using a stack and a variable, optimizing the search for the '132' pattern.

def find132pattern(nums):
    stack = []
    num3 = float('-inf')
    for num in reversed(nums):
        if num < num3:
            return True
        while stack and num > stack[-1]:
            num3 = stack.pop()
        stack.append(num)
    return False
import java.util.Stack;

public class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int num3 = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] < num3) {
                return true;
            }
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                num3 = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }
}
#include <vector>
#include <stack>
#include <limits.h>

bool find132pattern(std::vector<int>& nums) {
    std::stack<int> stk;
    int num3 = INT_MIN;
    for (int i = nums.size() - 1; i >= 0; --i) {
        if (nums[i] < num3) {
            return true;
        }
        while (!stk.empty() && nums[i] > stk.top()) {
            num3 = stk.top();
            stk.pop();
        }
        stk.push(nums[i]);
    }
    return false;
}
function find132pattern(nums) {
    let stack = [];
    let num3 = -Infinity;
    for (let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] < num3) {
            return true;
        }
        while (stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            num3 = stack.pop();
        }
        stack.push(nums[i]);
    }
    return false;
}
#include <stdbool.h>
#include <limits.h>

int has132PatternStack(int* nums, int numsSize) {
    int stack[numsSize];
    int top = -1;
    int num3 = INT_MIN;
    
    for (int i = numsSize - 1; i >= 0; i--) {
        if (nums[i] < num3) {
            return true;
        }
        while (top >= 0 && nums[i] > stack[top]) {
            num3 = stack[top--];
        }
        stack[++top] = nums[i];
    }
    return false;
}
using System;
using System.Collections.Generic;

public class Solution {
    public bool Find132pattern(int[] nums) {
        Stack<int> stack = new Stack<int>();
        int num3 = int.MinValue;
        for (int i = nums.Length - 1; i >= 0; --i) {
            if (nums[i] < num3) {
                return true;
            }
            while (stack.Count > 0 && nums[i] > stack.Peek()) {
                num3 = stack.Pop();
            }
            stack.Push(nums[i]);
        }
        return false;
    }
}

Iterating over the reversed list, the stack is used to check the '132' pattern. The 'num3' variable tracks the most recent valid '2'.

Complexity

Time complexity: O(n).
Space complexity: O(n).

Try this approach in the editor

Approach 3: Default Approach

function find132pattern(nums: number[]): boolean {
    let vk = -Infinity;
    const stk: number[] = [];
    for (let i = nums.length - 1; i >= 0; --i) {
        if (nums[i] < vk) {
            return true;
        }
        while (stk.length && stk[stk.length - 1] < nums[i]) {
            vk = stk.pop()!;
        }
        stk.push(nums[i]);
    }
    return false;
}
func find132pattern(nums []int) bool {
	vk := -(1 << 30)
	stk := []int{}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] < vk {
			return true
		}
		for len(stk) > 0 && stk[len(stk)-1] < nums[i] {
			vk = stk[len(stk)-1]
			stk = stk[:len(stk)-1]
		}
		stk = append(stk, nums[i])
	}
	return false
}
impl Solution {
    pub fn find132pattern(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut vk = i32::MIN;
        let mut stk = vec![];
        for i in (0..n).rev() {
            if nums[i] < vk {
                return true;
            }
            while !stk.is_empty() && stk.last().unwrap() < &nums[i] {
                vk = stk.pop().unwrap();
            }
            stk.push(nums[i]);
        }
        false
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Brute Force

Time complexity: O(n^3).
Space complexity: O(1).

Approach 2: Stack Optimization

Time complexity: O(n).
Space complexity: O(n).

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple LoopO(n³)O(1)Useful for understanding the definition of the 132 pattern or verifying small inputs.
Monotonic Stack OptimizationO(n)O(n)Best choice for interviews and large arrays; scans once using a decreasing stack.

Frequently asked questions

Is 132 Pattern easy or hard?

132 Pattern is generally rated Medium difficulty. The brute force idea is straightforward, but discovering the optimal O(n) monotonic stack solution requires deeper understanding of stack patterns and reverse traversal techniques.

132 Pattern Python/Java solution

Most implementations use a stack and a variable storing the potential 'ak' value. The algorithm iterates from right to left, pops smaller stack elements to update the middle value, and checks if the current number forms a valid ai < ak relationship. The same logic works across Python, Java, C++, and other languages.

How to solve 132 Pattern in O(n)?

Traverse the array from right to left while maintaining a decreasing stack. Use a variable to track the best candidate for the middle value (ak). If the current element becomes smaller than this stored value, a valid 132 pattern exists. Each element is processed once, resulting in O(n) time.

What is the best approach for 132 Pattern?

The most efficient approach uses a monotonic stack and scans the array from right to left. It tracks possible 'aj' values in a decreasing stack and stores the best candidate for 'ak' in a variable. This method detects a valid ai < ak < aj pattern in O(n) time with O(n) extra space.

Is 132 Pattern asked at Google/Amazon/Meta?

132 Pattern has appeared in interviews at major tech companies including Amazon, Google, and Meta. It tests knowledge of monotonic stacks, pattern detection in arrays, and the ability to optimize brute-force solutions into linear-time algorithms.

What data structure is used in 132 Pattern?

The optimal solution relies on a stack, specifically a monotonic decreasing stack. It helps maintain candidate values for the 'aj' element while tracking a valid 'ak' candidate during the backward scan of the array.

What is the time complexity of 132 Pattern?

The optimal stack-based solution runs in O(n) time because each element is pushed to and popped from the stack at most once. The brute force approach checks every triple (i, j, k) and requires O(n^3) time, which is impractical for large inputs.

Comments

Now write it yourselfClose this page and solve 132 Pattern in the editor, without looking.
Practise 132 Pattern