Monthly Archives: September 2013

Maximum size square sub matrix with all 1s in a binary matrix

Given a matrix of size M x N which contains only 0s and 1s, How do we find the largest square sub-matrix which contains all 1s.

For example in the following example, highlighted portion indicates a 3×3 square sub-matrix with all 1s.


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

  
We can solve this problem using Dynamic programming approach.

We take a temporary matrix with the same size as that of original matrix. The entries of the temporary matrix are calculated using the following method.

The first row and first column of temp matrix will be same as that of original matrix.

Remaining entries are calculated using the following formula

temp[i][j] = Min( temp[i][j-1], temp[i-1][j], temp[i-1][j-1] ) + 1 
                 if matrix[i][j] = 1
           = 0 otherwise

 The logic behind this is to take the minimum of the left entry (i,j-1), top entry(i-1,j), diagonal entry(i-1,j-1) and add 1 if the current entry is 1 otherwise fill zero for that entry.

Let us assume temp[i][j] represents the bottom right corner of the largest square sub-matrix with all 1s. The value also indicates the size of that matrix.

1 0 0 1 1 0
0 1 1 1 2 0
0 1 2 2 2 1
1 0 1 2 3 0
0 1 1 0 1 1

For example, the above temp matrix indicates that there is a 3×3 sub matrix exists with all 1s. It starts from index (1,2).

Here is the Java code 

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/30/13
* Time: 6:57 AM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int nRows = 5, nCols = 6;
int[][] boolMatrix = {
{1,0,0,1,1,0},
{0,1,1,1,1,0},
{0,1,1,1,1,1},
{1,0,1,1,1,0},
{0,1,1,0,1,1}
};
printMaxSubMatrixIndex(boolMatrix, nRows, nCols);
}
public static void printMaxSubMatrixIndex(int[][] bMatrix, int nRows, int nCols)
{
int[][] temp = new int[nRows][nCols];
int i,j;
//copy the first column as it is
for( i = 0; i < nRows; i++ )
{
temp[i][0] = bMatrix[i][0];
}
//copy the first row as it is
for( i = 0; i < nCols; i++ )
{
temp[0][i] = bMatrix[0][i];
}
//calculate temp table
for( i = 1; i < nRows; i++ )
{
for( j = 1; j < nCols; j++ )
{
int minEntry = Math.min(temp[i][j-1],temp[i-1][j]);
minEntry = Math.min(minEntry, temp[i-1][j-1]);
 
                if( bMatrix[i][j] == 1)
temp[i][j] = minEntry+1;
else
temp[i][j] = 0;
}
}
//iterate through the temp matrix to get the max size and indices
int maxSize = 0;
int r = -1;
int c = -1;
for( i = 0; i < nRows; i++ )
{
for( j = 0; j < nCols; j++ )
{
if( maxSize < temp[i][j] )
{
maxSize = temp[i][j];
r = i;
c = j;
}
}
}
//r-maxSize+1, c-maxSize+1 indicates starting point for required sub-matrix
System.out.println("Size of the Biggest square sub-matrix: "+ maxSize);
System.out.println("It starts at (" + (r-maxSize+1) + "," + (c-maxSize+1) + ")");
}
}

This method takes O(n2) time and O(m x n) space for the temp matrix.

Printing the number in binary format

How do we write a program to print the binary representation of an integer?

For the sake of simplicity, let us assume that the integer takes 32 bits. The integer 367 is represented in binary as follows.

0000 0000 0000 0000 0000 0001 0110 1111

Iterative Method:

In this method we extract the bit at each of the 32 positions from left to right. The bit at ith position can be found by performing bit-wise & operation between the following numbers
2i & num

In the following  Java Program, 2i is calculated by 1<<i. This is efficient way of calculating 2 raised to the power of i. This method prints all the leading 0s also.

public static void printBinary(int num)
{
int i = 31;

while( i >= 0)
{
int mask = 1 << i;
int bit = (num & mask) == 0 ? 0: 1;
System.out.print(bit);
i--;
}
System.out.println();
}


