Number of subarrays with range less than k

Issue

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?

Solution

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:)

Answered By – Stefan Haustein

Answer Checked By – Terry (AngularFixing Volunteer)

Leave a Reply

Your email address will not be published.