Visit All Places in Minimum Time

<Removed due to DMCA complaint>

The Idea: First, it is important to know what sort of problem we can reduce this too. Thinking abstractly, our goal is to find the minimum subarray in A that contains set(A). In other words, our goal is to try and find a minimum window in A that contains all the elements (vacation locations) in A.

In our algorithm, two pointers need to be maintained that form the current window (that doesn't optimally represent the solution), and a result window, which eventually will represent the optimal solution.

Initially, we need n vacation locations to visit, where n is the total amount of unique vacation location. Now comes the core algorithm: for every vacation location, we add it to our current window. We will continue to do this until the current window contains all of the required vacation days. The moment this happens one of the constraints of the problem is satisfied, but the start of our window could contain some redundant results. For example, in the process we may have encounter more than 1 vacation day. So our next task is to get rid of as much as possible from the start of the window as long as our current window contains all of the required vacation days. This will satisfy the second constraint (which is to minimize the number the total number of days for travel).

Complexity: O(2n) time and O(n) space

from collections import Counter


def solution(A):
    needed = {val: 1 for val in set(A)}
    missing = len(needed)

    # create start and end windows for the current window
    # as well as for the result window
    cur_i = result_i = result_j = 0
    for cur_j, num in enumerate(A, 1):

        # if the location hasnt been visited before 
        # subtract from visited list
        if needed[num] > 0:
            missing -= 1
        # number of times its been visited across
        needed[num] -= 1

        # once all locations are visited at least once
        # we need to minimize the length of the window
        if not missing:
            # needed[A[cur_i]] < 0 implies that there exists
            # within our window some duplicates for A[cur_i]
            # so adjust cur_i to remove these duplicates 
            while cur_i < cur_j and needed[A[cur_i]] < 0:
                needed[A[cur_i]] += 1
                cur_i += 1

            # update the maximum length of the current window
            if not result_j or cur_j - cur_i <= result_j - result_i:
                result_i, result_j = cur_i, cur_j
    return result_j - result_i