Monday, September 30, 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 3x3 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 3x3 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.

Sunday, September 29, 2013

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 );
        }
    }


Saturday, September 28, 2013

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;
}

Friday, September 27, 2013

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;
    }

Thursday, September 26, 2013

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;
    }

 

Wednesday, September 25, 2013

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--;
            }
        }
    }