Chord within a span: hints, no solution
Medium · Two pointers
A synthesiser stores the notes of a passage as pitches in a list sorted from lowest to highest, with repeats allowed when the same pitch is played more than once. Pitches are measured in cents, a whole-number unit.
A chord candidate is any choice of three positions i < j < k in the list. It fits a span if the difference between its highest and lowest pitch, pitches[k] minus pitches[i], is at most span. Count the candidates that fit. Positions are distinct even when their pitches are equal. The count can be far larger than 32 bits for long lists.
Examples
- Input
- pitches = [60, 62, 64, 67, 69], span = 5
- Output
- 3
- Note
- The fitting triples are positions (0,1,2), (1,2,3) and (2,3,4).
- Input
- pitches = [50, 60, 70], span = 5
- Output
- 0
- Note
- The only triple has pitches 20 apart, above the span of 5.
- Input
- pitches = [10, 10, 10, 10], span = 0
- Output
- 4
- Note
- Four equal pitches contain four different triples of positions.
Constraints
- 0 <= pitches.length <= 110000, sorted in non-decreasing order
- 0 <= pitches[i] <= 100000
- 0 <= span <= 100000
Hint 1: a nudge
If you fix the lowest note of a candidate, what decides which other notes may join it?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.