1261. Permutation Stretches
A ticket printer stamps each ticket with a sequence number, and a night-shift supervisor audits the printed stream. A contiguous stretch of the stream of length m is complete when it contains every number from 1 to m exactly once, in any order: 2, 1, 3 is complete, while 2, 2, 3 and 1, 3 are not.
Given the array nums, return how many contiguous stretches are complete. A single 1 is a complete stretch of length 1, and stretches at different positions count separately. The answer can exceed 32 bits, so return it as a 64-bit integer.
Aim for O(n) expected time and O(n) extra space: every complete stretch contains exactly one 1, which limits where its endpoints can be.
Example 1
- Input:
- nums = [4,2,1,3,6,1,5,2,1]
- Output:
- 7
- Explanation:
The complete stretches are 4,2,1,3 then 2,1,3 then 2,1 twice and the single 1 three times, giving 7 in total.
Example 2
- Input:
- nums = [3,1,4,1,5,2,6]
- Output:
- 2
- Explanation:
Only the two single-1 stretches are complete, because no longer window holds exactly 1 to m once each, so the answer is 2.
Example 3
- Input:
- nums = [5,2,6,1,1,4,3,2,1]
- Output:
- 7
- Explanation:
The complete stretches are the three single 1s, the windows 2,1 and 3,2,1 and the windows 1,4,3,2 and 4,3,2,1, giving 7 in total.
Constraints
1 ≤ n ≤ 105
1 ≤ nums[i] ≤ n
The answer fits in a 64-bit integer.
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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)