import java.util.LinkedList;
import java.util.Queue;
/*
* Question:
Given an array containing only 0s and 1s, find the minimum size of sub array containing exactly k-zeros.
Ex. 11010100011 k=4
result = 5(01000)
* Solution:
*
* Runtime: O(n)
* Space time: O(n)
*/
public class MinSubArrayQuestion1 {
public void findMinSubArr(int[] arr, int k) {
Queue
int minSubArrSize = arr.length;
for (int i = 0; i < arr.length; i++) {
if(arr[i] == 0) {
if(queue.size() != k){
queue.add(i);
}
else {
if(minSubArrSize > i - queue.peek() + 1) {
minSubArrSize = i - queue.peek() + 1;
}
queue.remove();
queue.add(i);
}
}
}
// Printing result.
if(queue.size() == k) {
System.out.print("Min SubArray : ");
for(int i = queue.peek(); queue.size() != 0; i++) {
if(i == queue.peek())
queue.remove();
System.out.print(arr[i]);
}
}
else {
System.out.println("No subarray found");
}
}
public static void main(String args[]) {
int[] arr = { 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 };
new MinSubArrayQuestion1().findMinSubArr(arr, 5);
}
}
1 comment:
There is no need for queue. We can just slide a window which contains k 0's. each time slide a window to right that include 1 zero and decrement left side of window by one zero.
Note: left most and right most part of window always points to 0, to maintain minimum window possible.
This is useful when we decrease the size of window from left
Post a Comment