Recursive Method:

In this function as long as num > 0, we recursively call the function by halving the number. When the number reaches 0, the stack unwinding happens. We print the remainder of num when divided by 2 (num%2). This method trims all the leading 0s if present but this works for only for non-negative integers.

public static void printBinaryRecursive(int num)
{
if( num > 0)
{
printBinaryRecursive( num/2 );
System.out.print( num%2 );
}
}


Print a string in reverse using recursion

The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the function returns and we print the character at the current pointer.

Since the function calling mechanism uses a stack to keep track the calling sequence. While unwinding the stack, we are able to print the characters in reverse.

For example printReverse(“hello”) function calling sequence looks like the following.
printReverse(“hello”)
  printReverse(“ello”)
    printReverse(“llo”)
      printReverse(“lo”)
        printReverse(“o”)
          printReverse(“”)
            return
        print “O”
      print “l”
    print “l”
  print “e”
print “h”

Here is the C++ code for the same

#include <iostream>

using namespace std;

void printReverse(char *str)
{
if( *str )
{
printReverse(str+1);
cout<<(*str);
}
}
int main()
{
char str[] = "reverse this";
printReverse(str);
return 0;
}

Checking if a number is power of 2

Given an integer how do we check if it is a power of 2?

For example 1, 2, 4, 8, 16, 32, 64, 128, 256,… are integral powers of 2.

There are several methods to check if a number is a power of 2.

Method#1: Using repeated division

If you repeatedly divide the number by 2 (without any remainder), You will finally get a 1 if it is a power of two.

For example if the number is 64

64/2 = 32/2 = 16/2 = 8/2 = 4/2 = 2/2 = 1

If the number is 22

22/2 = 11/2 = 5 (we stop here as there is a non-zero remainder)

public static boolean isPowerOfTwo(int num)
{
if( num <= 0 )
return false;

while( num > 1)
{
if( num %2 != 0)
return false;
num = num/2;
}
return true;
}


Method#2: Counting the set bits
If you consider the binary representation of the numbers, The powers of 2 always contain just one set (1) bit.

For example

1 = 0000 0001
2 = 0000 0010
4 = 0000 0100
8 = 0000 1000
16 = 0001 0000

So by counting the number of set bits and checking if it is 1, we can conclude that it is a power of 2

Please check my previous post for counting the set bits in a number.

Method#3: Efficient and clever
This method is also based on an observation of binary representation of numbers. 
We all know the Bit-wise and (&) operation . If it is represented by the following table

A   B    A&B
————–
1   1      1
1   0      0
0   1      0
0   0      0

If the number n is a power of 2, then the bit-wise and operation between n and (n-1) is always 0.

For N = 64                 0100 0000 = 64
                           0011 1111 = 63
                          ————- &
                           0000 0000
 

 public static boolean isPowerOfTwo(int num)
{
if( num <= 0 )
return false;

return (num & (num-1)) == 0? true: false;
}

Counting the set bits in a number

Given an integer, how do we count the number of set (1) bits?

For example the number 37 has 3 set bits in it’s binary representation (0010 0101)

Method#1: Simple

In this method we perform & operation between the number and 1 to get the last bit (Least Significant Bit or LSB). If it is 1 we increment the count. In the next iteration we right shift the number by one bit and repeat the same operation until the number becomes 0.

public static int getSetBitCount(int num)
{
int count = 0;

while( num > 0)
{
if( (num & 1) == 1)
count++;
num = num >> 1;
}
return count;
}

This method has a drawback that even if there less number of set bits, we have to go through all the bits to count the set bits. 
For example If the given number is 129 ( 1000 0001).  It unnecessarily goes though all the 0s between the first and last 1s.
Next method overcomes this drawback.

Method#2: Kernighan & Ritchie Method

This method is a slight improvement of the previous method where it skips the zeroes wherever they appear. 

This method is based on the observation that performing a bit-wise & operation between num and (num-1) clears the right most set bit.

