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: Usng 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.
Please write if you find anything incorrect or any better approach.
How about this, the one that checks the matrix coloumn by coloumn. the first time 1 is found, it returns the row number:
for(j=0;j<N;j++)
{
for(i=0;i<M;i++)
{
if(A[i][j]==1)
{
printf("%d", i);
exit;
}
}
}
We can do this in O(N+M) as well.
Start from top right corner.
If you encounter 0 go down.
If you encounter 1 go right.
You will end up at the column from which maximum number of 1′s starts.
Example :
000111
001111
011111
000011
111111
start from (0,5)
there is 1 so you go right (0,4) (current_answer = M-4-1 = 1 )
there is 1 so you go right (0,3) (current_answer = M-3-1 = 2 )
there is 1 so you go right (0,2) (current_answer = M-2-1 = 3 )
there is 0 so you go down (1,2) (current_answer = M-2-1 = 3 )
there is 1 so you go right (1,2) (current_answer = M-2-1 = 3 )
there is 1 so you go right (1,1) (current_answer = M-1-1 = 4 )
there is 0 so you go down (2,1) (current_answer = M-1-1 = 4 )
there is 1 so you go right (2,0) (current_answer = M-0-1 = 5 )
there is 0 so you go down(3,0) (current_answer = M-0-1 = 5 )
there is 0 so you go down (4,0) (current_answer = M-0-1 = 5 )
there is 1 so you … opps.. we found a row which has all 1′s. and that’s the answer.
(current_answer = M-(-1)-1 = 6 )
Hope this makes sense.
First of all when a 1 is encountered, you go left not right and how are you taking note of the row index with the max.no of 1′s….??
O(n + m) solution. Suppose n rows & m columns
….
currRow = 0
currCol = m-1
maxOneRow = -1;
while(currRow =0)
{
if(arr[row][col] == 1)
{
myRow = row;
col–;
}
else
row–;
return myRow
}
// Please add check for mid == 0, other wise it will throw exception.
public int getFirstOccurenceOne(int[] matrixRow, int low, int high) {
if (high >= low) {
int mid = (low+high)/2;
if ( (mid == 0 || matrixRow[mid-1] == 0) && matrixRow[mid] == 1 ) {
return mid;
} else if (matrixRow[mid] == 0) {
return getFirstOccurenceOne(matrixRow, mid+1, high);
} else {
return getFirstOccurenceOne(matrixRow, low, mid-1);
}
}
return -1;
}