Abstract / Summary

Check if there exists a triplet of indices i j k with i < j < k where the value at i is smaller than at k and the value at j is larger than at k.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 35% (900k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Monotonic Stack
• Ordered Set
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The function implements a detection routine for the “132” pattern in an integer sequence. A “132” pattern exists when three indices i < j < k satisfy nums[i] < nums[k] < nums[j]. The algorithm maintains a dynamic view of candidate low-high intervals while scanning the array once, using an ordered map to support efficient range queries. Early exits are triggered as soon as a valid pattern is found.

Initial validation

The very first step guards against inputs that cannot possibly contain a pattern because they lack enough elements.

if (nums.size() < 3)
    return false;

If the vector length is less than three, the function returns immediately, handling the edge case of trivially short inputs.

Establishing the first interval

Two variables, low and high, are seeded from the first three elements. low records the smallest value seen so far, while high is set to the larger of the second and third elements, establishing an initial candidate interval. The map lowHigh stores the current low value as a key and the associated high as its value, and the second element is also entered with the same high.

auto low  = nums[0];
auto high = max(nums[1], nums[2]);
lowHigh[nums[0]] = high;
lowHigh[nums[1]] = high;

This preparation creates a baseline against which later elements are compared.

Main scanning loop

The core of the algorithm iterates from the third index onward, processing each element as current. The loop structure is straightforward:

for (int i = 2; i < nums.size(); i++)
{
    auto current = nums[i];
    // ... body ...
}

Inside the loop, several distinct logical branches handle different situations.

Skipping consecutive duplicates

When the current element equals its immediate predecessor, the iteration continues without further work. This avoids redundant work on equal adjacent values, which cannot contribute to a strict “132” ordering.

if (nums[i] == nums[i - 1]) // optimization
    continue;

Immediate pattern detection

If the current value lies strictly between the stored low and high, a “132” pattern is confirmed instantly, and the function returns true.

if (current > low && current < high)
    return true;

This check captures the simplest case where the three-element relationship is already satisfied.

Scanning existing intervals

When the immediate check fails, the algorithm probes the map for any previously recorded low-high pair that could form a pattern with the current value. It uses lower_bound to locate the first key not less than current, then walks backwards through the map entries, comparing each stored high against current. If any stored high exceeds current, a valid pattern is found.

auto scan = lowHigh.lower_bound(current);
if (scan != lowHigh.begin())
    do
    {
        scan--;
        if (scan->second > current)
            return true;
    } while (scan != lowHigh.begin());

Walking backwards ensures that only intervals with a low value smaller than current are examined, respecting the required ordering of indices.

Ignoring values equal to current bounds

If current matches either the current low or high, the iteration skips further processing. Since a “132” pattern requires strict inequality, equality cannot satisfy the condition, and the algorithm avoids unnecessary updates.

if (current == low || current == high)
    continue;

Updating the high bound

When current exceeds the existing high, the algorithm raises the high bound and propagates this change through the map. It iterates over all entries, raising any stored high that is lower than the new high. Updated keys are collected in a temporary vector same.

if (current > high)
{
    high = current;
    vector<int> same;
    // move highs higher
    for (auto& update : lowHigh)
        if (update.second < high)
        {
            update.second = high;
            same.push_back(update.first);
        }

After raising the highs, the algorithm removes redundant map entries, keeping only the first occurrence of each high value. This pruning prevents the map from growing with duplicate intervals that no longer contribute new information.

    // erase redundant entries
    for (int i = 1; i < same.size(); i++)
        lowHigh.erase(same[i]);

    continue;
}

The continue statement ensures that after a high update, the loop proceeds directly to the next element, bypassing the low-reset logic.

Resetting when current is lower than low

If current falls below the existing low, both low and high are reset to current, and a new entry is inserted into the map. This handles the scenario where a new, smaller potential start of a pattern appears.

// current < low
low = high = current;
lowHigh[current] = current;

By resetting both bounds, the algorithm discards previous intervals that can no longer lead to a valid pattern because any future element would need to be larger than the new low but smaller than a high that no longer exists.

Final outcome

If the loop completes without encountering a return, the function concludes that no “132” pattern exists and returns false.

return false;

Edge-case handling

The code explicitly addresses several edge conditions:

• Input vectors with fewer than three elements are rejected early.
• Consecutive duplicate values are ignored, preventing false positives from equal elements.
• Equality with the current low or high bounds triggers a skip, preserving the strict inequality requirement.
• When a new element surpasses the current high, the map is updated and cleaned to avoid stale intervals.
• When a new element is smaller than the current low, both bounds are reset, ensuring that the algorithm always works with the most promising low-high pair.

These checks collectively guarantee correct behavior across a wide range of input patterns, including monotonic sequences, repeated values, and abrupt jumps.

Performance optimizations

The implementation incorporates several techniques to keep the runtime efficient:

• The early return on size < 3 eliminates unnecessary work for trivial inputs.
• Skipping consecutive duplicates reduces the number of map operations.
• Using std::map::lower_bound provides logarithmic access to the relevant region of stored intervals.
• The backward scan stops as soon as the beginning of the map is reached, avoiding a full traversal.
• When raising the high bound, the algorithm updates only those entries that actually need adjustment, and then removes duplicate keys, preventing the map from bloating with irrelevant entries.
• Resetting both bounds when encountering a new low eliminates the need to maintain multiple overlapping intervals, keeping the map compact.

These strategies together enable the function to process large arrays with a modest amount of auxiliary storage and a limited number of expensive map operations.

Imagine a long line of numbers standing on a playground. The goal is to see if any three numbers can play a special game together. These three numbers have to follow a specific pattern that looks like a little roller coaster. The first number needs to be the smallest, the second number needs to be the biggest, and the third number needs to be somewhere right in the middle between the first two.

When looking through the line, the numbers act like scouts trying to remember the smallest and largest ones seen so far. Every time a new number joins the view, the code checks if it fits the middle spot in the roller coaster. If the new number is bigger than the smallest one found before but smaller than the biggest one, the pattern is complete. If the number is even bigger than the biggest one, the scouts update their map to remember that the playground has grown taller. If the number is smaller than everything else, the scouts start fresh with this new, tiny number. The whole process is just a way to organize the numbers into little groups to see if that hidden roller coaster exists anywhere in the long line.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		C++				Java		TS
	WalkCCC	Python		C++				Java
	leetcode.ca	Python		C++		Go		Java	Rust	TS
	LeetcodeHelp	Python		C++				Java
	Progiez	Python		C++				Java
github	everthis		JS
	fartem				Ruby
	halfrost					Go
	JoshCrozier		JS
	linouk23			C++
	lkwq007	Python
	suxrobGM						C#
	trung-hn	Python
	wisdompeak			C++
	YuriSpiridonov	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
everthis	JavaScript
fartem	Ruby
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality