132 Pattern - Practice Coding Problems

132 Pattern - Problem

Array Binary Search Stack Monotonic Stack Ordered Set Medium

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.

Input & Output

Example 1 — Found Pattern

$ Input: nums = [1,2,3,4]

› Output: false

💡 Note: No 132 pattern exists. The array is strictly increasing, so no element can satisfy nums[i] < nums[k] < nums[j] with i < j < k.

Example 2 — Valid Pattern

$ Input: nums = [3,1,4,2]

› Output: true

💡 Note: Pattern found at indices (1,2,3): nums[1]=1, nums[2]=4, nums[3]=2, and 1 < 2 < 4 forms a 132 pattern.

Example 3 — Decreasing Array

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

› Output: true

💡 Note: Pattern found at indices (0,1,2): nums[0]=-1, nums[1]=3, nums[2]=2, and -1 < 2 < 3 forms a 132 pattern.

Constraints

n == nums.length
1 ≤ n ≤ 2 × 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with potential 132 pattern

Pattern Search

Look for three indices i < j < k with nums[i] < nums[k] < nums[j]

Result

Return true if pattern exists, false otherwise

Key Takeaway

🎯 Key Insight: Use a monotonic stack scanning backwards to efficiently track the largest valid middle element

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is to scan from right to left using a monotonic stack to efficiently track potential '3' values in the 132 pattern. Best approach uses a monotonic stack that maintains decreasing order while tracking the largest valid middle element. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack (Optimal)	O(n)	O(n)	Use a monotonic stack scanning backwards to efficiently find 132 patterns
Two Pass with Minimum Tracking	O(n²)	O(n)	Track minimum values to left, then check for valid k values on the right
Brute Force - Check All Triplets	O(n³)	O(1)	Check every possible triplet (i, j, k) to see if it forms a 132 pattern

Monotonic Stack (Optimal) — Algorithm Steps

Scan array from right to left
Maintain monotonic decreasing stack
Track largest valid '3' candidate
For each potential '2', check if pattern exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Right to Left

Process elements from end to start

Stack Operations

Maintain decreasing stack, update 'third'

Pattern Check

If current < third, pattern found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

bool solution(int* nums, int numsSize) {
    if (numsSize < 3) return false;
    
    int* stack = (int*)malloc(numsSize * sizeof(int));
    int stackSize = 0;
    int third = INT_MIN; // The '3' in 132 pattern
    
    // Scan from right to left
    for (int i = numsSize - 1; i >= 0; i--) {
        // If current number is less than third, we found 132 pattern
        if (nums[i] < third) {
            free(stack);
            return true;
        }
        
        // Pop elements smaller than current from stack
        // These become candidates for the '3' position
        while (stackSize > 0 && stack[stackSize - 1] < nums[i]) {
            int val = stack[--stackSize];
            if (val > third) {
                third = val;
            }
        }
        
        stack[stackSize++] = nums[i];
    }
    
    free(stack);
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    printf(solution(nums, size) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element pushed/popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n elements in worst case

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler