Find the row with maximum number of 1s
Last Updated : 23 Jul, 2025
Given a binary 2D array, where each row is sorted. Find the row with the maximum number of 1s.
Examples:
Input matrix : 0 1 1 1
0 0 1 1
1 1 1 1
0 0 0 0
Output: 2
Explanation: Row = 2 has maximum number of 1s, that is 4.
Input matrix : 0 0 1 1
0 1 1 1
0 0 1 1
0 0 0 0
Output: 1
Explanation: Row = 1 has maximum number of 1s, that is 3.
[Naive Approach] Row-wise traversal - O(M*N) Time and O(1) Space:
A simple method is to do a row-wise traversal of the matrix, count the number of 1s in each row, and compare the count with the max. Finally, return the index of the row with a maximum of 1s.
Below is the implementation of the above approach:
C++ #include <bits/stdc++.h> using namespace std; // Function that returns index of row with // maximum number of 1s. int rowWithMax1s(vector<vector<bool>>& mat) { int rowIndex = -1; int maxCount = 0; int R = mat.size(); int C = mat[0].size(); for (int i = 0; i < R; i++) { int count = 0; for (int j = 0; j < C; j++) { if (mat[i][j] == 1) { count++; } } if (count > maxCount) { maxCount = count; rowIndex = i; } } return rowIndex; } // Driver Code int main() { vector<vector<bool>> mat = {{0, 0, 0, 1}, {0, 1, 1, 1}, {1, 1, 1, 1}, {0, 0, 0, 0}}; cout << rowWithMax1s(mat); return 0; } // C program to find the row with maximum number of 1s. #include<stdio.h> #include<stdbool.h> #define R 4 #define C 4 // Function that returns index of row // with maximum number of 1s. int rowWithMax1s(bool mat[R][C]) { int indexOfRowWithMax1s = -1 ; int maxCount = 0 ; // Visit each row. // Count number of 1s. /* If count is more that the maxCount then update the maxCount and store the index of current row in indexOfRowWithMax1s variable. */ for(int i = 0 ; i < R ; i++){ int count = 0 ; for(int j = 0 ; j < C ; j++ ){ if(mat[i][j] == 1){ count++ ; } } if(count > maxCount){ maxCount = count ; indexOfRowWithMax1s = i ; } } return indexOfRowWithMax1s ; } // Driver Code int main() { bool mat[R][C] = { {0, 0, 0, 1}, {0, 1, 1, 1}, {1, 1, 1, 1}, {0, 0, 0, 0}}; int indexOfRowWithMax1s = rowWithMax1s(mat); printf("Index of row with maximum 1s is %d",indexOfRowWithMax1s); return 0; } // Java program for the above approach import java.util.*; class GFG { static int R = 4 ; static int C = 4 ; // Function that returns index of row // with maximum number of 1s. static int rowWithMax1s(int mat[][], int R, int C) { // Flag to check if there is not even a single 1 in the matrix. boolean flag = true; // Initialize max values int max_row_index = 0, max_ones = 0;; // Traverse for each row and count number of 1s for(int i = 0 ; i < R ; i++){ int count1 = 0 ; for(int j = 0 ; j < C ; j++){ if(mat[i][j] == 1){ count1++; flag = false; } } if(count1>max_ones){ max_ones = count1; max_row_index = i; } } // Edge case where there are no 1 in the matrix if(flag){ return -1; } return max_row_index; } // Driver Code public static void main(String[] args) { int mat[][] = { {0, 0, 0, 1}, {0, 1, 1, 1}, {1, 1, 1, 1}, {0, 0, 0, 0}}; System.out.print("Index of row with maximum 1s is " + rowWithMax1s(mat,R,C)); } } # Python implementation of the approach R,C = 4,4 # Function to find the index of first index # of 1 in a boolean array arr def first(arr , low , high): if(high >= low): # Get the middle index mid = low + (high - low)//2 # Check if the element at middle index is first 1 if ( ( mid == 0 or arr[mid-1] == 0) and arr[mid] == 1): return mid # If the element is 0, recur for right side elif (arr[mid] == 0): return first(arr, (mid + 1), high); # If element is not first 1, recur for left side else: return first(arr, low, (mid -1)); return -1 # Function that returns index of row # with maximum number of 1s. def rowWithMax1s(mat): # Initialize max values max_row_index,Max = 0,-1 # Traverse for each row and count number of 1s # by finding the index of first 1 for i in range(R): index = first (mat[i], 0, C-1) if (index != -1 and C-index > Max): Max = C - index; max_row_index = i return max_row_index # Driver Code mat = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]] print("Index of row with maximum 1s is " + str(rowWithMax1s(mat))) // C# program for the above approach using System; using System.Collections.Generic; public class GFG { static int R = 4; static int C = 4; // Function to find the index of first index // of 1 in a bool array []arr static int first(int []arr, int low, int high) { if (high >= low) { // Get the middle index int mid = low + (high - low) / 2; // Check if the element at middle index is first 1 if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1) return mid; // If the element is 0, recur for right side else if (arr[mid] == 0) return first(arr, (mid + 1), high); // If element is not first 1, recur for left side else return first(arr, low, (mid - 1)); } return -1; } public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Function that returns index of row // with maximum number of 1s. static int rowWithMax1s(int [,]mat) { // Initialize max values int max_row_index = 0, max = -1; // Traverse for each row and count number of 1s // by finding the index of first 1 int i, index; for (i = 0; i < R; i++) { int []row = GetRow(mat,i); index = first(row, 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code public static void Main(String[] args) { int [,]mat = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; Console.Write("Index of row with maximum 1s is " + rowWithMax1s(mat)); } } // javascript program for the above approach var R = 4; var C = 4; // Function to find the index of first index // of 1 in a boolean array arr function first(arr, low, high) { if (high >= low) { // Get the middle index var mid = low + parseInt((high - low) / 2); // Check if the element at middle index is first 1 if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1) return mid; // If the element is 0, recur for right side else if (arr[mid] == 0) return first(arr, (mid + 1), high); // If element is not first 1, recur for left side else return first(arr, low, (mid - 1)); } return -1; } // Function that returns index of row // with maximum number of 1s. function rowWithMax1s(mat) { // Initialize max values var max_row_index = 0, max = -1; // Traverse for each row and count number of 1s // by finding the index of first 1 var i, index; for (i = 0; i < R; i++) { index = first(mat[i], 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code var mat = [ [0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0] ]; console.log("Index of row with maximum 1s is " + rowWithMax1s(mat)); Time Complexity: O(M*N), where M is the number of rows and N is the number of columns.
Auxiliary Space: O(1)
[Better Approach] Using Binary Search - O(M * logN) Time O(1) Space:
Since each row is sorted, we can use Binary Search to count 1s in each row. We find the index of the first occurrence of 1 in each row. The count of 1s will be equal to the total number of columns minus the index of the first 1.
Below is the implementation of the above approach:
C++ #include <bits/stdc++.h> using namespace std; // Function to find the index of first instance // of 1 in a boolean array arr[] int first(vector<bool>& arr, int low, int high) { int idx = -1; while (low <= high) { // Get the middle index int mid = low + (high - low) / 2; // If the element at mid is 1, then update mid as // starting index of 1s and search in the left half if (arr[mid] == 1) { idx = mid; high = mid - 1; } // If the element at mid is 0, then search in the // right half else { low = mid + 1; } } return idx; } // Function that returns index of row // with maximum number of 1s. int rowWithMax1s(vector<vector<bool>>& mat) { // Initialize max values int max_row_index = -1, max = -1; int R = mat.size(); int C = mat[0].size(); // Traverse for each row and count number of 1s // by finding the index of first 1 for (int i = 0; i < R; i++) { int index = first(mat[i], 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code int main() { vector<vector<bool>> mat = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; cout << rowWithMax1s(mat); return 0; } // CPP program to find the row // with maximum number of 1s #include <stdio.h> using namespace std; #define R 4 #define C 4 // Function to find the index of first instance // of 1 in a boolean array arr[] int first(bool arr[], int low, int high) { int idx = -1; while (low <= high) { // Get the middle index int mid = low + (high - low) / 2; // If the element at mid is 1, then update mid as // starting index of 1s and search in the left half if (arr[mid] == 1) { idx = mid; high = mid - 1; } // If the element at mid is 0, then search in the // right half else { low = mid + 1; } } return idx; } // Function that returns index of row // with maximum number of 1s. int rowWithMax1s(bool mat[R][C]) { // Initialize max values int max_row_index = 0, max = -1; // Traverse for each row and count number of 1s // by finding the index of first 1 int i, index; for (i = 0; i < R; i++) { index = first(mat[i], 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code int main() { bool mat[R][C] = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; printf("Index of row with maximum 1s is %d", rowWithMax1s(mat)); return 0; } // Java program to find the row // with maximum number of 1s import java.io.*; class GFG { static int R = 4, C = 4; // Function to find the index of first index // of 1 in a boolean array arr[] static int first(int arr[], int low, int high) { int idx = -1; while (low <= high) { // Get the middle index int mid = low + (high - low) / 2; // If the element at mid is 1, then update mid // as starting index of 1s and search in the // left half if (arr[mid] == 1) { idx = mid; high = mid - 1; } // If the element at mid is 0, then search in // the right half else { low = mid + 1; } } return idx; } // Function that returns index of row // with maximum number of 1s. static int rowWithMax1s(int mat[][]) { // Initialize max values int max_row_index = 0, max = -1; // Traverse for each row and count number of // 1s by finding the index of first 1 int i, index; for (i = 0; i < R; i++) { index = first(mat[i], 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code public static void main(String[] args) { int mat[][] = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; System.out.println( "Index of row with maximum 1s is " + rowWithMax1s(mat)); } } # Python3 program to find the row # with maximum number of 1s # Function to find the index # of first index of 1 in a # boolean array arr[] def first(arr, low, high): idx = -1 while low <= high: # Get the middle index mid = low + (high - low) // 2 # If the element at mid is 1, then update mid as # starting index of 1s and search in the left half if arr[mid] == 1: idx = mid high = mid - 1 # If the element at mid is 0, then search in the # right half else: low = mid + 1 return idx # Function that returns # index of row with maximum # number of 1s. def rowWithMax1s(mat): # Initialize max values R = len(mat) C = len(mat[0]) max_row_index = 0 max = -1 # Traverse for each row and # count number of 1s by finding # the index of first 1 for i in range(0, R): index = first(mat[i], 0, C - 1) if index != -1 and C - index > max: max = C - index max_row_index = i return max_row_index # Driver Code mat = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]] print("Index of row with maximum 1s is", rowWithMax1s(mat)) // C# program to find the row with maximum // number of 1s using System; class GFG { public static int R = 4, C = 4; // Function to find the index of first index // of 1 in a boolean array arr[] static int first(int[] arr, int low, int high) { int idx = -1; while (low <= high) { // Get the middle index int mid = low + (high - low) / 2; // If the element at mid is 1, then update mid // as starting index of 1s and search in the // left half if (arr[mid] == 1) { idx = mid; high = mid - 1; } // If the element at mid is 0, then search in // the right half else { low = mid + 1; } } return idx; } // Function that returns index of row // with maximum number of 1s. public static int rowWithMax1s(int[][] mat) { // Initialize max values int max_row_index = 0, max = -1; // Traverse for each row and count number // of 1s by finding the index of first 1 int i, index; for (i = 0; i < R; i++) { index = first(mat[i], 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code public static void Main(string[] args) { int[][] mat = new int[][] { new int[] { 0, 0, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 1, 1, 1, 1 }, new int[] { 0, 0, 0, 0 } }; Console.WriteLine("Index of row with maximum 1s is " + rowWithMax1s(mat)); } } // JavaScript program to find the row // with maximum number of 1s R = 4 C = 4 // Function to find the index of first instance of 1 in an array arr[] function first(arr, low, high) { let idx = -1; while (low <= high) { // Get the middle index let mid = Math.floor(low + (high - low) / 2); // If the element at mid is 1, then update mid as // starting index of 1s and search in the left half if (arr[mid] === 1) { idx = mid; high = mid - 1; } // If the element at mid is 0, then search in the right half else { low = mid + 1; } } return idx; } // Function that returns index of row // with maximum number of 1s. const rowWithMax1s = (mat) => { // Initialize max values let max_row_index = 0, max = -1; // Traverse for each row and count number of 1s // by finding the index of first 1 let i, index; for (i = 0; i < R; i++) { index = first(mat[i], 0, C - 1); if (index != -1 && C - index > max) { max = C - index; max_row_index = i; } } return max_row_index; } // Driver Code let mat = [ [0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0] ]; console.log(`Index of row with maximum 1s is ${rowWithMax1s(mat)}`); Time Complexity: O(M log N) where M is the number of rows and N is the number of columns in the matrix.
Auxiliary Space: O(1)
[Expected Approach] Traversal from top-right to outside the grid - O(M + N) Time and O(1) Space:
Start from the top-right cell(row = 0, col = N - 1) and store the ans = -1. If the value in the current cell is 1, update ans with the current row and move left. Otherwise, if the current cell is 0, move to the next row:
- If mat[row][col] == 1, update ans = row and move left by col = col - 1.
- Else if mat[row][col] == 0, row = row + 1.
Continue, till we move outside the grid and return ans.
Below is the implementation of the above approach:
C++ #include <bits/stdc++.h> using namespace std; // The main function that returns index of row with maximum // number of 1s. int rowWithMax1s(vector<vector<bool>>& mat) { int maxRow = -1, row = 0; int R = mat.size(); int C = mat[0].size(); int col = C - 1; // Move till we are inside the matrix while (row < R && col >= 0) { // If the current value is 0, move down to the next row if (mat[row][col] == 0) { row += 1; } // Else if the current value is 1, update ans and // move to the left column else { maxRow = row; col -= 1; } } return maxRow; } // Driver Code int main() { vector<vector<bool>> mat = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; cout << "Index of row with maximum 1s is " << rowWithMax1s(mat); return 0; } // C++ program to find the row with maximum // number of 1s #include <stdio.h> #include <stdbool.h> #define R 4 #define C 4 // The main function that returns index of row with maximum // number of 1s. int rowWithMax1s(bool mat[R][C]) { int maxRow = -1, row = 0, col = C - 1; // Move till we are inside the matrix while (row < R && col >= 0) { // If the current value is 0, move down to the next // row if (mat[row][col] == 0) { row += 1; } // Else if the current value is 1, update ans and // move to the left column else { maxRow = row; col -= 1; } } return maxRow; } // Driver Code int main() { bool mat[R][C] = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; printf("%d", rowWithMax1s(mat)); return 0; } public class GFG { static final int R = 4; static final int C = 4; // The main function that returns index of row with // maximum number of 1s public static int rowWithMax1s(int[][] mat) { int maxRow = -1, row = 0, col = C - 1; // Move till we are inside the matrix while (row < R && col >= 0) { // If the current value is 0, move down to the // next row if (mat[row][col] == 0) { row++; } // Else if the current value is 1, update maxRow // and move to the left column else { maxRow = row; col--; } } return maxRow; } // Driver Code public static void main(String[] args) { int[][] mat = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; System.out.println( "Index of row with maximum 1s is " + rowWithMax1s(mat)); } } # Python3 program to find the row # with maximum number of 1s # Function that returns # index of row with maximum # number of 1s. def rowWithMax1s(mat): R = len(mat) C = len(mat[0]) max_row = -1 row = 0 col = C - 1 # Move till we are inside the matrix while row < R and col >= 0: # If the current value is 0, move down to the next row if mat[row][col] == 0: row += 1 # Else if the current value is 1, update max_row and move to the left column else: max_row = row col -= 1 return max_row # Driver Code mat = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]] print("Index of row with maximum 1s is", rowWithMax1s(mat)) using System; public class GFG { static int R = 4; static int C = 4; // The main function that returns index of row with // maximum number of 1s static int RowWithMax1s(int[, ] mat) { int maxRow = -1, row = 0, col = C - 1; // Move till we are inside the matrix while (row < R && col >= 0) { // If the current value is 0, move down to the // next row if (mat[row, col] == 0) { row++; } // Else if the current value is 1, update maxRow // and move to the left column else { maxRow = row; col--; } } return maxRow; } // Driver Code static void Main() { int[, ] mat = { { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 }, { 0, 0, 0, 0 } }; Console.WriteLine("Index of row with maximum 1s is " + RowWithMax1s(mat)); } } // Function that returns index of row with maximum number of 1s function rowWithMax1s(mat) { const R = mat.length; // Number of rows const C = mat[0].length; // Number of columns let maxRow = -1; let row = 0; let col = C - 1; // Move until we are inside the matrix while (row < R && col >= 0) { // If the current value is 0, move down to the next row if (mat[row][col] === 0) { row++; } // Else if the current value is 1, update maxRow and move to the left column else { maxRow = row; col--; } } return maxRow; } // Driver Code const mat = [ [0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0] ]; console.log("Index of row with maximum 1s is", rowWithMax1s(mat)); OutputIndex of row with maximum 1s is 2
Time Complexity: O(M+N) where M is the number of rows and N is the number of columns in the matrix.
Auxiliary Space: O(1)
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile