Here’s an interesting puzzle I ran across yesterday.

Say you have a sorted array of integers, for example:

{1, 2, 5, 7, 8, 8, 9, 12, 14, 15, 16, 17, 18, 19, 20}

You want to find the longest subrange, start..end, where a[start]+r >= a[end], and r is a constant positive integer. (Or, to put it another way, (a[end] - a[start]) <= r).

So given the array above, if r is 2, then the longest subrange would be {7, 8, 8, 9}. If r is 5, then the longest subrange would be {14, 15, 16, 17, 18, 19}.

Write a function that, given an array and a range, will return the starting index and the number of items that match. For example, in C#:

    int FindSubrange(int[] a, int r, out int length)
    {
        // do calculation
        ...
        // return values
        length = maxLength;
        return maxRangeStartIndex;
    }

This function would return index 3 and length 4 for the first example above. For the second example it would return index 8 and length 6.

The array can be of arbitrary length (potentially billions of items) and can contain any valid integer values. It is sorted, but might contain duplicate values.

There is an obvious O(n²) solution. Can you do better?

I’ll post my solution in a day or two.