0410MediumArrayBinary SearchStackMonotonic StackOrdered Set

Dip Peak Shelf In A Trace

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find132pattern(trace: list[int]) -> bool:

Java

public boolean find132pattern(int[] trace)

The intended approach

Time O(n)Space O(n) for the stack

Sweep the ticks from the last one back to the first, keeping a stack of readings seen so far that are still candidates for the peak, and a single value `shelf` holding the best candidate for the shelf found so far. Before pushing the current reading, if it already falls below `shelf` then it serves as the dip and the answer is yes. Otherwise the current reading evicts every smaller reading from the stack, and the largest reading it evicts becomes the new `shelf`, since that evicted reading sits later in the run and below the current one.

Pythonentry point: find132pattern

def find132pattern(trace):
    # Time O(n): the loop runs once per tick and each reading is pushed and
    # popped at most once overall. Space O(n) for the stack.
    stack = []
    shelf = None
    for i in range(len(trace) - 1, -1, -1):
        value = trace[i]
        if shelf is not None and value < shelf:
            return True
        while stack and stack[-1] < value:
            shelf = stack.pop()
        stack.append(value)
    return False

The obvious version

Try every ordered triple of tick positions with three nested loops and test the two comparisons directly.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find132pattern(trace):
    n = len(trace)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if trace[i] < trace[k] and trace[k] < trace[j]:
                    return True
    return False

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
6 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in