Algorithm: Find smallest contiguous array containing K 0's in array of 1's and 0's

I was thinking to improve my algorithmic fundamentals, so I planned to make few notes for myself that will assist me in future (Obviously at the time of Interviews). Following questions and answers have been taken from stackoverflow.com. This post is a sticky notes post for me. Please do not use the answers for reference purpose.

Following question was asked to me in an telephonic discussion with some interviewer. I had posted the question on stackoverflow where people provided me a satisfactory and efficient solution.

Problem Statement
I have array of 1's and 0's only. Now I want to find smallest contiguous subset/subarray which contains at least K 0's.

Example:

1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0

K(6) is either 0 0 1 0 1 1 0 0 0 or 0 0 0 0 1 0 1 1 0.

We have to come up with the solution where algorithm must minimize the number of iterations.

Algorithm

• In the given array, find the first occurance of 0 (say at index i).
• Keep on scanning until you've k 0's included in your window (say, the window ends at index j) Record the window Length(say j-i+1=L).
• Discard the left-most 0 at index i, and keep scanning till you get next 0 (say at index i').
• Extend the right-end of the window situated at j to j' to make the count of 0's = k again.
• If the new window-length L'=j'-i'+1 is smaller update it.

Following algorithm does not take care about the boundary conditions and all, but this can be applied to the example mentioned above.

Iteration

1. i = 3, String for K(6) 0 1 1 0 1 1 0 0 0 0, so j = 12, and l = 10.
2. i = 6, String for K(6) 0 1 1 0 0 0 0 1 0, so j = 14, and l = 9. Update
3. i = 9, String for k(6) 0 0 0 0 1 0 1 1 0, so j = 17, and l = 9. Donot update
4. i = 10, string for k(6) 0 0 0 1 0 1 1 0 0, so i = 18, and l = 9. Do not update
5. i = 11, String for k(6) 0 0 1 0 1 1 0 0 0, so I = 19, and l = 9; Do not update
6. i = 12, String for K(6) 0 1 0 1 1 0 0 0 1 1 0, so I = 22, and l = 11, do not update
7. i = 14, String for K(6) 0 1 1 0 0 0 1 1 0 0, so I = 23, and l = 10, do not update
8. i = 17, String for K(6) 0 0 0 1 1 0 0 1 0, so I = 25, and l = 9, do not update
9. i = 18, String for K(6) 0 0 1 1 0 0 1 0 0, so I = 26, and l = 9, do not update
10. i = 19, String for K(6) 0 1 1 0 0 1 0 0 0, so I = 27, and l = 9, do not update

No more iteration is available. So first string which has 6 o's and has the minimum length is selected from the array set.

Java Program

package com.number;

public class MinimumStringContainingKZeros {
 
 public String minStrHavingKZeros(String str, int k){
  int i = find(str, 1, 0);
  int j = find( str, k - 1, i + 1 );
  System.out.println( i + " && " + j);
  if( i == -1 || j == -1 ) return "";
  int i1 = i;
  int j1 = j;
  while(true){
   i1 = find(str, 1, i1 + 1);
   j1 = find(str, 1, j1 + 1);
   if( j1 == -1 ) break;
   if( j1 - i1 < j - i ){
    i = i1;
    j = j1;
   }
  }
  return str.substring(i, j + 1);
 }
 
 int find(String str, int count, int start){
  int index = start;
  while( index < str.length() ){
   if( str.charAt(index) == '0'){
    count --;
    if( count == 0 ){
     return index;
    }
   }
   index++;
  }
  return -1;
 }
}

Time Complexity

Appllication has to run through the whole characters twice, once to find the first element and another to last element.

O(n) is the time complexity of the application.

Space Complexity

No additional space is required in this algorithm.