Show problems as
Classic problem #456MediumArrayBinary SearchStackMonotonic StackOrdered Set

132 Pattern

Real-world version: Dip Peak Shelf In A Trace
Tracked in this browser only
Read 132 Pattern on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A field logger writes one signed reading per tick into trace. Readings can sit below zero.

A dip-peak-shelf is a choice of three ticks i, j, k obeying i < j < k, such that

trace[i] < trace[k] < trace[j]

In words: the earliest of the three is the dip, the middle one is the peak, and the last one is a shelf that lands strictly above the dip and strictly below the peak. Both comparisons are strict, and the three ticks do not have to be next to one another.

Return true if any dip-peak-shelf occurs in trace, and false if none does.

Examples

Example 1

Input
trace = [6,9,7]
Output
true

Ticks 0, 1 and 2 give the dip 6, the peak 9 and the shelf 7, and 6 < 7 < 9 holds.

Example 2

Input
trace = [5,5,5,5]
Output
false

Every reading is 5, so no choice of three ticks can put a shelf strictly between a dip and a peak.

Example 3

Input
trace = [8,4,9,2,7]
Output
true

Ticks 1, 2 and 4 give the dip 4, the peak 9 and the shelf 7, and 4 < 7 < 9 holds. Tick 3 sits between the peak and the shelf, which the definition allows.

Example 4

Input
trace = [2,4,6,8,10]
Output
false

The readings only ever climb, so the last of any three ticks is the largest of the three and can never be the shelf.

Example 5

Input
trace = [-8,-2,-5]
Output
true

Readings may be negative: ticks 0, 1 and 2 give the dip -8, the peak -2 and the shelf -5, and -8 < -5 < -2 holds.

Example 6

Input
trace = [7,3]
Output
false

Only two ticks were logged, and a dip-peak-shelf needs three.

Constraints

  • n == trace.length
  • 1 <= n <= 2 * 10^5
  • -10^9 <= trace[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find132pattern(trace: list[int]) -> bool:
Java
public boolean find132pattern(int[] trace)

More on the same topics