The problem
The list a holds journey times in minutes, sorted from shortest to longest, with no two the same. Find two journeys that together take exactly target minutes. Return their indices as [i, j] with i < j. If several pairs work, return the one with the smallest i. If none works, return [].
pair_with_sum([2, 5, 8, 12, 16, 23, 38, 45], 31)
# [2, 5]: 8 + 23
pair_with_sum([1, 2, 3, 4, 5, 6], 7)
# [0, 5], not [1, 4] or [2, 3]
pair_with_sum([1, 4, 9], 8) # []
Use the sorted order. The aim is O(n) time and O(1) extra space.
Limits
- Up to 200,000 values. Values may be negative.
Builds on ARRS-2 Two pointers.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | One pair | Not run | |
| 2 | No pair | Not run | |
| 3 | Several pairs: smallest i | Not run | |
| 4 | A value cannot pair with itself | Not run | |
| 5 | Negative values | Not run | |
| 6 | Fewer than two values | Not run | |
| 7 | 200,000 values, no pair | Not run | |
| 8 | 200,000 values, pair in the middle | Not run |