Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

Question

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the length of the longest subarray $A'$ in $A$ s. t. $\max(A')-\min(A') \leq k$.

For example, in the array $A = \{6, 5, 9, 10, 7, 13, 8, 7, 5, 15\}$ with $k = 6$ the algorithm must return 6, because the subarray $A' = \{9, 10, 7, 13, 8, 7\}$ has length 6 and the difference between its maximum and its minimum is no more than 6.

Another example, with $A = \{1, 3, 5, 2, 3, 1, 7\}$ with $k = 2$ the result is 3, because the subarray $A' = \{2, 3, 1\}$ has length 3 and the difference between its maximum and minimum is less or equal than 2.

So far I tried to build an algorithm that goes like this (it may be buggy, it's just a draft to make my idea of solution clear):

int test(int* arr, int len, int k) {
    int minIndex = 0;
    int maxIndex = 0;
    int start = 0;
    int end = 0;
    int maxLength = 0;
    for (int i = 1; i < len; i++) {
        end = i;
        // Update the minimum and maximum if necessary while scanning the array
        if (arr[i] < arr[minIndex])
            minIndex = i;
        if (arr[i] > arr[maxIndex])
            maxIndex = i;
        // Check the new maximum/minimum doesn't make the subarray invalid
        if (arr[maxIndex] - arr[minIndex] > k) {
            // We broke the subarray, check the length of the longest subarray until now
            if (end - start > maxLength)
                maxLength = end - start;

            // Restart from the second element, then the third, and so on
            start++;
            maxIndex = minIndex = start;
            i = start;
        }
    }

    return maxLength;
}

The main problem with this algorithm is that in the worst case it runs in $\Theta(n^2)$, which doesn't comply with the problem's requests.

Answer 1

Basic idea: Use 2 pointers to traverse the array: start and end. Both start at the beginning of the array. Try moving end one position at a time and track the maximum subarray length, until the gap is too large. When that happens, move start towards end until you have smaller gap or you meet with the end pointer (the subarray becomes empty).

How to evaluate the gap: by definition max - min of current subarray. So we keep track of min and max.

Have a min deque where you keep elements in ascending order, so that the head of the queue will be the current minimum. When encountering a new element: remove all elements larger than it from the back of the queue, then add the new element to the back of the queue. This guarantees ascending ordering.

Have a max deque where you keep elements in descending order, so that the head of the queue will be the current maximum. When encountering a new element: remove all elements smaller than it from the back of the queue, then add the new element to back of the the queue. This guarantees descending ordering.

NB: You don't keep the elements themselves in the min and max queues; instead, keep their indices in the original array! This way you have both position and value, which is important for the following step.

When the gap becomes too large: obviously you cannot increase end before first bringing start closer to it. So increate start by one. Now check the head of both queues: they are the indices of current min and current max. If any (or both) these indices are now lower than start, then they don't belong to the current subarray anymore. Drop them, the head of the queue will be the new min/max.

Continue until end reaches the end of the array.

This gives you linear complexity: each element is processed once, and added and removed at most once from each queue.

Java implementation:

public int find(int[] numbers, int maxGap) {
    int best = 0;
    int bestStart = 0, bestEnd = 0;

    Deque<Integer> minQueue = new LinkedList<>();
    Deque<Integer> maxQueue = new LinkedList<>();

    int start = 0, end = 0;

    while (end < numbers.length) {
        int x = numbers[end];

        // add end to the minQueue keeping increasing order
        while (!minQueue.isEmpty() && numbers[minQueue.peekLast()] >= x) {
            minQueue.removeLast();
        }
        minQueue.addLast(end);

        // add end to the maxQueue keeping decreasing order
        while (!maxQueue.isEmpty() && numbers[maxQueue.peekLast()] <= x) {
            maxQueue.removeLast();
        }
        maxQueue.addLast(end);

        // minimum is at the front of minQueue
        int minIdx = minQueue.peekFirst();
        int minVal = numbers[minIdx];

        // maximum is at the front of maxQueue
        int maxIdx = maxQueue.peekFirst();
        int maxVal = numbers[maxIdx];

        // check
        if (maxVal - minVal > maxGap) {
            start++;
            if (start > minQueue.peekFirst()) {
                minQueue.removeFirst();
            }
            if (start > maxQueue.peekFirst()) {
                maxQueue.removeFirst();
            }
        } else {

            // track progress
            if (end - start + 1 > best) {
                best = end - start + 1;
                bestStart = start;
                bestEnd = end;
            }

            end++;
        }
    }

    // debug
    for (int i = bestStart; i <= bestEnd; i++) {
        System.out.print(numbers[i] + " ");
    }
    System.out.println();

    return best;
}

Answer 2

If the gap of $A[i\ldots j]$ is no more than $k$, then so is $A[(i+1)\ldots j]$. So you don't need to set i back to start in the line i = start;. As a result, the running time is reduced to $O(n)$.

A notable thing is the tricky of efficiently computing minIndex and maxIndex for a range. This can be done by range minimum (maximum) query. It takes $O(n)$ preprocessing time and each query takes constant time.

Answer 3

There are two things to do:

For each start pointer find the maximal end pointer. Note that end is increasing so it's just O(n) iterations.

At each iteration, maintain the minimum and maximum value. This can be done with heaps and sets (or hash maps). The amortized complexity is O(log(k)). You may have O(log n) if you don't use hash maps.

The final complexity is thus O(n log n), and if you allow the hash maps to be O(1), O(n log k).

@xskxzr proposes an alternative way to compute the range minima and maxima, so the problem is indeed O(n). However I think the algorithm is quite complicated with Cartesian trees so O(n log k) seems to be a simpler solution.

Answer 4

def pickingNumbers(a):
    a.sort()
    c=[]
    i=0
    while (i<len(a)):
        c.append(0)
        for j in range(0,len(a)-i):
            if a[i+j]-a[i]>1:
                break
            else:c[i]+=1
        i+=1
    return max(c)