Minimum window of days required to travel all cities

Question

This is an interesting question that I came across in a coding challenge:

There are k cities and n days. A travel agent is going to show you city k on day n. You're supposed to find the minimum number of days in which you can visit all cities. You're also allowed to visit cities more than once, but ideally you wouldn't want to do that since you want to minimize the number of days.

Input :You're given an array of days and cities where days are indices and cities are values. A=[7,4,7,3,4,1,7] So A[0]=7 means travel agent will show you city 7 on day 0, city 4 on day 1 etc.

So Here if you start out on day 0, you'll have visited all cities by day 5, but you can also start on day 2 and finish up on day 5.

Output:4 Because it took you 4 days to visit all the cities at least once

My solution : I do have an O(N^2) solution that tries out all combinations of cities. But the test said that the ideal time and space complexity should be O(N). How do I do this?

def findmin(A):
    hashtable1={}
    locationcount=0
    #get the number of unique locations
    for x in A:
        if A[x] not in hashtable1:
            locationcount+=1

    index1=0
    daycount=sys.maxint
    hashtable2={}
    #brute force
    while index1<len(A):
        index2=index1
        prevday=index2
        ans=0
        count1=0
        while index2<len(A):
            if A[index2] not in hashtable2:
                count1+=1
                ans+=(index2-prevday)
                hashtable2[A[index2]]=1
            index2+=1
        if count1==count:
            daycount=min(ans,daycount)
        hashtable2.clear()
        index1+=1
    return daycount+1

Order

Please show your current solution and attempts to optimise it... – Edie

Updated code, but I couldn't optimize it. – Order

Answer 1

This problem might be solved with two-pointer approach.

Some data structure should contain element counts in current window. Perhaps your hash table is suitable.

Set left and right pointer to the start of list.

Move right pointer, incrementing table entries for elements like this:

  hashtable2[A[rightindex]] = hashtable2[A[rightindex]] + 1

When all (locationcount) table entries become non-zero, stop moving right pointer. You have left-right interval covering all cities. Remember interval length.

Now move left pointer, decrementing table entries. When some table entry becomes zero, stop moving left pointer.

Move right pointer again. Repeat until the list end.

Note that indexes run the list only once, and complexity is linear (if table entry update is O(1), as hash map provides in average)

Turbulent

have you solved your solution for ex. A= [2,1,1,3,2,1,1,3] – Jordanson

I don't see potential problems with this example. The first suitable interval of indices is 0-3, the second one 2-4, it remains the best. – Turbulent

Answer 2

I had this problem in interview and failed as I thought about a moving windows too late. I took it a few days later and here is my C# solution which I think is O(n) (the array will be parsed at most 2 times).

The remaining difficulty after my flash was to understand how to update the end pointer. There's probably a better solution, my solution will always provide the highest possible starting and ending days even if the vacation could be started earlier.

    public int solution(int[] A) {

        if (A.Length is 0 or 1) {
            return A.Length;
        }

        var startingIndex = 0;
        var endingIndex = 0;
        var locationVisitedCounter = new int[A.Length];
        locationVisitedCounter[A[0] - 1] = 1;

        for (var i=1; i<A.Length; i++)
        {
            var locationIndex = A[i] - 1;

            locationVisitedCounter[locationIndex]++;

            if (A[i] == A[i - 1])
            {
                continue;
            }

            endingIndex=i;

            while (locationVisitedCounter[A[startingIndex] - 1] > 1)
            {
                locationVisitedCounter[A[startingIndex] - 1]--;
                startingIndex++;
            }

        }

        return endingIndex - startingIndex + 1;
    }

Haslet

Answer 3

Python solution

def vacation(A):
    
    # Get all unique vacation locations
    v_set = set(A)
    a_l = len(A)
    
    day_count = 0
    
    # Maximum days to cover all locations will be the length of the array
    max_day_count = a_l 
    
    for i in range(a_l):
        count = 0
        v_set_copy = v_set.copy()
        
        # Starting point to find next number of days 
        #that covers all unique locations

        for j in range(i, a_l):
            
            # Remove from set, if the location exists, 
            # meaning we have visited the location

            if (A[j] in v_set_copy):
                v_set_copy.remove(A[j])
            else:
                pass
            count = count + 1
            
            # If we have visited all locations, 
            # determine the current minimum days needed to visit all and break

            if (len(v_set_copy) == 0):
                day_count = min(count, max_day_count)
                max_day_count = day_count
                break
            
    return day_count

Psychopath

Answer 4

I solved it using two-pointer approach, pointer i is for moving the pointer forward, pointer j is to move towards getting the optimal solution. Time Complexity: O(2*N)

def solution(A):
    n = len(A)
    hashSet = dict()
    max_count = len(set(A))
    i = 0
    j = 0
    result = float("inf")

    while i < n:

        if A[i] in hashSet:
            hashSet[A[i]] += 1
        else:
            hashSet[A[i]] = 1
        if len(hashSet) == max_count:
            result = min(result, i-j)
        
        while len(hashSet) == max_count and j<=i:
            hashSet[A[j]] -= 1
            if hashSet[A[j]] == 0:
                del hashSet[A[j]]
                j+=1
            if len(hashSet) < max_count:
                break
            result = min(result, i-j)

            if result == max_count:
                return result
            j+=1
        i+=1
    return result

Holleran

Thanks, I solved the same way. – Evalynevan

Answer 5

1. from L = 0 move right until all distinct locations are visited; say R
2. maintain a map of element to frequency from L to R inclusive
3. until R == n - 1 OR L - R + 1 == distinct element count:-
4. Increase L, until we get an invalid window, i.e. map's element freq becomes 0
5. Increase R by 1 and update map.

Affrica

Answer 6

For reference, this question kind of is related to leetcode question 76.Minimum Window Substring. You can watch the solution here NeetCode. My solution in python following the same tutorial.

def solution(A):
    if not A: return
    locations = dict()
    for location in A:
        locations[location] = 0

    res,resLen = [-1,-1],float("infinity")

    # left_pointer, right_pointer
    lp,rp = 0,0
    for rp in range(len(A)):
        locations[A[rp]] = locations.get(A[rp],0) + 1
        while (0 not in locations.values()):
            if(rp - lp + 1) < resLen:
                res = [lp,rp]
                resLen = (rp-lp + 1)
            locations[A[lp]] -= 1
            lp += 1
    lp,rp = res
    return len(A[lp:rp+1]) if resLen != float("infinity") else 0

A = [7,4,7,3,4,1,7]
# A= [2,1,1,3,2,1,1,3]
# A = [7,3,2,3,1,2,1,7,7,1]
print(solution(A=A))

Peppermint

Answer 7

Although others have posted their answers, I think my solution is a little bit simpler and neater, I hope it helps.

from collections import defaultdict
from typing import List


# it is a sliding window problem
def min_days_to_visit_all_cities(arr: List[int]):
    no_of_places = len(set(arr))
    l, r = 0, 0
    place_to_count = defaultdict(int)

    res = len(arr)
    while r < len(arr):
        while r < len(arr) and len(place_to_count) < no_of_places:
            place_to_count[arr[r]] += 1
            r += 1
        while len(place_to_count) >= no_of_places:
            res = min(res, r - l)
            place_to_count[arr[l]] -= 1
            if place_to_count[arr[l]] == 0:
                del place_to_count[arr[l]]
            l += 1
    return res

Wrong