Searching for shortest slice in an array with all unique values, how to do this in optimal way?

Question

I have an array that contains N elements, which values are in 0 <= value < N range and can be discontinuous. For this array I need to find a slice which will contain all unique values and at the same time it will be the shortest slice that will meet the above criterion.

An example, for array {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8} with 5 unique values {1, 2, 3, 4, 8} we are talking about slice {2, 1, 4, 3, 4, 8} with length 6.

Is there an optimal way to do this? As for now I've naive implementation that has far too high complexity (nested loops). I've tried to come up with an idea for an algorithm to do this in an optimal way but sadly to no avail. As for now I've tried to come up with something that will make use of occurrences for each unique value when looping through array, but still my mind is not clear enough. Any ideas are welcome, this problem is troubling me for a long time. :) Thank you in advance.

Best regards

Answer 1

The first run collects possible values and creates a map with pairs (value; counter = 0). Let Nis map size

For the second run prepare two indexes - left and right, and ActiveCnt.

Move right, updating map counters. When you update zero counter, increment ActiveCnt. When ActiveCnt becomes equal to N, stop.

Now move left, decrementing map counters. When some counter becomes zero, get difference between right and left, compare it with current MinLength, then decrement ActiveCnt. Continue with right index and so on.