For example if num = 39
0010 0111
0010 0110
———-&
0010 0110 

The number of iterations in this algorithm is based on the number of set bits. If number is 129 we can find the set bits in just two iterations.

1000 0001 = 129
1000 0000 = 128
———-&
1000 0000 = 128
0111 1111 = 127
————-&
0000 0000
 

public static int getSetBitCount(int num)
{
int count = 0;

while( num > 0)
{
num = num & (num-1);
count++;
}
return count;
}

 

Sorting the array of 0,1,2’s

We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.

For example if the input array is [2,0,1,2,1,0,0,2], the output should be
[0,0,0,1,1,2,2,2].

As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that would be an overkill to solve this problem. We can utilize the property that the array contains just 0,1, and 2.

Method#1: Bucket sort approach – Simple
Just take three counters to count 0,1 and 2. Update these while iterating through the array. This is an example of bucket sort with three buckets. Every time we see a 0, we put that in 0th bucket. If we see a 1 we put that into a 1st bucket and so on…

In the second iteration, Fill the array with respective counts of 0,1, and 2 in that order. The following is the Java implementation.

public static void sort012(int[] array)
{
int count0 = 0;
int count1 = 0;
int count2 = 0;

int i;
//Count 0's, 1's and 2's
for( i = 0; i < array.length; i++ )
{
switch( array[i] )
{
case 0:
count0++;
break;
case 1:
count1++;
break;
case 2:
count2++;
break;
}
}

//Fill the array with respective counts
int resInd = 0;

for( i = 0; i < count0; i++ )
{
array[resInd++] = 0;
}
for( i = 0; i < count1; i++ )
{
array[resInd++] = 1;
}
for( i = 0; i < count2; i++ )
{
array[resInd++] = 2;
}
}

 
Method#2: Dutch National Flag algorithm (Tricky)

This algorithm is based on Dutch national flag problem proposed by famous computer scientist Dijkstra.

In this method the array is divided into three partitions each partition is tracked by three indices. The first part stores 0s, the second part stores 1s and the third part stores 2s.

ind0 , ind1 starts from the beginning of the array, and ind2 starts from the ending of the array.
In each iteration we increment ind1 and examine the element at array[ind1]

  1. If it is 0 we have to push that left part and increment ind0, and ind1
  2. If it is 1 we simply increment ind1.
  3. If it is 2 we push it to the end and decrement ind2.
  4. Repeat the above 3 steps until ind1 and ind2 meet each other.

This algorithm scans the array only once.

Here is the snapshot of the array in each iteration.

2
0
1
2
1
0
0
2
Ind0, Ind1
Ind2

2
0
1
2
1
0
0
2
Ind0, Ind1
Ind2
0
0
1
2
1
0
2
2
Ind0, Ind1
Ind2
0
0
1
2
1
0
2
2
Ind0, Ind1
Ind2
0
0
1
2
1
0
2
2
Ind0, Ind1
Ind2
0
0
1
2
1
0
2
2
Ind0
Ind1
Ind2
0
0
1
0
1
2
2
2
Ind0
Ind1
Ind2
0
0
0
1
1
2
2
2
Ind0,
Ind1, Ind2

 

public static void sort012(int[] array)
{
int ind0 = 0;
int ind1 = 0;
int ind2 = array.length-1;

while( ind1 <= ind2 )
{
if( array[ind1] == 0 )
{
                //swap ind0, ind1 elements 
int temp = array[ind0];
array[ind0] = array[ind1];
array[ind1] = temp;

ind0++;
ind1++;
}
else if( array[ind1] == 1 )
{
ind1++;
}
else if( array[ind1] == 2 )
{
                //swap ind1, ind2 elements 
int temp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = temp;
ind2--;
}
}
}


Sorting binary array

Given an array of 0s and 1s, how do we sort them? After sorting all the 0s appear before all the 1s.

For example the array [0,1,0,1,1,0,0,0,1,1] becomes [0,0,0,0,0,1,1,1,1,1]

