Count requests in time ranges
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A request log lists arrival times in seconds, sorted from earliest to latest; several requests can share a second.
Each entry of ranges is a pair [from, to]. For each pair, count the requests with from <= t < to, and return the counts in the same order as the ranges.
There can be as many ranges as requests, so count each range without walking the log.
- 0 ≤ times.length ≤ 200,000, sorted, non-decreasing
- 0 ≤ ranges.length ≤ 200,000
- from ≤ to for every range
Examples
countInRanges([1, 3, 3, 5, 8], [[3, 6]])returns[3]Seconds 3, 3 and 5.countInRanges([1, 3, 3, 5, 8], [[0, 1], [8, 9], [6, 8]])returns[0, 1, 0]A range never includes its end.countInRanges([], [[0, 100]])returns[0]
Hints
Hint 1 of 2
The count in [from, to) is (the first index with a time at least to) minus (the first index with a time at least from).
Hint 2 of 2
Write one function, the first index whose time is at least x, with lo = 0 and hi = times.length, and call it twice per range.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Counting by walking the log is fine for one range and hopeless for 200,000 of them: that is 200,000 walks of 200,000 entries. Because the log is sorted, the requests inside [from, to) sit side by side, so the count is the distance between two positions.
Both positions are the same question: the first index whose time is at least x. Search it with lo = 0 and hi = times.length. hi starts one past the end because "no time is at least x" is a valid answer: the position after the last entry.
The to of a range is excluded, so it uses the same "at least" search as from. Searching for the first time above to instead counts requests at exactly to, which is the off-by-one the first known-wrong solution makes.
function countInRanges(times, ranges) {
const firstAtLeast = (x) => {
let lo = 0, hi = times.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (times[mid] >= x) hi = mid; else lo = mid + 1;
}
return lo;
};
return ranges.map(([from, to]) => firstAtLeast(to) - firstAtLeast(from));
}Complexity. O(log n) per range, so O(q log n) for q ranges; O(1) extra space besides the answer.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.