Particle Velocity Periods
MediumArrays · Microsoft
particles[i] is the position of a particle measured at time i; measurements are taken at equal time intervals.
A stable period is a contiguous stretch particles[l..r] of at least three measurements in which the particle moves at constant velocity, meaning the difference particles[t + 1] - particles[t] is the same for every t from l to r - 1. The velocity may be zero or negative.
Return the total number of stable periods. Periods that overlap or contain one another are all counted separately.
Example 1
- Input:
- particles = [4, 7, 10, 13, 9, 5, 5, 5]
- Output:
- 5
- Explanation
- Positions 4, 7, 10, 13 move by +3 each step, giving 3 periods (two of length 3, one of length 4). 13, 9, 5 moves by -4 for 1 more, and 5, 5, 5 is still for 1 more, so the total is 5.
Example 2
- Input:
- particles = [2, 2, 2, 2]
- Output:
- 3
- Explanation
- The velocity is always 0: there are two periods of length 3 and one of length 4.
Example 3
- Input:
- particles = [1, 2, 4]
- Output:
- 0
- Explanation
- The differences are 1 and 2, so the only window of three measurements is not stable.
Constraints
1 <= particles.length <= 10^5-10^9 <= particles[i] <= 10^9