23

Suppose you have an array of numbers, and another set of numbers. You have to find the shortest subarray containing all numbers with minimal complexity.

The array can have duplicates, and let's assume the set of numbers does not. It's not ordered - the subarray may contain the set of number in any order.

For example:

Array: 1 2 5 8 7 6 2 6 5 3 8 5
Numbers: 5 7

Then the shortest subarray is obviously Array[2:5] (python notation).

Also, what would you do if you want to avoid sorting the array for some reason (a la online algorithms)?

5
  • I presume the array can have duplicates?
    – Josh
    Mar 27, 2011 at 6:12
  • what is the range of the numbers? Mar 27, 2011 at 6:12
  • The "another set of numbers" is unordered? With no duplicates (since it is a set)?
    – Ted Hopp
    Mar 27, 2011 at 6:13
  • Give some relevant example of array. Mar 27, 2011 at 6:13
  • ...by python notation do you mean index 2 to 5 excluding 5?
    – flight
    Mar 27, 2011 at 6:24

6 Answers 6

20

Proof of a linear-time solution

I will write right-extension to mean increasing the right endpoint of a range by 1, and left-contraction to mean increasing the left endpoint of a range by 1. This answer is a slight variation of Aasmund Eldhuset's answer. The difference here is that once we find the smallest j such that [0, j] contains all interesting numbers, we thereafter consider only ranges that contain all interesting numbers. (It's possible to interpret Aasmund's answer this way, but it's also possible to interpret it as allowing a single interesting number to be lost due to a left-contraction -- an algorithm whose correctness has yet to be established.)

The basic idea is that for each position j, we will find the shortest satisfying range ending at position j, given that we know the shortest satisfying range ending at position j-1.

EDIT: Fixed a glitch in the base case.

