Postcode Stretch on the Van
A delivery van is loaded so the parcels sit on one long rack, sorted by postcode. Many parcels share a postcode, so they form a stretch of neighbours on the rack.
When the driver turns into a new postcode area, the tablet should light up exactly that stretch: the first and the last parcel for that postcode. If no parcel is for this area, it lights nothing.
Your task
Write findStretch(postcodes, code). postcodes is sorted in non-decreasing order. Return [first, last]: the smallest and largest index holding code. If code is not present (or the list is empty), return [-1, -1].
Aim for O(log n) even when one postcode fills most of the rack.
findStretch(postcodes: int[], code: int) → int[]
Examples
postcodes = [2040, 2040, 3115, 3115, 3115, 3120, 4500] code = 3115
[2, 4]
Postcode 3115 fills indexes 2, 3 and 4. Index 1 is still 2040 and index 5 is already 3120, so the stretch is [2, 4].
postcodes = [2040, 2040, 3115, 3115, 3115, 3120, 4500] code = 3200
[-1, -1]
3200 would sit between 3120 and 4500, but no parcel has it, so nothing lights up.
Constraints
- 0 ≤ postcodes.length ≤ 100,000
- 1000 ≤ postcodes[i], code ≤ 99,999
- postcodes is sorted in non-decreasing order.
Start with brute force
Scan the rack and remember the first and last index where the postcode matches. Or binary search for any match and then walk left and right to the edges of the stretch.
Both are O(n) in the worst case. If 99,000 of 100,000 parcels share the postcode, the walk outward visits nearly all of them. Two boundary searches need about 34 looks in total, no matter how long the stretch is.
Hints
0 of 4 shown- Hint 1
A normal binary search for 3115 in the first example might land on index 3. Is that enough to know where the stretch starts and ends?
- Hint 2
You could walk outwards from index 3, but if 90,000 parcels share the postcode that walk is slow. You need the two edges directly.
- Hint 3
The start of the stretch is the first index with a value of at least
code. The end is one before the first index with a value greater thancode. Both are "first index where a condition becomes true". - Hint 4
Write one helper
firstIndex(cond)with the lower-bound loop (lo = 0,hi = n,hi = midwhen true,lo = mid + 1otherwise). Call it forvalue >= codeand forvalue > code. If the first result is out of range or does not holdcode, return[-1, -1].
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Do not look for the postcode. Look for the two edges of its stretch, each with its own binary search.
Trace [2040, 2040, 3115, 3115, 3115, 3120, 4500] with code 3115.
First search, condition v >= 3115:
lo = 0,hi = 7,mid = 3: 3115 qualifies.hi = 3.lo = 0,hi = 3,mid = 1: 2040 does not.lo = 2.lo = 2,hi = 3,mid = 2: 3115 qualifies.hi = 2. Stop:first = 2, and it really holds 3115.
Second search, condition v > 3115:
lo = 0,hi = 7,mid = 3: 3115 does not qualify.lo = 4.lo = 4,hi = 7,mid = 5: 3120 qualifies.hi = 5.lo = 4,hi = 5,mid = 4: 3115 does not.lo = 5. Stop: the stretch ends at 5 - 1 = 4.
The answer is [2, 4]. The check after the first search matters: when the code is missing, the first search still returns a position (where the code would go), so you must confirm that position actually holds it.
function findStretch(postcodes, code) {
// first index where isTrue(value) holds, or n if none
const firstIndex = (isTrue) => {
let lo = 0, hi = postcodes.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (isTrue(postcodes[mid])) hi = mid;
else lo = mid + 1;
}
return lo;
};
const first = firstIndex((v) => v >= code);
if (first === postcodes.length || postcodes[first] !== code) return [-1, -1];
const afterLast = firstIndex((v) => v > code);
return [first, afterLast - 1];
}def find_stretch(postcodes, code):
# first index where is_true(value) holds, or n if none
def first_index(is_true):
lo, hi = 0, len(postcodes)
while lo < hi:
mid = (lo + hi) // 2
if is_true(postcodes[mid]):
hi = mid
else:
lo = mid + 1
return lo
first = first_index(lambda v: v >= code)
if first == len(postcodes) or postcodes[first] != code:
return [-1, -1]
after_last = first_index(lambda v: v > code)
return [first, after_last - 1]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.