Given an integer N and an array of length N consisting of integers from 0 to N-1 may or may not contain all the integers and may contain duplicates. Find a subarray (i,j) from index i to index j such that it contains all the integers that are in the array and is of minimum length. The output is the length of such a subarry

Example: A=[2,1,1,3,2,1,1,3] so minimal subarray length =3 as A[2] to A[4] contains all the numbers

My Thoughts:

Maintain a counter array and two index start and end which contains a count of elements from the start to end index of the array. Iterate over the array each time updating the value of the counter and setting the end to the current index and incrementing start till counter[start]>1. Initially start=0, end=0

This approach seems logically correct to me. I encountered this problem during a programming test and did pass all the sample test cases. But it failed all the hidden cases. I may be missing something here.

CodePudding user response：

Parse the array once to count its distinct members.

Next, use 2 pointers. Keep a counting map of value counts between the pointers, and also keep track of the number of distinct elements between the pointers.

Any time the number of distinct elements between the pointers is too small, advance the forward pointer, o/w the rear pointer.

Keep track of and return the smallest distance between pointers that has the full count of distinct elts.

CodePudding user response：

first find number of distinct elements and then apply sliding window.

looks similiar to https://leetcode.com/problems/subarrays-with-k-different-integers/