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.

  • 2
    Can you credit the original source for this problem? – D.W. Jun 13 at 16:43

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.

  • I don't think the maxIndex and minIndex are correct. – Labo Jun 15 at 17:40
  • @Labo Could you please explain more? – xskxzr Jun 15 at 17:45
  • You are just maintaining the largest and smallest numbers ever seen, not those between start and end. I am walking and on my smartphone so I might be wrong but this seems incorrect to me. – Labo Jun 15 at 17:47
  • @Labo I mean after an $O(n)$ preprocessing, one can query minIndex and maxIndex for any range in constant time. – xskxzr Jun 15 at 17:51
  • OK, he also needs to update that part. – Labo Jun 15 at 17:53

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.