Loading page…
Practice problem · medium
A parcel-delivery app books couriers for fixed shifts. A shift is a number of minutes. A courier can cover a shift with two delivery windows that fill it exactly, with no gap and no overlap.
You get the lengths of the delivery windows and the shift length. You count how many windows have a partner window, at a different position, that completes the shift.
Write windows_with_partner(durations, shift).
durations[i] is the length in minutes of the i-th window.j != i has durations[i] + durations[j] == shift.Input: durations = [120, 360, 240, 120], shift = 480
Output: 3The trace counts the lengths, then checks each window for the complement shift - length. A window whose complement is its own length needs a second copy.
| i | length | Complement (480 - length) | Partner exists? | Windows so far |
|---|---|---|---|---|
| 0 | 120 | 360 | yes | 1 |
| 1 | 360 | 120 | yes | 2 |
| 2 | 240 | 240 | no: only one 240 | 2 |
| 3 | 120 | 360 | yes | 3 |
Three windows have a partner, so the output is 3. The window of 240 would need a second 240.
Input: durations = [240], shift = 480
Output: 0One window cannot partner with itself, so the answer is 0.
Input: durations = [240, 240], shift = 480
Output: 2Two windows of 240 fill the 480-minute shift together, so both have a partner.
0 ≤ durations.length ≤ 100,000 (windows)1 ≤ durations[i] ≤ 500,000,000 (minutes)2 ≤ shift ≤ 1,000,000,000Checking every other window for each window costs about n × n steps, 10^10 at n = 100,000. A table of counts answers "does the complement exist?" in one step. The sum of two lengths is at most 10^9, so it fits in a 32-bit int.
windows_with_partner · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.