title: Minimum window of days required to travel all cities
body: <p>This is an interesting question that I came across in a coding challenge:</p>
  
  <p>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. </p>
  
  <p><strong>Input</strong> :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.</p>
  
  <p>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. </p>
  
  <p><strong>Output</strong>:4 Because it took you 4 days to visit all the cities at least once</p>
  
  <p><strong>My solution</strong> : 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?</p>
  
  <pre><code>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&lt;len(A):
          index2=index1
          prevday=index2
          ans=0
          count1=0
          while index2&lt;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
  </code></pre>