Category Archives: Matrix

Searching for a word in a grid

Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid.
The word can be formed in any of the 8 possible directions as shown below.

Here is how I solved this problem.

Write a function which takes the string to be searched, the starting coordinates, and the direction number (as shown above) as parameters.

bool search_grid(const char *word, int x, int y, int direction)

If the current letter matches, depends on the direction, we recursively invoke the same method for the next character in the string with modified coordinates.
If the current letter does not match, the word cannot be found in the given direction starting from the initial coordinates.

Here is the C++ program which implements the basic algorithm for the word match. This is not  a complete program. You may try writing a wrapper which finds the initial coordinates to start the word search (Find the the coordinates where the first letter of the word appears) and do some checks for base cases like empty string etc.

Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row.

For example consider the following matrix.

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

The maximum number of 1s in any row is three which appear in the third row.

The general approach is to find the number of 1s in each row and update the maximum.


There are two ways to find the number of 1s.
  • One simple approach is to linearly search for first 1 and find the count of 1s. This will take O(n) time in worst case. So the overall time complexity would be O(n2).
  • Another faster method is to search for first 1 using binary search since each row is sorted. This will take only O(log n) time and the overall complexity would be O(n log n).

Even more efficient approach can be as follows.

  • Start with the right most element in the first row, keep counting the number of 1s until we reach zero. 
  • Move to the next row and start checking the elements from previous column
    • If the element is zero, just move on to the next row
    • Otherwise count the ones until we reach zero or the first column
  • Repeat the above step for all the rows. At the end, we get the maximum number 1s.

This approach just runs in O(n+m) where n, m are the number of rows and columns respectively.

    Here is the C++ implementation of the above. I have used the lower_bound() method from the standard library to find the left most occurrence of a 1. Look at my previous post to understand how this method works.

    Setting the matrix elements to zero

    Given a matrix of size m * n, write a program to fill zero in ith row and jth column if matrix[i][j] is zero.

    For example let us consider the following matrix.

      6 0 2
      1 3 4
      5 9 0
    ]
    It should transform to the following.
      0 0 0
      1 0 0
      0 0 0
    ]

    This problem looks simple at the first glance, but if we do not write the program carefully it results in the wrong output, typically marks all the elements in the matrix to zeros.

    So a wrong solution can be iterate through all the elements of a matrix, and whenever we found a zero, set the corresponding rows and columns as zero.

    This will have undesired effect. Since we are modifying the same matrix, it is possible that an unexplored element may be set to zero because of a zero in the same row or column. So it is not possible to solve this problem in just one iteration.

    An inefficient, but correct solution could be to create a temporary matrix which is a copy of the original matrix, and mark the elements in temp instead of the original. This will take O(m*n) extra space.

    Can we solve this more efficiently?

    One possibility is to first go through all the elements in the matrix and store the zero containing row and column indices into two sets.

    Then set all the elements in the corresponding rows and columns to zeros in the next step. This approach will only take O(m+n) space, an improvement over the previous. Any solution should take O(m*n) time because we have to iterate through all the elements of the matrix at least  once.

    Here is the C++ function which takes the matrix as input and modify it.

    Searching for an element in the sorted matrix

    Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently?

    Example of the array can be

    int[][] matrix = {
                       {1,3,5,7,9},
                       {10,12,14,16,18},
                       {19,21,23,25,27},
                       {28,30,32,34,36},
                       {37,39,41,43,45}
                    };

    This can be done using the following algorithm. 

    We start our search with the top right element. 

    • If it is equal to the key, we print corresponding indices and we are done!. 
    • If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser. 
    • If the key is less than the given element, we move to the previous column.  The reason is similar to the above.

    We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.

    Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.

    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.