We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each integers in the range $[1,k]$. $k$ can go up to 50, but $n$ can be large number, up to 100000.

I know that the offline version with fixed array can be solved in $O(NK)$ with sliding window across the array, but I don't know how to extend this or another algorithm to make it work online.

Please give me some hints where to start.

  • $\begingroup$ I guess I was a bit too quick about the specific time complexity. But do try to implement the sliding window algorithm in an online version. $\endgroup$ – Yuval Filmus Apr 1 '18 at 9:33
  • $\begingroup$ I don't have much experience with sliding window algorithms, is it possible to do the sliding window in online fashion, because it should scan the whole array for each update, since one number can change a lot, for example if on beginning the interval is very big, after one update it will become smaller. $\endgroup$ – someone12321 Apr 1 '18 at 17:22
  • $\begingroup$ For interval, I mean the subarray containing all integers from 1 to K $\endgroup$ – someone12321 Apr 1 '18 at 17:23
  • $\begingroup$ You should store some additional information that would help you update the data structure. $\endgroup$ – Yuval Filmus Apr 1 '18 at 17:29
  • $\begingroup$ But still, when you update one element it changes a lot, I don't see how can we reduce to updating only one single element $\endgroup$ – someone12321 Apr 1 '18 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.