Friday, January 17, 2014

Find row with maximum number of 1s in sorted matrix

Problem: You are given a MxN matrix with each row sorted. Matrix is having only 0′s and 1′s. You have to find row wotth maximum number of 1′s.
eg. matrix given:
000111
001111
011111
000011
111111 // row with max number of 1′s

Method 1: Brute force approach
Traverse the matrix row wise and count number of 1′s. If the number of 1′s is greater than max count than store index of row. Return index with max 1′s.
Time Complexity: O(MxN) M is no of rows,N is no of cols.

Method 2: Using binary search(each row is sorted)
We will find occurence of first 1. Total number o 1′s will be total coumns – index of first 1.
Implementation of above approach:
// function which retrun index of 1st one in each row using binary search
int getFirstOccurence(int arr[], int low, int high)
{
  if(high >= low)
  {
    int mid = (low + high)/2;
 
    // check if the middle element is first 1
    if ( arr[mid-1] == 0 && arr[mid] == 1)
      return mid;
    else if (arr[mid] == 0)
      return getFirstOccurence(arr, (mid + 1), high);
    else
      return getFirstOccurence(arr, low, (mid -1));
  }
  return -1;
}
// function which check max 1's row
int findRowMaxOne(int mat[m][n])
{
    int max_row = 0, max = -1;
    int i, ind, count;
    for (i = 0; i < m; i++)
    {
       ind = getFirstOccurence(mat[i], 0, n-1);
       count = n - ind;
       if (ind != -1 && count > max)
       {
           max = count;
           max_row = i;
       }
    }
 
    return max_row;
}

Time Complexity: O(mLogn) where m is number of rows and n is number of columns in matrix.

0 comments:

Post a Comment