Problems › TypeScript › patterns
How many readings fall in the band
A sorted column of measurements is checked against a tolerance band, and the report wants the count inside it — over millions of rows, so scanning is out.
- The readings arrive sorted ascending.
- Both ends of the band are inclusive.
- A band that runs backwards contains nothing.
- Return how many readings fall inside.
countInBand(readings: list<int>, low: int, high: int) → int
Where you start
function countInBand(readings: number[], low: number, high: number): number {
}Worked examples
| Call | Result |
|---|---|
countInBand([1,3,5,7,9], 3, 7) | 3 |
countInBand([1,3,5,7,9], 4, 4) | 0 |
countInBand([2,2,2,2], 2, 2) | 4 |
countInBand([1,2,3], 3, 1) | 0 |
Hint
Two binary searches: the first position not below the low end, and the first position above the high end. The gap between them is the answer.
Reference solution in TypeScript
function countInBand(readings: number[], low: number, high: number): number {
if (low > high) return 0;
const lowerBound = (target: number): number => {
let lo = 0;
let hi = readings.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (readings[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
};
return lowerBound(high + 1) - lowerBound(low);
}