Find a Row of a Matrix Having Maximum Number of 1

  • Write a program to find a row having maximum number of 1's in a row wise sorted boolean matrix.

Given a matrix of size M x N having 0 and 1. Each row of input matrix is sorted from left to right. We have to find a row having maximum number of 1's.
For Example: 

Input Matrix: 
0, 1, 1, 1
0, 0, 1, 1
0, 0, 1, 1
1, 1, 1, 1

Output :
Row number 3 contains maximum number of 1

Method 1 : By counting number of 1's in every row
Let inputMatrix be a boolean integer matrix of size R X C.
  • Traverse input matrix row wise and count the number of 1's in every row.
  • If the number of 1's in current row is more than the maximum count found till now then update maximum count.
  • At last, print the row number having maximum count of 1.
Time Complexity : O(R*C)
Method 2 : Using Modified Binary Search
Let inputMatrix be a boolean integer matrix of size R X C.
  • As each row of matrix is sorted, we just need to find the index of first 1(left most 1) to get the count of all 1's in a row. Let the index of left most 1 is i, then total number of 1's in that row is C - i.
  • We will use a modified binary search algorithm to find the left most instance of 1.
  • Using this approach we can find the number of 1's in any row in log(C) time instead of O(C).
  • If the number of 1's in current row is more than the maximum count found till now then update maximum count.
  • At last, print the row number having maximum count of 1.
Time Complexity : O(RLog(C)), we have to do binary search for every row.

C program to find row having maximum number of 1 using binary search

#include <stdio.h>

#define COLS 4
#define ROWS 4
 
/* Returns the index of first occurence of K in sorted array. 
If is not present then it returns -1. It uses a customized 
binary search algorithm */
int getFirstIndex(int *array, int left, int right, int K) {
    int mid;
 if (right >= left) {
  /* Get mid index */
        mid = (left + right)/2;
 
        /*
        if array[mid] == K, then mid will be the index of first 
  occurence of K if either mid == 0, or array[mid-1] < K
        */
        if ((array[mid] == K) && (mid == 0 || K > array[mid-1]))
            /* first occurence found */
            return mid;
        else if (K > array[mid])
            /* Recursively search on right sub array */ 
            return getFirstIndex(array, (mid + 1), right, K);
        else
            /* Recursively search on left sub array */
            return getFirstIndex(array, left, (mid - 1), K);
    }
    return -1;
}
 
/* Returns the index of row having maximum number of 1's in matrix */ 
int getMaxOneRowIndx(int matrix[ROWS][COLS]) {
    int i, firstIndex, rowMax = 0, max = 0; 
 
    /* As all rows are sorted, Find the index of first one in every
  row(Index), and then number of 1's is equal to COLS - Index.
 Return the index of row hacing maximum number of 1 */
    for (i = 0; i < ROWS; i++) {
       firstIndex = getFirstIndex(matrix[i], 0, COLS-1, 1);
       if(firstIndex != -1 && (COLS-firstIndex) > max) {
           max = COLS - firstIndex;
           rowMax = i;
       }
    }
    
    return rowMax;
}
 
int main() {
    int matrix[ROWS][COLS] = { {0, 1, 1, 1},
                               {0, 0, 1, 1},
                               {0, 0, 1, 1},
                               {1, 1, 1, 1}
    };
 
    printf("Maximum number of 1's is in row %d\n", 
        getMaxOneRowIndx(matrix));
 
    return 0;
}
Output
Maximum number of 1's is in row 3
Method 3 : Fastest approach having O(R + C) time complexity
Let inputMatrix be a boolean integer matrix of size R X C. ro
  • As each row of matrix is sorted from left to right, all 1's are grouped together in right side of a row.
  • Let the index of left most 1 in max one count row found till now is i.
  • We will first check whether current row(rth row) contains more 1's than max one count row found till now. If yes, then we will process current row otherwise skip it.
    1. If matrix[r][i] == 0, then skip this row.
    2. Else traverse rth row toward left side from index i till we find left most 1.
Time Complexity : O(R + C)
Here is the C program implementing above algorithm. 
#include <stdio.h>

#define COLS 4
#define ROWS 4
 
/* Returns the index of row having maximum number of 1's in matrix */ 
int getMaxOneRowIndx(int matrix[ROWS][COLS]) {
    int i, firstIndex, rowMax;
    /* Initialize rowMax to 0 and firstIndex to COLS */
    rowMax = 0; firstIndex = COLS;
 
    for(i = 0; i < ROWS; i++){
     while(firstIndex > 0 && matrix[i][firstIndex-1] == 1){
        firstIndex--;
        rowMax = i;
        }
    }
 
    return rowMax;
}
 
int main() {
    int matrix[ROWS][COLS] = { {0, 1, 1, 1},
                               {0, 0, 1, 1},
                               {1, 1, 1, 1},
                               {0, 0, 0, 1}
    };
 
    printf("Maximum number of 1's is in row %d\n", 
        getMaxOneRowIndx(matrix));
 
    return 0;
}
Output
Maximum number of 1's is in row 2
Posted by
Labels: ,