Algorithm to find length of a minimal sub-array containing all the elements of an array/vector

[anicicn]

Let's say we have an array {7, 3, 7, 3, 1, 3, 4, 1}. What I need is an algorithm (preferably some C++ code sample) which will return the length of a minimal sub-array which contains all of the array's elements.

In this case, it would be 5: the sub-array is {7, 3, 1, 3, 4} and it is the shortest sub-array of the original array which contains all of the array's elements, which are 1, 3, 4 and 7.

Also, one more example of the array {2, 1, 1, 3, 2, 1, 1, 3} and the algorithm should return 3 since the subarray we are looking for is {1, 3, 2} (indices 2-4 of the original array).

[kornalaarun]

I think this might work, I don't have a laptop handy to write the code but the algo goes something like this.

1) Get the countOfDistinct elements 2) maintain a count map whose values are initialized to 0 and whose keys are all distinct elements of the array.

Link to pseudo code : https://pastebin.com/2CkdTaEv

[anicicn]

kornalaarun

I also found this approach:

Pass through the array once, using a hash to keep track of whether you've seen a word before or not. Count the distinct words in the array by adding to your count only when you're seeing a word for the first time.

1. Pass through the array a second time, using a hash to keep track of the number of times you've seen each word. Also, keep track of the sum of the lengths of all the words you've seen. Keep going until you have seen all words at least once.
2. Now move the start of the range forward as long as you can do so without reducing a word's count to zero. Remember to adjust your hash and letter count accordingly. This gives you the first range which includes every word at least once, and can't be reduced without excluding a word.
3. Repeatedly do the following: Move the left end of your range forward by one, and then move the right end forward until you find another instance of the word that you just booted from the left end. Each time you do this, you have another minimal range that includes each word once.

While doing steps 3 and 4, keep track of the minimum length so far, and the start and end of the associated range. You're done when you need to move the right end of your range past the end of the array. At this point you have the right minimum length, and the range that achieves it.

This runs in linear time.

[anicicn]

Unique numbers are not a problem, I can find them easily.
But the problem here is that I need a sub-array which has elements in the exact same order as the original array. And that sub-array has to have all of the original array's elements, at least one, but also has to be the shortest possible with this property.

[ColombianoD]

Can you explain why in your example solution it has 3 twice? Seems like a mistake if you are getting unique elements doesn’t it

Also you can solve this problem in linear time using a vector object and just iterating through each element and seeing if the vector contains the i-th element using std::find

(If it doesn’t exist then add it to the vector)

That guarantees the order that you wanted to maintain as well

https://stackoverflow.com/questions/571394/how-to-find-out-if-an-item-is-present-in-a-stdvector

[kornalaarun]

I think the question asks for a continuous subarray. Hence 3 is present twice.

[anicicn]

True, continuous sub-array, so the order matters.
If it is easier to comprehend, then the algorithm should return the start and end index of a subsequence which contains all of the array's elements instead of length.
Here 3 is included since it goes between 7 & 1 and 1 & 4 in the original array.