I'm trying to optimize a function that takes a sorted list of integers and tells me what is the maximum number of elements in the list between any definite size range. To be clear, the range itself isn't given, the size of it is; the lower and upper bounds can be anything as long as they are the given distance apart.
Example:
List | Range | Output | Reason |
---|---|---|---|
[0, 1, 3, 3, 4, 5, 5, 5, 5, 5, 6, 6, 7, 8, 9] | 2 | 7 | Max of 7 elements between [5,7) |
[0, 1, 3, 3, 4, 5, 5, 5, 5, 5, 6, 6, 7, 8, 9] | 3 | 8 | Max of 8 elements tied between [3,6) & [4,7) & [5,8) |
[1, 4, 6, 9, 12, 15, 24, 25, 26, 27, 40, 42, 42, 44, 45] | 10 | 5 | Max of 5 elements between [40,50) |
I expect the list to have anywhere between 10,000 to 1,000,000 elements and the range to be rather small in comparison so optimization is the main concern. I've written the following JavaScript that reduces through the list, and filters out everything not between the range but I can't help but wonder if there's a better way to optimize it rather than using filter
since the list is sorted.
let search = (list, range) => list.reduce((maxCount, val, _, arr) => {
let rangedCount = arr.filter(x => x >= val && x < val + range).length;
if (rangedCount > maxCount) return rangedCount;
return maxCount;
}, 0);
Aren't I now iterating through the list once more for each element in it by using Array.filter
inside Array.reduce
? I'd expect that there's some better way to optimize this such as using a binary search instead of filter but - correct me if I'm wrong - a binary search could give me a random index among multiple duplicates.
Array.prototype.findIndex()
variant capitalising on from first element in an array that satisfies the provided testing function, all do: that would allow exponential search for that index. \$\endgroup\$