132 Pattern

🎯

132 Pattern

mediumSTACKAmazonGoogleFacebook

Imagine you are analyzing stock prices to detect a specific pattern that might indicate a profitable trading opportunity - the 132 pattern.

💡 This problem asks to find a specific subsequence pattern in an array, which is tricky because it requires tracking three values with order constraints. Beginners often struggle because it’s not just about sorting or simple scanning; it involves careful state tracking and efficient lookups.

📋

Problem Statement

Given an array of n integers nums, determine if there exists a 132 pattern in the sequence. 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 such a pattern exists, otherwise return false.

1 ≤ n ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1, 2, 3, 4]"

Outputfalse

No 132 pattern exists because the sequence is strictly increasing.

Input"[3, 1, 4, 2]"

Outputtrue

The subsequence [1, 4, 2] forms a 132 pattern: 1 < 2 < 4 with indices i=1, j=2, k=3.

Input"[-1, 3, 2, 0]"

Outputtrue

Multiple 132 patterns exist, e.g., [-1, 3, 2] or [-1, 3, 0].

• Array of length less than 3 → false
• All elements equal → false
• Strictly increasing array → false
• Strictly decreasing array → false

⚠️

Common Mistakes

Confusing the order of indices i, j, k

Incorrect pattern detection or false negatives

✅ Always ensure i < j < k and the value inequalities hold accordingly

Not handling edge cases like arrays with less than 3 elements

Runtime errors or incorrect true returns

✅ Add checks for array length before processing

Using the wrong comparison operators in the pattern condition

Missing valid patterns or detecting invalid ones

✅ Use strict inequalities: nums[i] < nums[k] < nums[j]

Pushing elements onto the stack without popping smaller elements in the optimal approach

Stack does not correctly track the '3' and '2' values, causing false negatives

✅ Pop all smaller elements before pushing the current element to maintain correct stack state

Trying to find the pattern from left to right in the optimal approach

Fails to track the '2' value correctly, leading to incorrect results

✅ Traverse from right to left to correctly identify the '2' and '3' values

🧠

Brute Force (Triple Nested Loops)

💡 Starting with brute force helps understand the problem’s core: checking all possible triples to find the pattern. Though inefficient, it builds intuition about the pattern’s definition.

Intuition

Check every possible triplet (i, j, k) with i < j < k and verify if nums[i] < nums[k] < nums[j].

Algorithm

1. Iterate i from 0 to n-3
2. For each i, iterate j from i+1 to n-2
3. For each j, iterate k from j+1 to n-1
4. Check if nums[i] < nums[k] < nums[j], return true if yes

💡 The triple nested loops directly implement the pattern’s definition but are inefficient due to repeated checks.

</>

Code

def find132pattern(nums):
    n = len(nums)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if nums[i] < nums[k] < nums[j]:
                    return True
    return False

# Driver code
if __name__ == '__main__':
    print(find132pattern([3,1,4,2]))  # True
    print(find132pattern([1,2,3,4]))  # False

Line Notes

for i in range(n - 2):Outer loop picks the first element i of the triplet

for j in range(i + 1, n - 1):Middle loop picks the second element j after i

for k in range(j + 1, n):Inner loop picks the third element k after j

if nums[i] < nums[k] < nums[j]:Check if the triplet satisfies the 132 pattern condition

public class Solution {
    public static 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;
    }

    public static void main(String[] args) {
        System.out.println(find132pattern(new int[]{3,1,4,2})); // true
        System.out.println(find132pattern(new int[]{1,2,3,4})); // false
    }
}

Line Notes