Let us look at two approaches to solve this problem. The first one is based on bucket sort and the second is more intelligent.

Method#1:

We can take two counts to keep track of the number of 0s and 1s. We iterate through the array two times.  In the first iteration we calculate the counts. In the second iteration we fill the array with respective counts. C++ code is given below.

void sort01(int array[], int n)
{
int count0 = 0;
int count1 = 0;
int i;
for( i = 0; i < n; i++ )
{
if( array[i] == 0 )
count0++;
else if( array[i] == 1 )
count1++;
}

int resInd = 0;

for( i = 0; i < count0; i++ )
{
array[resInd++] = 0;
}

for( i = 0; i < count1; i++ )
{
array[resInd++] = 1;
}
}


Method#2:
We start with two indices one pointing to the beginning, another pointing to the end of the array. We increment the begin index until we find a 1. We decrement the end index until we find a 0. We swap these two values so that all 0s move to beginning and all 1s move to the ending.

We repeat these steps until both indices meet. This algorithm goes through the array only once. Look at the following steps in action for the example input.

[0   1   0   1   1   0   0   0   1   1]
 L–>                             <–R

[0   1   0   1   1   0   0   0   1   1]  – Swap A[L], A[R]
     L                       R 

[0   0   0   1   1   0   0   1   1   1]  – “
             L           R

[0   0   0   0   1   0   1   1   1   1]  – “
                 L   R

[0   0   0   0   0   L   1   1   1   1]  – “
 

void sort01(int array[], int n)
{
int low = 0,high = n-1;
while ( low < high )
{
while( low < high && array[low] == 0 )
low++;

while( low < high && array[high] == 1 )
high--;

if( low < high)
swap( array[low], array[high] );
}
}


Even though both algorithms run in O(n) time, the first algorithm traverse through the array two times and the second algorithm traverse through the array only once.

Finding the most occuring element ( mode) in an array

Given an array of numbers, how do we find the element which appears most number of times? In statistics this element is called mode.

A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop counts the frequency of the element. Obviously this solution takes O(n2) time.
public static int mode( int[] array )
{
int maxCount = 1;
int maxElement = array[0];
for( int i = 0; i < array.length; i++ )
{
int count = 0;
for( int j = 0; j < array.length; j++ )
{
if( array[i] == array[j] )
count++;
}
if( maxCount < count )
{
maxCount = count;
maxElement = array[i];
}
}
return maxElement;
}

Second Method:
In this method we sort the array first. Then all the equal elements will be placed together. We can count the frequencies easily.

public static int mode( int[] array )
{
Arrays.sort(array); 
        //Assume first element as the mode
        int count = 1;
int maxCount = 1;
int maxElement = array[0]; 
        //start from the second element
        for( int i = 1; i < array.length; i++ )
{
            //array[i] is same as previous element; increment count
if( array[i-1] == array[i] )
{
count++;
}
else //new element; update the maxCount, maxElement and reset count
{
if( maxCount < count )
{
maxCount = count;
maxElement = array[i-1];
}
count = 1;
}
}
return maxElement;
}

This method takes O( n log n ) time because sorting is involved. It runs O(1) space because constant extra space is required.

Third Method:
This method is based on map. We first calculate the frequencies of all the elements in the array and store them in a map.
Then we iterate through the map to find the maximum occurring element. 

public static int mode( int[] array )
{
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
int i; 
        //Calculate the frequency map 
        for( i = 0; i < array.length; i++ )
{
//No entry in the map; add new with count 1
if( map.get(array[i]) == null )
{
map.put( array[i], 1 );
}
else //increment the count if already exists in the map
{
int valCount = map.get(array[i]);
map.put( array[i], ++valCount );
}
}
        //iterate through the map to find the maximum occurring element
Iterator iter = map.keySet().iterator();
int maxFreq = 0;
int maxElement = 0;
while( iter.hasNext() )
{
Integer key = (Integer)iter.next();
int value = map.get(key);
if( value > maxFreq )
{
maxFreq = value;
maxElement = key;
}
}
return maxElement;
}

