AlgoMaster Logo

132 Pattern

mediumFrequency9 min readUpdated June 23, 2026

Understanding the Problem

We need to find three elements in the array, in order from left to right, that form a specific pattern: the first element is the smallest, the third is in the middle, and the second is the largest. In other words, we need indices i < j < k where nums[i] < nums[k] < nums[j].

The naming "132 pattern" comes from the relative ordering of the values: position 1 has the smallest value, position 3 has the middle value, and position 2 has the largest value. So despite the indices being in order (i, j, k), the values follow a "small, big, medium" pattern.

The three elements do not need to be adjacent; they can sit anywhere in the array as long as their indices increase. The work is in tracking candidates for each role efficiently.

One reframing drives every efficient approach below: find a pair (nums[j], nums[k]) where j < k and nums[k] < nums[j], then check whether any element before index j is smaller than nums[k]. The triplet search becomes a pair search plus a lookup.

Key Constraints:

  • 1 <= n <= 2 * 10^5 → At 200,000 elements, O(n^2) is roughly 4 * 10^10 operations, well past any time limit. The target is O(n log n) or O(n).
  • -10^9 <= nums[i] <= 10^9 → Values can be negative, so initial sentinels must use the smallest representable value (or negative infinity) rather than 0.

Approach 1: Brute Force

Intuition

Check every possible triplet (i, j, k). For each combination of three indices where i < j < k, test whether nums[i] < nums[k] < nums[j]. If any triplet passes, return true. This translates the problem statement directly into code.

Algorithm

  1. Use three nested loops to enumerate all triplets (i, j, k) with i < j < k.
  2. For each triplet, check if nums[i] < nums[k] < nums[j].
  3. If the condition holds, return true.
  4. If no valid triplet is found after checking all possibilities, return false.

Example Walkthrough

1(i,j,k)=(0,1,2): need nums[i] < nums[k] < nums[j], i.e. 3 < 4 < 1. Fails: 4 < 1 is false
0
i
3
1
j
1
2
4
k
3
2
1/4

Code

An O(n^3) scan cannot finish for n = 2 * 10^5. The first improvement targets the "i" role: for a fixed j, the best candidate for nums[i] is the minimum of everything before index j, and one prefix pass computes that for every j at once.

Approach 2: Precomputed Minimum with Pair Search

Intuition

For the "1" in the 132 pattern (the smallest element), the best choice at any index j is the smallest value to its left: the smaller nums[i] is, the wider the window between nums[i] and nums[j] that nums[k] can fall into. A prefix minimum array supplies that value for every j, so no loop over i is needed.

With the prefix minimum in hand, iterate over each j from left to right and scan the suffix for any k > j where prefixMin[j] < nums[k] < nums[j]. This reduces the problem from three nested loops to two.

Algorithm

  1. Build a prefix minimum array where prefixMin[j] is the smallest value in nums[0..j-1].
  2. For each index j from 1 to n-2, check if nums[j] > prefixMin[j] (otherwise no valid i exists for this j).
  3. For each valid j, scan all indices k from j+1 to n-1, checking if prefixMin[j] < nums[k] < nums[j].
  4. If found, return true. If no triplet is found after all iterations, return false.

Example Walkthrough

1Build prefixMin: [3, 3, 1, 1]. Start scanning j=1
0
3
1
j
1
2
4
3
2
1/4

Code

The remaining bottleneck is the inner scan for k. For each j, that scan answers one question: does any element to the right of j fall strictly between prefixMin[j] and nums[j]? That is a counting query over a growing set of values, and a Fenwick tree answers it in O(log n) instead of O(n).

Approach 3: Prefix Minimum + Fenwick Tree

Intuition

Keep the prefix minimum from Approach 2, but replace the linear scan for k with a counting structure. Process j from right to left and maintain a multiset of the elements at indices greater than j. The question "is there a k > j with prefixMin[j] < nums[k] < nums[j]?" becomes "how many stored values lie strictly between prefixMin[j] and nums[j]?"

A Fenwick tree (binary indexed tree) supports the two operations this needs in O(log n) each: insert one occurrence of a value, and count how many stored values are at most x. The count of values strictly inside the interval is then count(values < nums[j]) minus count(values <= prefixMin[j]). Values span -10^9 to 10^9, far too wide to index directly, so compress them first: sort a copy of the array and use each value's first position in the sorted copy (1-based) as its rank. Using the first position keeps both queries exact, since every value smaller than v gets a rank below rank(v) and every value at or above v gets a rank of at least rank(v). Duplicates share a rank, and their insertions accumulate at the same tree position, so counts remain correct.

Algorithm

  1. Build the prefix minimum array, where prefixMin[j] is the smallest value in nums[0..j-1].
  2. Sort a copy of nums. Define rank(v) as 1 plus the first index of v in the sorted copy, found with binary search.
  3. Create a Fenwick tree over ranks 1..n and insert nums[n-1].
  4. For each j from n-2 down to 1, the tree holds exactly the elements at indices greater than j. If nums[j] > prefixMin[j], compute query(rank(nums[j]) - 1) - query(rank(prefixMin[j])). The first term counts stored values strictly below nums[j]; the second counts stored values at or below prefixMin[j]. If the difference is positive, return true.
  5. Insert nums[j] into the tree and move to j-1. If the loop completes, return false.

Example Walkthrough

For nums = [3, 5, 0, 3, 4], the prefix minimum is [3, 3, 3, 0, 0] and the sorted copy is [0, 3, 3, 4, 5], giving rank(0)=1, rank(3)=2, rank(4)=4, rank(5)=5.

1prefixMin=[3,3,3,0,0]. Ranks: 0=1, 3=2, 4=4, 5=5. Insert nums[4]=4. Tree holds {4}
0
3
1
5
2
0
3
3
4
4
inserted
1/5

Both 3s in the array map to rank 2; when duplicates are inserted, they accumulate at the same tree position and are counted as separate elements. At j=1, the query finds exactly one stored value in the open interval (3, 5): the 4 at index 4, which completes the pattern (3, 5, 4).

Code

The Fenwick tree brings the runtime to O(n log n). A monotonic stack does better: one right-to-left pass that replaces the counting structure with a single integer, for O(n) total.

Approach 4: Monotonic Stack (Optimal)

Intuition

Scan from right to left with two pieces of state: a stack of elements that can still serve as the "3" (the nums[j] role), and a variable third holding the best candidate found so far for the "2" (the nums[k] role), initialized to negative infinity.

When the current element is greater than the stack's top, the current element works as nums[j] for every smaller value popped off the stack: each popped value sits to its right and below it, which is what nums[k] requires. Record the largest popped value in third. Keeping only the maximum is safe because the remaining test is nums[i] < third, and a larger third makes that test strictly easier to pass.

If the scan reaches an element smaller than third, that element completes the pattern as nums[i], and the function returns true.

Algorithm

  1. Initialize an empty stack and a variable third set to negative infinity.
  2. Iterate through the array from right to left.
  3. If the current element is less than third, return true: the current element is nums[i], third is nums[k], and the element that popped third is nums[j].
  4. While the stack is non-empty and the current element is greater than the stack's top, pop from the stack and update third to the maximum of third and the popped value.
  5. Push the current element onto the stack.
  6. If the loop finishes without finding a pattern, return false.

Example Walkthrough

1Initialize: scan right to left, stack=[], third=-inf
0
3
1
1
2
4
3
2
i
1/5

Code