Number of subarrays with range less than k

问题:

Given an (unsorted) array S and some integer k, find the number of pairs i,j such that the range of S[i...j] < k. Where range is max(S[i...j]) - min(S[i...j]).

I received this question in an interview and was only able to come up with a O(nlogn) solution after sorting S. However, I was told there is an O(n) solution. Any ideas?

回答1:

Starting with i,j = 0, we could iterate j, keeping track of min and max. When the range becomes >= k via raising max, we need to find a new i where min(s[i..j]) > max - k (analog for the other case).

Obviously we could find this index by searching backwards from j, but we need to search forward from i to keep the runtime linear (example: 1 2 3 4 5 6 with k = 4 would backtrack several elements with backwards search in each step, while forward search makes sure each i is only considered once).

To be able to do so, we could keep two lists of indices with monotonously ascending / descending array values.

So as we iterate j in the "outer" loop, we remove all indices with values bigger than s[j] from the ascending list and then append j. Analog for the descending list. Since we always append one element and the number of removals can't exceed the number of additions, this part should still be linear.

While searching a new i with a value that is sufficiently close to the new min/max in the "inner" loop, we remove the visited elements from the front of the lists.

Edit: Code

import java.util.LinkedList;

public class Ranges {

  public static int countRanges(int[] s, int k) {
    int i = 0;
    int min = s[0];
    int max = s[0];
    LinkedList<Integer> ascending = new LinkedList();
    ascending.add(0);
    LinkedList<Integer> descending = new LinkedList();
    descending.add(0);
    System.out.println("[0...0]");
    int count = 1;
    for (int j = 1; j < s.length; j++) {
      int value = s[j];

      while (!ascending.isEmpty() && s[ascending.getLast()] > value) {
        ascending.removeLast();
      }
      ascending.add(j);

      while (!descending.isEmpty() && s[descending.getLast()] < value) {
        descending.removeLast();
      }
      descending.add(j);

      if (s[j] > max) {
        max = s[j];
        if (max - min >= k) {
          while(max - s[ascending.getFirst()] >= k) {
            ascending.removeFirst();
          }
          i = ascending.getFirst();
          min = s[i];
          while (descending.getFirst() < i) {
            descending.removeFirst();
          }
        }
      } else if (s[j] < min) {
        min = s[j];
        if (max - min >= k) {
          while(s[descending.getFirst()] - min >= k) {
            descending.removeFirst();
          }
          i = descending.getFirst();
          max = s[i];
          while (ascending.getFirst() < i) {
            ascending.removeFirst();
          }
        }
      }
      System.out.println("[" + i + "..." + j + "]");
      count += j - i + 1;  // New subarrays involving j
    }
    return count;
  }


  public static void main(String[] args) {
    final int[] s = new int[] {1, 7, 2, 3, 4, 1, 2, 5, 6};
    final int k = 3;
    System.out.println("count: " + countRanges(s, k));
  }
}

Working notes: https://i.imgur.com/G2FlSoc.jpg O:)

回答2:

You can do this with a variation of the classic 2-pointer technique. The difference is that you need to keep track of the start index of the range whose values fall within k, but also of the minimum and maximum value within this range, so that we know when the current value goes out of range (the value at the start index isn't necessarily the minimum or maximum). Another thing to note is that when the current value goes out of range, the new start index isn't necessarily indicated by the minimum or maximum value, but has to be searched by iterating backwards starting from the current index.

As KSwama pointed out, there is a possibilitiy of having to iterate backwards over the same elements multiple times, so the time complexity will not be linear. I think the worst case would mean iterating over most elements up to k times, so the complexity is probably something like O(n×k).

Set the start index to 0, and min and max to S[0]. Then, iterate over the input and for each value S[i], adjust min or max to S[i] if necessary. When you come to a value S[i] that is e.g. greater than or equal to min+k, set min and max to S[i], and then iterate backwards from i (while adjusting min) until you find a value S[j] that is less than or equal to max-k; j+1 then becomes the new start index. For each value S[i], the number of pairs it adds to the total is i-start.

Example:

S = [1,3,-1,2,5,3,6,2,4,0]  
k = 5

We start with:

i  S[p] start min  max pairs

0    1    0    1    1    -  
1    3    0    1    3    1  
2   -1    0   -1    3    2  
3    2    0   -1    3    3  
4    5  

At this point we come to a value that is larger than min+k. So we set the current value S[i] as the new min and max, and iterate backwards (while updating min) until we find the first value that is less than or equal to max-k, which is S[2]=-1; so S[3] becomes the new minimum, and 3 the new start index:

i  S[p] start min  max pairs

4    5    3    2    5    1  
5    3    3    2    5    2  
6    6    3    2    6    3  
7    2    3    2    6    4  
8    4    3    2    6    5  
9    0  

At this point we come to a value that is less than or equal to max-k. So we set min and max to 0, and iterate backwards (while updating max) until we reach S[6], which is greater than or equal to min+k, so 7 becomes the new start index; note that the new max is not S[start], but the higher value 4 that we passed on the way.

i  S[p] start min  max pairs

9    0    7    0    4    2  

And the total number of pairs is 23 (if I've understood the way they're counted correctly).

---

If you want to bring down the complexity to O(n), there are a number of options, but Stefan Haustein's answer is probably the way to go.