Saturday, February 16, 2013

Find Minimum SubArray



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 queue = new LinkedList();
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:

Unknown said...

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