Find minimum sub-array which has 1 to k numbers in java

Suppose we have one array:

4, 5, 6, 7, 1, 2,1,, 4, 5, 3, 6, 7, 10, 1, 2, 3, 4

And k=4, that means we have to find the sub array which has all the elements 1, 2, 3, 4

and the array length should be minimum.

Intuition: First we will just find the index till where we can get all the numbers then we will proceed to minimize the size of the sub-array.

So as we can see till index 9 we can get all the desired numbers. Then we will try to minimize this length. And by minimizing means we can get another sub array which is minimum as in this case which is: 1,2,3,4 at last in the array.

So we go ahead using this method we can get the minimum sub array having 1 to k numbers.

Code in Java:

public class NumbersfromOnetoK {
    public static void main(String[] args) {
 NumbersfromOnetoK m = new NumbersfromOnetoK();
        int[] arr={4, 5, 6, 1, 7, 1, 2, 4, 5, 3, 6, 7, 10, 1, 2, 3, 4}; 
        int k=4;
        m.findSubArrayWith_1_to_K_Numbers();
    }


    private void findSubArrayWith_1_to_K_Numbers(int[] arr, int k){
 int strtInd=0,endInd=0,digCount=0;
 int[] kArr=new int[k+1];
        /*
  * First find the sub array in which 1 to k number exist, it may 
  * not be the minimal
  * */
 for(int i=0;i<arr.length;i++){  
     if(arr[i] <=k && arr[i] >=1){
  if(kArr[arr[i]]==0) digCount++;    // count of digits from 1...k
  kArr[arr[i]]++;
  if(digCount == k) {endInd=i;break;}
     }
 }
 
 int min_len=endInd-strtInd+1; // initially we let this is min 
        int tempInd=endInd;
 int i=strtInd;
 
        while(tempInd<arr.length){
     if(arr[i]<=k){
  kArr[arr[i]]--;
  if(kArr[arr[i]] == 0){
      kArr[arr[i]]++; // retain digits's count

                    // calculating new minimum
      if(tempInd-i+1 < min_len){
   min_len=tempInd-i+1;
   strtInd=i;endInd=tempInd;
      }
                    
                    // increase tempInd when it is under array length
      if(tempInd < arr.length)
   tempInd++;

                    // skipping nos which are not in range 1..k
      while(tempInd < arr.length && arr[tempInd] > k)tempInd++;

      // if no is in 1..k then increment its count in kArray
                    if(tempInd < arr.length)
   kArr[arr[tempInd]]++;
  }
  else
       i++; // increase i when the dig count in not reduced
     }
     else
  i++; // increase i if no is out of range 1..k
     
 }
        //print start and end index of sub array
 System.out.println(strtInd+" "+endInd+" len="+min_len); // final answer
    }
}

Time Complexity : O(n) 
Space Complexity : O(k) 

Logic: The whole logic includes below points:

Phase 1:

1. make an array of size k+1 to store count of numbers from 1..k , skipping index 0 as we are not including 0 Array name in code is : kArr 
2. Run the loop and increase count as : kArr[arr[i]]++; 
3. Also unique digits(under 1..k) count using digCount 
4. When diCount becomes k then stop the loop. 

Phase 2:

1. Assign the below values to variables: tempInd = end index where we have stopped the loop min_len = endInd - strtind +1 ; i = strtInd; 
2. Run a while loop till the end of array in search of minimum length of sub-array containing 1..k
3. Treat the sub-array which we got from phase 1 as window. 
4. Now we will try to decrease window from left as in our case after phase 1 we have kArray as (digit - count): endInd = 9, strtInd = 0, min_len = 11 1 - 2, 2 - 1, 3 - 1, 4 - 2 
5. When we try to reduce the window, we have 4 on left so reducing the count is not making the count of 4 as 0 in kArray so that means we can reduce the window. kArray : 1 - 2, 2 - 1, 3 - 1, 4 - 1 and index i = 4 
6. Now we will increment i=1 from i=0; 
7. We again try to decrease window from left, we get 5 which is not our number, index i = 2 
8. We got 6 which is again not our number(in range 1..k) and index i = 3 
9. We got 1, can we reduce it ? Yes as we have count = 2 for 1 The kArray : 1 - 1, 2 - 1, 3 - 1, 4 - 1 and index i = 4 
10. Again we try to reduce, at i = 4 we have 7 so just increment i at i = 5 we have 1, but when we try to reduce the count in kArray will become 0 for 1 
11. That means we cannot reduce from left now.
12. So we will increase the window from right And we will accommodate new numbers(in 1..k) in search of minimum sub-array 
13. Update minimum length if possible 
14. In this case we have skipped number 6, 7, 10 as they are out of range. 
15. And tempInd increased to 13 and we got 1 so we incremented count of 1 from 1 to 2The kArray : 1 - 2, 2 - 1, 3 - 1, 4 - 1 
16. And again we will try to decrease window from left 
17. Means we can as i = 5 is 1 and we can decrease count of 1 to 1 from 2, index i = 6 
18. Now again try to decrease window from left, i = 6 is 2 The kArray : 1 - 1, 2 - 1, 3 - 1, 4 - 1 and index i = 6 
19. Count in kArray for 2 will become 0, so we will update min_len 
20. And then increase window to right 
21. We got 2 at tempInd = 14 and increase count of 2 in kArray: The kArray : 1 - 1, 2 - 2, 3 - 1, 4 - 1 and index i = 6, tempInd = 14 
22. Now we can decrease window form left so : The kArray : 1 - 1, 2 - 1, 3 - 1, 4 - 1 and index i = 7 
23. @Index i = 7, we have 4, when we try to decrease window from left count of 4 will become 0 so we will try to increase window from right 
24. Update min_len, increment tempInd to 15 and we get number 3, The kArray : 1 - 1, 2 - 1, 3 - 2, 4 - 1 and index i = 7 
25. We can't decrease window from left as same problem described in point 25 
26. Update min_len, increment tempInd to 16 and we get number 4 The kArray : 1 - 1, 2 - 1, 3 - 2, 4 - 2 and index i = 7 
27. Now we can reduce array from left and index i = 8 The kArray : 1 - 1, 2 - 1, 3 - 2, 4 - 1 and index i = 8 
28. Again try to reduce from left: YES we can The kArray : 1 - 1, 2 - 1, 3 - 1, 4 - 1 and index i = 9
29. And i will get incremented to 12 as numbers are out of range. 
30. Now when we will try to decrease window from left which we cannot 
31. Update minimum length which is min_len= tempInd - i +1 = 16 - 13 + 1 = 4 
32. We increase tempInd but tempInd will become 17 which is > arr.length 
33. We come out of the while loop, print the strtInd and endInd updated during the process and length of the sub-array. 

Thanks for Reading! 
Have a good one :)