Base case: Find the smallest j' such that [0, j'] contains all interesting numbers. By construction, there can be no ranges [0, k < j'] that contain all interesting numbers so we don't need to worry about them further. Now find the smallestlargest i such that [i, j'] contains all interesting numbers (i.e. hold j' fixed). This is the smallest satisfying range ending at position j'.

To find the smallest satisfying range ending at any arbitrary position j, we can right-extend the smallest satisfying range ending at position j-1 by 1 position. This range will necessarily also contain all interesting numbers, though it may not be minimal-length. The fact that we already know this is a satisfying range means that we don't have to worry about extending the range "backwards" to the left, since that can only increase the range over its minimal length (i.e. make the solution worse). The only operations we need to consider are left-contractions that preserve the property of containing all interesting numbers. So the left endpoint of the range should be advanced as far as possible while this property holds. When no more left-contractions can be performed, we have the minimal-length satisfying range ending at j (since further left-contractions clearly cannot make the range satisfying again) and we are done.

Since we perform this for each rightmost position j, we can take the minimum-length range over all rightmost positions to find the overall minimum. This can be done using a nested loop in which j advances on each outer loop cycle. Clearly j advances by 1 n times. Since at any point in time we only ever need the leftmost position of the best range for the previous value of j, we can store this in i and just update it as we go. i starts at 0, is at all times <= j <= n, and only ever advances upwards by 1, meaning it can advance at most n times. Both i and j advance at most n times, meaning that the algorithm is linear-time.

In the following pseudo-code, I've combined both phases into a single loop. We only try to contract the left side if we have reached the stage of having all interesting numbers:

# x[0..m-1] is the array of interesting numbers.
# Load them into a hash/dictionary:
For i from 0 to m-1:
    isInteresting[x[i]] = 1

i = 0
nDistinctInteresting = 0
minRange = infinity
For j from 0 to n-1:
    If count[a[j]] == 0 and isInteresting[a[j]]:
        nDistinctInteresting++
    count[a[j]]++

    If nDistinctInteresting == m:
        # We are in phase 2: contract the left side as far as possible
        While count[a[i]] > 1 or not isInteresting[a[i]]:
            count[a[i]]--
            i++

        If j - i < minRange:
            (minI, minJ) = (i, j)

count[] and isInteresting[] are hashes/dictionaries (or plain arrays if the numbers involved are small).

6
  • Can you explain how do you populate the isInteresting[] array in O(n) time? [I am assuming that the array size is n, and the set of interesting elements has m elements.]
    – Josh
    Mar 28, 2011 at 23:30
  • @Josh: As I say at the bottom, isInteresting[] is a hash or dictionary so lookups are O(1). My code doesn't currently show it getting populated -- I'll fix that in a moment. That step will take O(m) time, and m < n (since otherwise there are definitely no solutions), so the whole thing is O(n). Mar 29, 2011 at 2:13
  • Its difficult to justify the line isInteresting[x[i]] = 1 since the question never mentions that numbers are themselves small. (Suddenly becomes a pseudopolynomial solution.)
    – Josh
    Mar 29, 2011 at 4:13
  • @Josh: I don't understand -- all that line does is insert an element into a hash, which is O(1). What is the problem exactly? Mar 30, 2011 at 13:50
  • @j_random_hacker: As it is written, isInteresting is an array. So, say x[i] = 23082038402834, then you need an array that big. Of course, that is not what is meant. What you really mean is to put it into a hash, but then hashes are implemented using linked lists to hold the collisions. So, you can set this value in O(1) time, by adding to the front of the list, which is fine. But then, where you check isInteresting in the if block, that is not guaranteed to be O(1). That may be O(log n), or worse, O(n), if you have too many collisions.
    – Josh
    Mar 30, 2011 at 22:46
6

This sounds like a problem that is well-suited for a sliding window approach: maintain a window (a subarray) that is gradually expanding and contracting, and use a hashmap to keep track of the number of times each "interesting" number occurs in the window. E.g. start with an empty window, then expand it to include only element 0, then elements 0-1, then 0-2, 0-3, and so on, by adding subsequent elements (and using the hashmap to keep track of which numbers exist in the window). When the hashmap tells you that all interesting numbers exist in the window, you can begin contracting it: e.g. 0-5, 1-5, 2-5, etc., until you find out that the window no longer contains all interesting numbers. Then, you can begin expanding it on the right hand side again, and so on. I'm quite (but not entirely) sure that this would work for your problem, and it can be implemented to run in linear time.

10
  • This sounds indeed in the right direction, but I can't find the specific formulation for it.
    – R S
    Mar 27, 2011 at 6:27
  • @R S: Try it out on paper and see if it helps. :-) Don't worry about getting it to run in linear time; that is achieved with a little trick that can be added later without changing how the main algorithm works. So for each number you add to / remove from the window, update the hashmap (which, on paper, can just be a table of number frequencies) and see if all interesting numbers are present. I'm on my way to bed now (guess this was a bad time to post anything), but if you get stuck, post your progress so far, and I (or someone else) can take a look at it tomorrow. Mar 27, 2011 at 6:39
  • Can you explain a bit more why you think it would be linear time? My solution (below/above) solves this in O((m+n) log n) time, and I am interested in knowing if indeed a linear time algorithm is possible.
    – Josh
    Mar 27, 2011 at 15:01
  • @Josh (and @R S): Assuming that the sliding window approach is correct, the trick to achieving linear time is to observe that the purpose of the hashmap is to repeatedly answer the question "does the current window contain all interesting numbers?". Let k be the size of the set of interesting numbers, and let m be the number of nonzero entries in the hashmap (that is, the number of nonzero interesting-number-occurrences in the current window). Then, the question can be rephrased as "Is m = k?". (Continues in the next comment.) Mar 27, 2011 at 16:13
  • (Cont.) Note that k can be maintained in constant time per window expansion/contraction: when we expand the window, we check the hashmap entry for the new number. If it is zero, we increment m, because we now have a number that we didn't have before. When we contract the window, we check the hashmap entry for the number that we remove, and if it goes from 1 to 0, it means that we have now "lost" a number, so we decrement m. (Continues) Mar 27, 2011 at 16:18
0

Say the array has n elements, and set has m elements

Sort the array, noting the reverse index (position in the original array)
// O (n log n) time

for each element in given set
   find it in the array
// O (m log n) time  - log n for binary serch, m times

keep track of the minimum and maximum index for each found element

min - max defines your range

Total time complexity: O ((m+n) log n)

