Algorithm To Find Shortest Continuous Subarray That Contains All Values From A Set

I have the following problem to solve: Given a set of integers, e.g. {1,3,2}, and an array of random integers, e.g. [1, 2, 2, -5, -4, 0, 1, 1, 2, 2, 0, 3,3] Find the shortest cont

Solution 1:

You are using two-pointer approach, but move both indexes only once - until the first match found. You should repeat move right - move left pattern to get the best index interval.

deffind_sub(l, s):
    left = 0
    right = 0
    ac = 0
    lens = len(s)
    map = dict(zip(s, [0]*lens))
    minlen = 100000while left < len(l):
        while right < len(l):
            curr = l[right]
            right += 1if curr in s:
                c = map[curr]
                map[curr] = c + 1if c==0:
                    ac+=1if ac == lens:
                        breakif ac < lens:
            breakwhile left < right:
            curr = l[left]
            left += 1if curr in s:
                c = map[curr]
                map[curr] = c - 1if c==1:
                    ac-=1breakif right - left + 1 < minlen:
            minlen = right - left + 1
            bestleft = left - 1
            bestright = right

    return l[bestleft:bestright]

print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 0, 3, 3], {1,3,2}))
print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1,3,2}))
>>[2, -5, -4, 3, 1]
>>[2, 1, 0, 3]

Solution 2:

You can use a sliding window approach (using a generator), the idea is to generate all subsets of size n (size of the set) to size N (size of the list), and check if any of them exists, stopping when finding the first one:

from itertools import islice, chain

defwindow(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable""   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    iflen(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result


l = [1, 2, 2, -5, -4, 3, 1, 1, 2, 0]
s = {1,3,2}

defminimum_subset(l, s):
    for w in chain.from_iterable(window(l, i) for i inrange(len(s), len(l)+1)):
        if s == set(w):
            return w
    return []

print(minimum_subset(l, s))

Result (3, 1, 1, 2) Here you have the live example

Solution 3:

This should be the most performant solution, running in O(n):

deffind_sub(l, s):
    iflen(l) < len(s):
        returnNone# Keep track of how many elements are in the interval
    counters = {e: 0for e in s}

    # Current and best interval
    lo = hi = 0
    best_lo = 0
    best_hi = len(l)

    # Increment hi until all elements are in the interval
    missing_elements = set(s)
    while hi < len(l) and missing_elements:
        e = l[hi]
        if e in counters:
            counters[e] += 1if e in missing_elements:
            missing_elements.remove(e)
        hi += 1if missing_elements:
        # Array does not contain all needed elementsreturnNone# Move the two pointers
    missing_element = Nonewhile hi < len(l):
        if missing_element isNone:
            # We have all the elementsif hi - lo < best_hi - best_lo:
                best_lo = lo
                best_hi = hi

            # Increment lo
            e = l[lo]
            if e in counters:
                counters[e] -= 1if counters[e] == 0:
                    missing_element = e
            lo += 1else:
            # We need more elements, increment hi
            e = l[hi]
            if e in counters:
                counters[e] += 1if missing_element == e:
                    missing_element = None
            hi += 1return l[best_lo:best_hi]


assert find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 0, 3, 3], {1, 3, 2}) == [2, -5, -4, 3, 1]
assert find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1, 3, 2}) == [2, 1, 0, 3]
assert find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1, 3, 7}) isNone

Solution 4:

Joining in the fun, here's my attempt. I'm not familiar with algorithm names, but this would seem like a sliding window approach based on @Netwave's description for his answer.

I = {1, 3, 2}
A = [1, 2, 2, -5, -4, 0, 1, 1, 2, 2, 0, 3, 3]

setcount = {i: 0for i in I}
stage = []
shortest = A

for i inrange(len(A)):
    # Subset
    stage.append(A[i])
    # Update the countif A[i] in I:
        setcount[A[i]] += 1while0notin setcount.values():
        # Check if new subset is shorter than existing'siflen(stage) < len(shortest):
            shortest = stage.copy()

        # Consume the head to get progressively shorter subsetsif stage[0] in I:
            setcount[stage[0]] -= 1

        stage.pop(0)


>>>print(shortest)
[1, 2, 2, 0, 3]