Sorted Before the Turn
EasyArrays & Hashing
Problem
A circular display shows prices that were sorted in non-decreasing order, but the display may have been turned: its starting point could be any position of the sorted list, wrapping around at the end.
Given the shown order nums, return true if it is some rotation (possibly by zero positions) of a non-decreasing array, and false otherwise.
Example 1
- Input:
- nums = [3, 4, 5, 1, 2]
- Output:
- true
It is [1, 2, 3, 4, 5] started from position 2.
Example 2
- Input:
- nums = [2, 1, 3, 4]
- Output:
- false
There is a drop at 2 → 1 and another when wrapping from 4 back to 2.
Example 3
- Input:
- nums = [1, 2, 3]
- Output:
- true
Rotation by zero positions.
Constraints
- 1 ≤ nums.length ≤ 10^5
- -10^9 ≤ nums[i] ≤ 10^9
Hint
Show the first hint
Walk around the circle once. In a sorted array, how many times does the value go down?
Walkthrough
How to approach it
01Clarify before coding
- Does a rotation by zero count? Yes, a sorted array is valid.
- Can values repeat? Yes; equal neighbours are not drops.
- Is a single element valid? Yes.
02Brute force
Try every rotation k, build it, and check whether it is sorted.
Cost: O(n²) time: 10^10 steps at n = 10^5.
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.