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 locationsfor x in A:if A[x] not in hashtable1:locationcount+=1index1=0daycount=sys.maxinthashtable2={}#brute forcewhile index1<len(A):index2=index1prevday=index2ans=0count1=0while index2<len(A):if A[index2] not in hashtable2:count1+=1ans+=(index2-prevday)hashtable2[A[index2]]=1index2+=1if count1==count:daycount=min(ans,daycount)hashtable2.clear()index1+=1return daycount+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)