Dip Pattern Search
MediumStack
Problem
A dip pattern in an array nums is a triple of indices i < j < k with nums[i] < nums[k] < nums[j]: a low value, then a peak, then a value that falls back between them.
Return true if nums contains a dip pattern and false otherwise.
Example 1
- Input:
- nums = [4, 1, 5, 3]
- Output:
- true
1 < 3 < 5 at indices 1, 2, 3.
Example 2
- Input:
- nums = [1, 2, 3, 4]
- Output:
- false
Nothing ever falls back.
Constraints
- 1 ≤ nums.length ≤ 2·10^5
- -10^9 ≤ nums[i] ≤ 10^9
Hint
Show the first hint
Fix the role of the middle-valued element nums[k]. What would make it as useful as possible?
Walkthrough
How to approach it
01Clarify before coding
- Are the inequalities strict? Yes, all three.
- Do the indices need to be adjacent? No, only ordered.
- Is n large? Up to 2·10^5, so O(n²) is too slow.
02Brute force
Try all triples, or for each j use the prefix minimum as nums[i] and scan right for a value strictly between.
Cost: O(n³) for all triples, O(n²) with the prefix-minimum trick: 4·10^10 steps at worst.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.