This method runs in O(n) time but takes O(n) space for the map.

Finding the first repeated element in the array

Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.

For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].
The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is found before 78, 78 is the required answer because it appears before 45 in the array.

The brute force approach which runs in O(n2) always works for this problem. This method is explained in my previous post.

In this post we will see the Hash map based algorithm. We iterate through the array once to find the frequencies of all the unique elements in the array.

We iterate through the array again to see the first element which appears more than once.

Here is the Java implementation.


import java.util.HashMap;
/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/20/13
* Time: 12:52 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array = {1,2,3,3,2,4};
int firstRepInd = getFirstRepeatedIndex(array);
if( firstRepInd >= 0 )
{
System.out.println( array[firstRepInd] + " is the first repeated element");
}
else
{
System.out.println("No element is repeated!");
}
}
public static int getFirstRepeatedIndex(int[] array)
{
int resultInd = -1;
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
int i;
for( i = 0; i < array.length; i++ )
{
//No entry in the map; add new with count 1
if( map.get(array[i]) == null )
{
map.put( array[i], 1 );
}
else //increment the count if already exists in the map
{
int valCount = map.get(array[i]);
map.put( array[i], ++valCount );
}
}
for( i = 0; i < array.length; ++i )
{
if( map.get(array[i]) > 1)
{
resultInd = i;
break;
}
}
return resultInd;
}
}

Similar Question: How do we find the first repeated character in the string?

How to check if two strings are anagrams of each other

Anagram of a word is nothing but rearrangement of it’s letters to form another word.

For example ‘listen’ is an anagram of ‘silent’ and ‘enlist’.

We have to write a function to check if two given strings are anagrams are not.

We can solve this problem in two different ways. The first way is to sort the two strings and compare them. If they are equal, they are anagrams; otherwise they are not. The intuition behind this is by sorting the letters in the string, it forms a unique pattern. All anagrams must transform to this unique pattern when they are sorted.


For example when we sort the letters in the string ‘listen’ or ‘silent’ it becomes
‘eilnst’ 

Here is the Java function which implements the first method. Here I have used separate strings to hold the sorted sequence so that the original strings are not modified. If the original strings can be modified, we can avoid using the extra String variables.

 public static boolean areAnagrams(String strFirst, String strSecond )
{
char [] charArray = strFirst.toCharArray();
Arrays.sort(charArray);
String strFirstSort = new String( charArray );
charArray = strSecond.toCharArray();
Arrays.sort(charArray);
String strSecondSort = new String( charArray );

return strFirstSort.equals(strSecondSort);
}


Method#2:
The second method is to count the letters in both the strings and match the counts. If the letter count of both the strings is same, then we can conclude that they are anagrams.

In the following Java implementation we do not count the frequencies of letters in both the strings, but we calculate the counts for just one string.

public static boolean areAnagrams(String strFirst, String strSecond )
{
//Assume ASCII charset of size 256 alphabets
int[] charCount = new int[256];

getCharCount(strFirst,charCount);

for( int i = 0; i < strSecond.length(); i++ )
{
char ch = strSecond.charAt(i);
// If count of ch is more in second string, return false
if( charCount[ch] <= 0 )
return false;
else
charCount[ch]--;
}

for( int i = 0; i < 256; i++ )
{
if( charCount[i] > 0 )
return false;
}
return true;
}
public static void getCharCount(String strInput, int[] charCount)
{
for( int i = 0; i < strInput.length(); i++ )
{
charCount[ strInput.charAt(i)]++;
}
}

Then we iterate through the characters of the second string, we try to decrement the frequency of each character. If we found a zero, that means that particular character has appeared more number of times in the second string, then we can say that they are not anagrams. Otherwise we decrement the count of that character.

Finally we check the count array if they have any non-zero entries. If they are anagrams, we have all zero entries in count array. 

Note: We have considered the space also as a significant character in the above programs. So ‘school master’ can not be anagram of ‘the classroom’  even though they contain same letters. Also the input strings are case-sensitive.