The subrange puzzle I posted yesterday came from this Stack Overflow post. My original response contained the algorithm below, in a slightly different form. It also contained a bug in that it didn’t handle the case where the end of the longest subrange was also the end of the array. An oversight.

My solution is based on the insight that in a sorted array, if a[start]+r >= a[end], then a[start+1]+r is, too. Provided that start <= end.

So if I start at the beginning of the array with start = end = 0 and move the end index forward until a[0]+r < a[end], I’ve found my first “longest subrange.” Then, I increment start. At this point, I know that the values a[1] through a[end-1] satisfy the conditions. They have to because the array is sorted, meaning that a[1] >= a[0].

I don’t have to check the values between a[1] and a[end-1] to see if they’re in the new subrange. I already know that they are.

The algorithm does a single pass through the array, incrementing end until a[start]+r < a[end], then incrementing start until a[start]+r >= a[end].

The result is that the algorithm never makes more than 2*n comparisons, where n is the number of items in the array. The actual number of comparisons will be approximately (2*n)-length, where length is the length of the longest run. The algorithm also uses constant extra space regardless of the size of the array or the value of r.

Here’s the code in C#.

    int FindRange(int[] a, int r, out int length)
    {
        int start = 0;
        int maxIndex = 0;
        int matchLength = 0;
        length = 0;
        for (int end = 0; end < a.Length; ++end)
        {
            if (a[end] > a[start] + r)
            {
                matchLength = end - start;
                if (matchLength > length)
                {
                    length = matchLength;
                    maxIndex = start;
                }
                // move forward until within range
                do
                {
                    ++start;
                } while (a[end] > a[start] + r);
            }
        }
        // Final check, from a[start] to end of array
        matchLength = a.Length - start;
        if (matchLength > length)
        {
            length = matchLength;
            maxIndex = start;
        }
        return maxIndex;
    }

This problem is somewhat similar to the Maximum subarray problem from Jon Bentley’s Programming Pearls, which I read and worked through the puzzles almost 20 years ago. Although I didn’t recognize it as such at the time, I suspect that the time I spent solving that problem (and other puzzles) back then helped me to solve this one in just a few minutes. The disturbing thing, though, is that I at first said that the algorithm was O(n²) in the worst case. I had to clean up the code before I realized that it was O(n). Weird.

One might ask why I spend time on these puzzles. There are several answers. First, I find them interesting. Some people like Sudoku, crossword puzzles, and chess. I like algorithm puzzles. They help me relax and they also sharpen my skills. And some of the puzzles are real-world problems. Many times in my career I’ve used some of the techniques learned from doing these puzzles to drastically reduce the running time of a critical application.