Given a sorted list of integers, find the highest count of elements between an indeterminate but fixed size range

Question

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.

Answer 1

Inappropriate use of iteration functions

Complexity

When the data is sorted it is a sure sign that there is a solution with less complexity than \$O(n^2)\$

The use of 'Array.reduce' and Array.filter are inappropriate and forces your solution to have a complexity of \$O(n^2)\$

The standard Array iteration functions, Array.forEach, Array.reduce, Array.filter do not provide a way to exit before the end, or start at an index above 0. It is far more convenient in performance oriented code to just use standard loops 'for', 'while', or 'do while' loops

The outer loop need only iterate to list.length - maxCount which means that in the best case the problem can be solved in \$O(n)\$

The inner loop can start at the index of the outer loop and can exit as soon as a value is outside the range. Only in the best case would it have to iterate all values.

The overall complexity to solve this problem best case is \$O(n)\$ and worst is \$O(n {log} n)\$ (my estimation)

Performance

Performance and complexity are not the same.

In performance code avoid repeating calculations. In your filter you add val + range which can be done once outside the filter. Thus if list is 1000 items long you would do an additional 999,000 needless additions.

There is no need to reassign list to arr in the reduce callback list.reduce((maxCount, val, _, arr) as the callback closes over list. In this case there is little performance gain but fast code is a habit.

Rewrite

Rewriting your solution

const search = (list, range) => list.reduce((max, val) => {
    const maxVal = val + range;
    const count = list.filter(x => x >= val && x < maxVal).length;
    return count > max ? count : max;
}, 0);

Rewriting a solution using while loops.

Using the arguments you gave the rewrite runs ~10 times faster. Though this increases dramatically as the size of list grows.

There is some ambiguity the rewrite assumes that.

• range is unsigned and can include 0

const search = (list, range) => {
    const len = list.length;
    var i = 0, max = 0;
    while (i < len - max) {
        let j = i;
        const maxVal = list[i] + range;
        while (j < len && list[j] < maxVal) { j++ }
        max = Math.max(max, j - i++);
    }
    return max;
}

Additional optimisations to consider.

• There is an early exit if range == 0 that I did not include as I don't know how likely that would be.

• If the list contains many duplicate values there is a optimisation possible, though that would increase the source code complexity by a considerable amount and not worth the effort if duplicate values are rare.

• You could also check at start (early exit) if (range > list[list.length - 1] - list[0]) { return list.length } but only if you expect range to be large often.

Answer 2

I'd establish a base line implementation for correctness tests and performance using the most simple approach to conceivably do. (For me, that would be initialising a start of range to start of list and running an end of range until value out of range, keeping index and length (end - start) of a champion.)
A performant solution may need to find indices of values different from their predecessor faster than by walking the list, one approach being exponential search, and using that to advance not only end, but start, too.

---

(I haven't done JavaScript: think about improving coding as well as algorithm.)
base line using linear searches:

/** Returns the maximum length among 
 * substrings of a non-descending sequence with last-first below range.
 */
function maxCountInRange(sequence, range) {
    const len = sequence.length;
    if (len <= 1)
        return len;
    let tail = 0, max = 1;  //, ls=0;
    while (tail < len - max) {  // && ls++ < len) {
        let head = tail + max;  // think spanworm
        let high = sequence[tail] + range;
        // linear search for a value not in "tail's" range
        while (head < len && sequence[head] < high)
            head++;
        max = Math.max(max, head - tail);
        if (len <= head)
            return max;
        let low = sequence[head] - range + 1;
        // linear search for a value in "head's" range
        while (sequence[tail] < low)
            tail++;
    }
    return max;
}

arr = [0, 1, 3, 3, 4, 5, 5, 5, 5, 5, 6, 6, 7, 8, 9];
console.log(maxCountInRange(arr, 2));
console.log(maxCountInRange(arr, 3));
arr = [1, 4, 6, 9, 12, 15.5, 24, 25, 26, 27, 40, 42, 42, 44, 45];
console.log(maxCountInRange(arr, 10));

tail touches every possible index, head skips ahead according to current max.

Hm. Not the simplest thing to read, write, or debug, but then it's how I'd handle a moderate size sequence using paper&pencil(s).