1308. Low Disorder Stretches
A telescope logs brightness readings in the order they were taken. Inside any run of consecutive readings, an out-of-order pair is a pair of positions i < j in that run with nums[i] > nums[j]. A run is called tidy when it contains at most k out-of-order pairs.
Given the array nums and the long integer k, return how many non-empty contiguous runs of nums are tidy. Runs at different positions count separately even when their values are the same. Equal readings never form an out-of-order pair. The answer can exceed 32 bits, so return it as a long.
Making a run longer can only add out-of-order pairs, never remove them, so the aim is a solution that runs in O(n log n) time and O(n) space.
Example 1
- Input:
- nums = [3,1,2], k = 1
- Output:
- 5
- Explanation:
The runs [3], [1], [2], [1,2] and [3,1] each have at most 1 out-of-order pair, while [3,1,2] has 2, so the count is 5.
Example 2
- Input:
- nums = [5,4,3,2,1], k = 0
- Output:
- 5
- Explanation:
With k = 0 only runs with no out-of-order pair qualify, which here means the 5 single readings.
Example 3
- Input:
- nums = [2,2,2], k = 0
- Output:
- 6
- Explanation:
Equal readings never form an out-of-order pair, so all 6 runs are tidy.
Constraints
-
1 ≤ nums.length ≤ 5 * 104 -
1 ≤ nums[i] ≤ 109 -
0 ≤ k ≤ 1010
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 6,000 msC++ 1,500 msJava 3,000 msJavaScript 3,000 msTypeScript 3,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)