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.

Data Structures

Data structures are different ways of storing data. After various years of research many people have come up with the following different kind of DS. These different DS are used based on the requirement. DS is chosen based on the problem.

In this blog we will look at the different structures which are helpful to tackle various computing problem. I have tried to put little information about all DS available, In future I will try to explain each one of them with their various versions. Hope it will help me to understand DS more.

Data Structure	Fields	Operations	Time Complexity	Pros	Cons	Comments
Array	MAX_CAPACITY	add(index, value) – On the specified index add the value.	O(1)	Index based Retrieval	1. Fixed Size of Array.	Arrays are the oldest and most DS. It is used to implement most of the other datastructures.
	index	delete(index) – Delete at specified index.	O(1)		2. Complex position based insertion
	objects[]	search(value) – Search the value.	O(n)		3. One block Allocation. It is not possible to use scattered memory with arrays
Linked List	Node{ Data, nextNode}	Insert – Add value at head.	O(1)	1. Linear Access	1. Retrieval at any index is slower wrt to Arrays.
	head of Node type	Delete – Search and delete the value.	O(n)	2. Does not need continuous memory locations.	2. Complex to use.	Linked list are useful when user is concentrating on insert operation instead index based retrieval.
		Search – Search the value.	O(n)	3. Size of the list is not fixed.
Stacks	MAX_CAPACITY	IsEmpty – If CURRENT_INDEX = -1	O(1)			Stacks works on last in first out methodology... Stacks are widely used in computer programming.
	CURRENT_INDEX	isFull CURRENT_INDEX = MAX_CAPACITY	O(1)			Stacks are used to validate compile time programs.
	objects[]	Push – Insert a object in array.	O(1)			Infix/postfix/prefix evaluation is done using stacks.
		Pop – removes a object and returns its value.	O(1)
Queue	MAX_CAPACITY	isEmpty – If HEAD = TAIL	O(1)			Queue works on First In/First out methodology.
	HEAD	isFull |HEAD - TAIL| = MAX_CAPACITY	O(1)			Queue are used to maintain threads.
	TAIL	Enqueue – inserting the record at head.	O(1)
	objects[]	Dequeue – Deletng the record from tail.	O(1)
Tree	Node{ Data, Node1, Node2, Node3 ....}	add(value) – Based on property of the tree add the node accordinly.	O(log(n))	1. Insertion is faster than array but slower than linked list.	1. Difficult to maintain the balance of the tree.	Trees are used for solving lot of algorithmic problems. It is known as most important and efficient data structure to solve multiple issues.
	depth	Delete – Search and delete the value.	O(n)	2. Searching is faster.	2. Complex and confusion at times.
	Leaves – Nodes which do not have any children.	Search – Search the value.	O(log(n))	3. Used with lot of different data structures.
	Internal Nodes – Nodes having one or more children.			4. Solves lot of problems.
Graph	Map of vertices and it's accessible vertices.	adjacent(G, x, y): tests whether there is an edge from node x to node y.	O(K)			Graphs are generally used for greedy solutions.
		neighbors(G, x): lists all nodes y such that there is an edge from x to y.	O(K)			Shortest path algorithms.
		add(G, x, y): adds to G the edge from x to y, if it is not there.	O(K)
		delete(G, x, y): removes the edge from x to y, if it is there.	O(1)
HashTable	objects[]	add(value) – Adds the value to the array.	O(1)	Fast searching operations are performed.	Need efficient hashing algorithms, otherwise it can be painful to search objects.	It is widely used in Database Indexing and caching operations.
	MAX_SIZE	delete(value) – Removes the value from the array.	O(1)	Used when program deals with huge chunk of data.
		Search(value)	O(1)