for (int i = 0; i < n - 2; i++) {Select first index i for the triplet

for (int j = i + 1; j < n - 1; j++) {Select second index j after i

for (int k = j + 1; k < n; k++) {Select third index k after j

if (nums[i] < nums[k] && nums[k] < nums[j]) {Check if the 132 pattern condition holds

#include <iostream>
#include <vector>
using namespace std;

bool find132pattern(vector<int>& nums) {
    int n = nums.size();
    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;
}

int main() {
    vector<int> nums1 = {3,1,4,2};
    vector<int> nums2 = {1,2,3,4};
    cout << boolalpha << find132pattern(nums1) << endl; // true
    cout << boolalpha << find132pattern(nums2) << endl; // false
    return 0;
}

Line Notes

for (int i = 0; i < n - 2; i++) {Outer loop picks first element i

for (int j = i + 1; j < n - 1; j++) {Middle loop picks second element j

for (int k = j + 1; k < n; k++) {Inner loop picks third element k

if (nums[i] < nums[k] && nums[k] < nums[j]) {Check if triplet forms 132 pattern

function find132pattern(nums) {
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }
    return false;
}

// Test cases
console.log(find132pattern([3,1,4,2])); // true
console.log(find132pattern([1,2,3,4])); // false

Line Notes

for (let i = 0; i < n - 2; i++) {Select first index i for the triplet

for (let j = i + 1; j < n - 1; j++) {Select second index j after i

for (let k = j + 1; k < n; k++) {Select third index k after j

if (nums[i] < nums[k] && nums[k] < nums[j]) {Check if the 132 pattern condition is met

⏱

Complexity

TimeO(n^3)

SpaceO(1)

Three nested loops each can iterate up to n times, resulting in cubic time complexity.

💡 For n=20, this means 20*19*18 = 6840 operations, which is slow but still manageable for small inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Better Approach (Using Min Prefix Array and Nested Loop)

💡 This approach improves efficiency by precomputing the minimum value before each index, reducing one nested loop and avoiding redundant comparisons.

Intuition

For each middle element j, track the minimum element to its left (i) and check if there exists a k > j with nums[k] between min prefix and nums[j].

Algorithm

1. Create an array min_prefix where min_prefix[j] = minimum of nums[0..j-1]
2. For each j from 1 to n-2, iterate k from j+1 to n-1
3. Check if min_prefix[j] < nums[k] < nums[j], return true if yes
4. Return false if no pattern found

💡 Precomputing min_prefix helps quickly find the smallest i for each j, reducing redundant checks.

</>

Code

def find132pattern(nums):
    n = len(nums)
    if n < 3:
        return False
    min_prefix = [0] * n
    min_prefix[0] = nums[0]
    for i in range(1, n):
        min_prefix[i] = min(min_prefix[i-1], nums[i])
    for j in range(1, n - 1):
        if nums[j] <= min_prefix[j]:
            continue
        for k in range(j + 1, n):
            if min_prefix[j] < nums[k] < nums[j]:
                return True
    return False

# Driver code
if __name__ == '__main__':
    print(find132pattern([3,1,4,2]))  # True
    print(find132pattern([1,2,3,4]))  # False

Line Notes

min_prefix = [0] * nInitialize array to store minimum prefix values

min_prefix[0] = nums[0]First element is the minimum prefix for index 0

for i in range(1, n):Fill min_prefix with running minimums

if min_prefix[j] < nums[k] < nums[j]:Check if nums[k] fits the 132 pattern between min_prefix[j] and nums[j]

public class Solution {
    public static boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;
        int[] minPrefix = new int[n];
        minPrefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            minPrefix[i] = Math.min(minPrefix[i - 1], nums[i]);
        }
        for (int j = 1; j < n - 1; j++) {
            if (nums[j] <= minPrefix[j]) continue;
            for (int k = j + 1; k < n; k++) {
                if (minPrefix[j] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(find132pattern(new int[]{3,1,4,2})); // true
        System.out.println(find132pattern(new int[]{1,2,3,4})); // false
    }
}

Line Notes

int[] minPrefix = new int[n];Array to store minimum prefix values

minPrefix[0] = nums[0];Initialize first prefix minimum

for (int i = 1; i < n; i++) {Compute running minimum prefix

if (minPrefix[j] < nums[k] && nums[k] < nums[j]) {Check if nums[k] fits the 132 pattern

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool find132pattern(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return false;
    vector<int> minPrefix(n);
    minPrefix[0] = nums[0];
    for (int i = 1; i < n; i++) {
        minPrefix[i] = min(minPrefix[i - 1], nums[i]);
    }
    for (int j = 1; j < n - 1; j++) {
        if (nums[j] <= minPrefix[j]) continue;
        for (int k = j + 1; k < n; k++) {
            if (minPrefix[j] < nums[k] && nums[k] < nums[j]) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> nums1 = {3,1,4,2};
    vector<int> nums2 = {1,2,3,4};
    cout << boolalpha << find132pattern(nums1) << endl; // true
    cout << boolalpha << find132pattern(nums2) << endl; // false
    return 0;
}

Line Notes

vector<int> minPrefix(n);Stores minimum prefix values

minPrefix[0] = nums[0];Initialize first prefix minimum

for (int i = 1; i < n; i++) {Compute running minimum prefix

if (minPrefix[j] < nums[k] && nums[k] < nums[j]) {Check if nums[k] fits the 132 pattern

function find132pattern(nums) {
    const n = nums.length;
    if (n < 3) return false;
    const minPrefix = new Array(n);
    minPrefix[0] = nums[0];
    for (let i = 1; i < n; i++) {
        minPrefix[i] = Math.min(minPrefix[i - 1], nums[i]);
    }
    for (let j = 1; j < n - 1; j++) {
        if (nums[j] <= minPrefix[j]) continue;
        for (let k = j + 1; k < n; k++) {
            if (minPrefix[j] < nums[k] && nums[k] < nums[j]) {
                return true;
            }
        }
    }
    return false;
}

// Test cases
console.log(find132pattern([3,1,4,2])); // true
console.log(find132pattern([1,2,3,4])); // false

Line Notes

const minPrefix = new Array(n);Array to store minimum prefix values

minPrefix[0] = nums[0];Initialize first prefix minimum

for (let i = 1; i < n; i++) {Compute running minimum prefix

if (minPrefix[j] < nums[k] && nums[k] < nums[j]) {Check if nums[k] fits the 132 pattern

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Precomputing min prefix is O(n), nested loops are O(n^2), overall quadratic time.

💡 For n=1000, this means about 1,000,000 operations, which is borderline but better than cubic.

Interview Verdict: Accepted but inefficient for large inputs

This approach is a clear improvement but still too slow for the largest constraints, motivating further optimization.

🧠

Optimal Approach (Monotonic Stack with Tracking Third Value)

💡 This approach uses a stack to efficiently track candidates for the '3' and '2' in the 132 pattern, achieving linear time complexity.

Intuition

Traverse from right to left, use a stack to keep potential '3' values, and track the '2' value with a variable. If we find a '1' smaller than the tracked '2', pattern exists.

Algorithm

1. Initialize an empty stack and a variable 'third' to -∞infinity to track the '2' value
2. Traverse nums from right to left
3. While stack top is less than current num, pop from stack and update 'third'
4. If current num is less than 'third', return true (pattern found)
5. Push current num onto stack
6. Return false if no pattern found

💡 The stack helps find the '3' and '2' values efficiently, and 'third' tracks the best candidate for the '2' in the pattern.

</>

Code

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

# Driver code
if __name__ == '__main__':
    print(find132pattern([3,1,4,2]))  # True
    print(find132pattern([1,2,3,4]))  # False

Line Notes

stack = []Initialize stack to keep track of potential '3' values

third = float('-inf')Tracks the '2' value in the 132 pattern

for num in reversed(nums):Traverse array from right to left to find pattern efficiently

if num < third:If current number is less than 'third', pattern found

import java.util.Stack;

public class Solution {
    public static 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;
    }

    public static void main(String[] args) {
        System.out.println(find132pattern(new int[]{3,1,4,2})); // true
        System.out.println(find132pattern(new int[]{1,2,3,4})); // false
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Stack to hold candidates for '3' in pattern

int third = Integer.MIN_VALUE;Variable to track '2' value in pattern

for (int i = nums.length - 1; i >= 0; i--) {Traverse array from right to left

if (nums[i] < third) return true;If current num is less than 'third', pattern found

#include <iostream>
#include <vector>
#include <stack>
#include <climits>
using namespace std;

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() && st.top() < nums[i]) {
            third = st.top();
            st.pop();
        }
        st.push(nums[i]);
    }
    return false;
}

int main() {
    vector<int> nums1 = {3,1,4,2};
    vector<int> nums2 = {1,2,3,4};
    cout << boolalpha << find132pattern(nums1) << endl; // true
    cout << boolalpha << find132pattern(nums2) << endl; // false
    return 0;
}

Line Notes

stack<int> st;Stack to hold potential '3' values

int third = INT_MIN;Tracks the '2' value in the pattern

for (int i = nums.size() - 1; i >= 0; i--) {Traverse array from right to left

if (nums[i] < third) return true;If current number is less than 'third', pattern found

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

// Test cases
console.log(find132pattern([3,1,4,2])); // true
console.log(find132pattern([1,2,3,4])); // false

Line Notes

const stack = [];Stack to hold candidates for '3' in the pattern

let third = -Infinity;Tracks the '2' value in the 132 pattern

for (let i = nums.length - 1; i >= 0; i--) {Traverse array from right to left

if (nums[i] < third) return true;If current number is less than 'third', pattern found

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is pushed and popped at most once from the stack, resulting in linear time complexity.

💡 For n=100000, this means about 200000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This is the ideal approach to implement in interviews for this problem due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal monotonic stack approach is the best choice in interviews due to its linear time and clear logic.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(1)	No	Yes	Mention only - never code
2. Better (Min Prefix + Nested Loop)	O(n^2)	O(n)	No	Yes	Mention as intermediate step
3. Optimal (Monotonic Stack)	O(n)	O(n)	No	Yes, with extra tracking	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know how to present your solution clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding of the pattern.Step 3: Discuss the inefficiency and propose the better approach with min prefix.Step 4: Present the optimal monotonic stack solution with detailed explanation.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to optimal, and your knowledge of stack-based algorithms.

Common Follow-ups

• What if we want to find the actual indices of the pattern? → Track indices along with values in the stack.
• Can this approach be adapted for other patterns? → Yes, monotonic stacks are useful for various subsequence and next greater element problems.

💡 These follow-ups test deeper understanding and ability to adapt the solution to variations.

🔍

Pattern Recognition

When to Use

1) Need to find a subsequence with three elements satisfying order and inequality constraints, 2) Pattern involves a '132' order, 3) Problem hints at tracking minimums or next greater elements, 4) Large input size requiring efficient solution.

Signature Phrases

'132 pattern''subsequence i < j < k''nums[i] < nums[k] < nums[j]'

NOT This Pattern When

Problems involving only increasing or decreasing subsequences without the '132' order are different patterns.

Similar Problems

Next Greater Element - uses monotonic stack to find next bigger element132 Pattern II - variant with counting occurrencesFind 132 Pattern in Array - same problem with different constraints

Practice

1. Consider the following Python function that computes the largest rectangle area in a histogram using a monotonic stack approach. Given the input heights = [2, 1, 5], what is the value of the variable right after computing the right boundaries (just before calculating max_area)?

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [1, 3, 3]

D. [3, 3, 3]

Solution

1. Step 1: Trace right boundary computation for i=2 (height=5)

   Stack is empty, so right[2] = n = 3, stack = [2]

2. Step 2: Trace i=1 (height=1)

   Pop indices with height >= 1: pop 2 (height=5), stack empty, right[1] = 3, stack = [1]

3. Step 3: Trace i=0 (height=2)

   Stack top is 1 (height=1) < 2, so right[0] = 1, stack = [1,0]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Right boundaries correctly reflect next smaller bar indices [OK]

Hint: Right boundaries found by scanning from right with stack [OK]

Common Mistakes:

• Confusing indices or off-by-one in right boundary
• Not clearing stack before right boundary pass

2. Given the following code for the stock span problem, what is the return value of the third call to next with input prices [100, 80, 60]?

easy

A. 3

B. 2

C. 0

D. 1

Solution

1. Step 1: Trace the first two calls

   Call 1 with price=100: stack empty, span=1, stack=[0], prices=[100]. Call 2 with price=80: top price=100 > 80, no pop, span=2-0=1, stack=[0,1], prices=[100,80].

2. Step 2: Trace the third call with price=60

   Top price=80 > 60, no pop, span=3-1=1, stack=[0,1,2], prices=[100,80,60]. Return 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each price less than previous yields span 1 [OK]

Hint: Span resets to 1 when price is less than previous [OK]

Common Mistakes:

• Confusing index difference calculation
• Off-by-one errors in span computation

3. Given an integer array, you need to find the sum of the minimum values of all possible contiguous subarrays. Which algorithmic approach guarantees an optimal O(n) time complexity solution?

easy

A. Monotonic stack to find previous less and next less elements for each array element

B. Greedy approach selecting minimum elements from left to right

C. Dynamic programming with memoization of subarray minimums

D. Brute force nested loops checking all subarrays and their minimums

Solution

1. Step 1: Understand problem constraints

   The problem requires summing minimums of all subarrays efficiently, which brute force cannot do in O(n).

2. Step 2: Identify the pattern

   Monotonic stack helps find previous less and next less elements in O(n), enabling counting subarrays where each element is minimum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack finds boundaries for minimums in O(n) [OK]

Common Mistakes:

• Assuming greedy or DP solves this in O(n)
• Confusing with maximum subarray problems

4. What is the time complexity of the optimal iterative stack-based algorithm to evaluate a Reverse Polish Notation expression with n tokens?

medium

A. O(n) because each token is processed exactly once with constant-time stack operations

B. O(n) for processing tokens plus O(n) for recursion stack space

C. O(n log n) due to sorting or priority queue operations involved

D. O(n^2) because each operator requires scanning the stack to find operands

Solution

1. Step 1: Identify operations per token

   Each token is processed once; operands are pushed, operators pop two operands and push one result.

2. Step 2: Analyze stack operations

   Stack push/pop are O(1), so total time is proportional to number of tokens n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No nested loops or recursion in iterative approach [OK]

Hint: Stack operations are O(1), so linear time overall [OK]

Common Mistakes:

• Assuming O(n^2) due to repeated stack scans
• Confusing recursion stack space with time
• Thinking sorting is involved

5. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character might be compared multiple times during matching

B. O(n) because each character is processed once with constant-time stack operations

C. O(n log n) due to sorting or ordering operations on the stack

D. O(n) for time but O(n^2) for space due to stack growth in worst case

Solution

1. Step 1: Identify complexity of outer loop

   The algorithm iterates over each character exactly once, so the loop is O(n).

2. Step 2: Check stack operations

   Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant-time stack ops -> O(n) time [OK]

Hint: Each character processed once with O(1) stack ops [OK]

Common Mistakes:

• Confusing with brute force O(n^2) approach