Find the maximum length subarray condition 2 * min > max

Question

This was an interview question I was recently asked at Adobe:

In an array, find the maximum length subarray with the condition 2 * min > max, where min is the minimum element of the subarray, and max is the maximum element of the subarray.

Does anyone has any approach better than O(n^2)?
Of course, we can't sort, as a subarray is required.

Below is my O(n^2) approach:

max=Integer.MIN_VALUE;
for (int i=0; i<A.length-1;i++)
  for(j=i+1;j<A.length;j++)
  {
    int min =findMin(A,i,j);
    int max =findMAx(A,i,j);
    if(2*min<=max) {
      if(j-i+1>max) 
        max = j-i+1
    }
  }

Does anybody know an O(n) solution?

I incorporated additional info from the comments and reorganized the whole question in the attempt to make it more digestible. — zx485
Your solution is actually O(n³) rather than O(n²); you forgot to take into account the cost of findMin and findMax, which would be linear unless you built something extra to make it faster. That said, it's not hard to improve your solution to be in O(n²), by incrementally adjusting min and max as j iterates over the array rather than recomputing them from scratch on each iteration. — ruakh
FWIW, although an O(n) solution seems like a tall order, I see an O(n log n) solution: if you use heaps or a red-black tree to help keep track of min and max, you can write a while-loop that increments j whenever possible without violating the criterion, and increments i whenever incrementing j is not possible without violating the criterion. — ruakh
I doubt that using heaps will give you O(n log n). Would you use a min and a max heap? If you encounter a number that is too small, you would have to remove all maxes that violate the constraint from both heaps and take the highest index + 1 to get the new start point. Or am I missing something? — maraca
@maraca: If you're replying to a comment of mine, and you want me to see the reply, you should start with the comment with @ruakh: so it shows up in my inbox. (It's only by chance that I saw your reply here.) But to answer your question -- yes, you'd use a min-heap and a max-heap, and yes, you'd sometimes need to remove a whole bunch of elements at once. But any given element is only added at most once and removed at most once, so when you add up all the steps, they come out to O(n log n). (Note that log n + 0 + 0 + 0 = log n.) — ruakh

ruakh ruakh · Accepted Answer · 2020-03-18T00:59:31

Let A[i…j] be the subarray consisting of A[i], A[i+1], … A[j].

Observations:

If A[i…j] doesn't satisfy the criterion, then neither does A[i…(j+1)], because 2·min(A[i…(j+1)]) ≤ 2·min(A[i…j]) ≤ max(A[i…j]) ≤ max(A[i…(j+1)]). So you can abort your inner loop as soon as you find a j for which condition is not satisfied.
If we've already found a subarray of length L that meets the criterion, then there's no need to consider any subarray with length ≤ L. So you can start your inner loop with j = i + maxLength rather than j = i + 1. (Of course, you'll need to initialize maxLength to 0 rather than Integer.MIN_VALUE.)

Combining the above, we have:

int maxLength = 0;
for (int i = 0; i < A.length; ++i) {
    for (int j = i + maxLength; j < A.length; ++j) {
        if (findMin(A,i,j) * 2 > findMax(A,i,j)) {
            // success -- now let's look for a longer subarray:
            maxLength = j - i + 1;
        } else {
            // failure -- keep looking for a subarray this length:
            break;
        }
    }
}

It may not be obvious at first glance, but the inner loop now goes through a total of only O(n) iterations, because j can only take each value at most once. (For example, if i is 3 and maxLength is 5, then j starts at 8. If we A[3…8] meets the criterion, we increment maxLength until we find a subarray that doesn't meet the criterion. Once that happens, we progress from A[i…(i+maxLength)] to A[(i+1)…((i+1)+maxLength)], which means the new loop starts with a greater j than the previous loop left off.)

We can make this more explicit by refactoring a bit to model A[i…j] as a sliding-and-potentially-expanding window: incrementing i removes an element from the left edge of the window, incrementing j adds an element to the right edge of the window, and there's never any need to increment i without also incrementing j:

int maxLength = 0;
int i = 0, j = 0;
while (j < A.length) {
    if (findMin(A,i,j) * 2 > findMax(A,i,j)) {
        // success -- now let's look for a longer subarray:
        maxLength = j - i + 1;
        ++j;
    } else {
        // failure -- keep looking for a subarray this length:
        ++i;
        ++j;
    }
}

or, if you prefer:

int maxLength = 0;
int i = 0;
for (int j = 0; j < A.length; ++j) {
    if (findMin(A,i,j) * 2 > findMax(A,i,j)) {
        // success -- now let's look for a longer subarray:
        maxLength = j - i + 1;
    } else {
        // failure -- keep looking for a subarray this length:
        ++i;
    }
}

Since in your solution, the inner loop iterates a total of O(n²) times, and you've stated that your solution runs in O(n²) time, we could argue that, since the above has the inner loop iterate only O(n) times, the above must run in O(n) time.

The problem is, that premise is really very questionable; you haven't indicated how you would implement findMin and findMax, but the straightforward implementation would take O(j−i) time, such that your solution actually runs in O(n³) rather than O(n²). So if we reduce the number of inner loop iterations from O(n²) to O(n), that just brings the total time complexity down from O(n³) to O(n²).

But, as it happens, it is possible to calculate the min and max of these subarrays in amortized O(1) time and O(n) extra space, using "Method 3" at https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/. (Hat-tip to גלעד ברקן for pointing this out.) The way it works is, you maintain two deques, minseq for calculating min and maxseq for calculating max. (I'll only explain minseq; maxseq is analogous.) At any given time, the first element (head) of minseq is the index of the min element in A[i…j]; the second element of minseq is the index of the min element after the first element; and so on. (So, for example, if the subarray is [80,10,30,60,50] starting at index #2, then minseq will be [3,4,6], those being the indices of the subsequence [10,30,50].) Whenever you increment i, you check if the old value of i is the head of minseq (meaning that it's the current min); if so, you remove the head. Whenever you increment j, you repeatedly check if the tail of minseq is the index of an element that's greater or equal to the element at j; if so, you remove the tail and repeat. Once you've removed all such tail elements, you add j to the tail. Since each index is added to and removed from the deque at most once, this bookkeeping has a total cost of O(n).

That gives you overall O(n) time, as desired.

Find the maximum length subarray condition 2 * min > max

3 Answers