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

Question

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 length of a minimal sub-array which contains all of the array's elements.

In this case, it would be 5: {7, 3, 1, 3, 4} and this 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).

I found some similar question here: Find minimum length of sub-list containing all elements of a list but it does not seem answered.

The function signature should be like: int algorithm(std::vector<int> &arr){...}

Answer 1

Find last subarray in O(n) :

For example, for the array [1, 2, 3, 2, 2, 1, 1], get the counts of the items in a hash table/Map (or array for small range) : { 1: 3, 2: 3, 3: 1 }

To find the start index of the subarray, start from the first value in the array and check if it's count is more than 1. If it's count is more than 1, decrease it's count by one, and continue to next value until a value with count of 1. Repeat the same backwards to find the last index of the subarray :

1, 2, 3, 2, 2, 1, 1
      ^        ^

Find the rest of the subarrays in O(n) :

Now to check if that is the minimum subarray, check for subarrays before it. For that, search before the first index for the last index of the value 1 that is at the last index. If it is found, change the first index to it, and decrease the last index by one :

1, 2, 3, 2, 2, 1, 1
^           ^

Now to find the last index of the new subarray, search between the first and last index for the value 2 that is at the last index and change the last index to it :

1, 2, 3, 2, 2, 1, 1
^        ^  

Repeat until the value at the last index can't be found between the first and last index :

1, 2, 3, 2, 2, 1, 1
^     ^  

Now check if the count of the new subarray is less than that of the previous subarray and update the indexes of the current minimum subarray if needed.

The search for the rest of the subarrays has to be repeated until the value at the last index can't be found before the first index.