3
  • what do you mean by min - max? What/which min and max? And what do you do about duplicates?
    – flight
    Mar 27, 2011 at 6:25
  • Oh wait... I get the min-max. I was confused only because your solution doesn't take into account duplicates.
    – flight
    Mar 27, 2011 at 6:32
  • Recording just the minimum and maximum indices for each number isn't sufficient, because if a number appears 3 or more times, the shortest subarray will not necessarily contain the leftmost or rightmost occurrence of it. E.g. What is the shortest subarray containing { 1, 2, 3 } in 3, 1, 2, 3, 3? Answer: [1, 4], which doesn't use the minimum or maximum position of 3. Mar 28, 2011 at 7:57
0

This solution definitely does not run in O(n) time as suggested by some of the pseudocode above, however it is real (Python) code that solves the problem and by my estimates runs in O(n^2):

def small_sub(A, B):
    len_A = len(A)
    len_B = len(B)

    sub_A = []
    sub_size = -1
    dict_b = {}

    for elem in B:
        if elem in dict_b:
            dict_b[elem] += 1
        else:
            dict_b.update({elem: 1})

    for i in range(0, len_A - len_B + 1):
        if A[i] in dict_b:
            temp_size, temp_sub = find_sub(A[i:], dict_b.copy())

            if (sub_size == -1 or (temp_size != -1 and temp_size < sub_size)):
                sub_A = temp_sub
                sub_size = temp_size

    return sub_size, sub_A

def find_sub(A, dict_b):
    index = 0
    for i in A:
        if len(dict_b) == 0:
            break

        if i in dict_b:
            dict_b[i] -= 1

            if dict_b[i] <= 0:
                del(dict_b[i])

        index += 1

    if len(dict_b) > 0:
        return -1, {}
    else:
        return index, A[0:index]
0

Here's how I solved this problem in linear time using collections.Counter objects

from collections import Counter

def smallest_subsequence(stream, search):
    if not search:
        return []  # the shortest subsequence containing nothing is nothing

    stream_counts = Counter(stream)
    search_counts = Counter(search)

    minimal_subsequence = None

    start = 0
    end = 0
    subsequence_counts = Counter()

    while True:
        # while subsequence_counts doesn't have enough elements to cancel out every
        # element in search_counts, take the next element from search
        while search_counts - subsequence_counts:
            if end == len(stream):  # if we've reached the end of the list, we're done
                return minimal_subsequence
            subsequence_counts[stream[end]] += 1
            end += 1

        # while subsequence_counts has enough elements to cover search_counts, keep
        # removing from the start of the sequence
        while not search_counts - subsequence_counts:
            if minimal_subsequence is None or (end - start) < len(minimal_subsequence):
                minimal_subsequence = stream[start:end]
            subsequence_counts[stream[start]] -= 1
            start += 1

print(smallest_subsequence([1, 2, 5, 8, 7, 6, 2, 6, 5, 3, 8, 5], [5, 7]))
# [5, 8, 7]
0

Java solution

    List<String> paragraph = Arrays.asList("a", "c", "d", "m", "b", "a");
    Set<String> keywords = Arrays.asList("a","b");

    Subarray result = new Subarray(-1,-1);

    Map<String, Integer> keyWordFreq = new HashMap<>();

    int numKeywords = keywords.size();

    // slide the window to contain the all the keywords**
    // starting with [0,0]
    for (int left = 0, right = 0 ; right < paragraph.size() ; right++){

      // expand right to contain all the keywords
      String currRight = paragraph.get(right);

      if (keywords.contains(currRight)){
        keyWordFreq.put(currRight, keyWordFreq.get(currRight) == null ? 1 : keyWordFreq.get(currRight) + 1);
      }

      // loop enters when all the keywords are present in the current window
      // contract left until the all the keywords are still present
      while (keyWordFreq.size() == numKeywords){
        String currLeft = paragraph.get(left);

        if (keywords.contains(currLeft)){

          // remove from the map if its the last available so that loop exists
          if (keyWordFreq.get(currLeft).equals(1)){

            // now check if current sub array is the smallest
            if((result.start == -1 && result.end == -1) || (right - left) < (result.end - result.start)){
              result = new Subarray(left, right);
            }
            keyWordFreq.remove(currLeft);
          }else {

            // else reduce the frequcency
            keyWordFreq.put(currLeft, keyWordFreq.get(currLeft) - 1);
          }
        }
        left++;
      }

    }

    return result;
  }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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