Home » Technical Interview Questions » Array Interview Questions » Find the row with maximum number of 1’s

Find the row with maximum number of 1’s


Reading Time - 2 mins

Given a matrix(2D array) containing binary digits with each row sorted, this function will find the row which as maximum number of 1’s .

Example

INPUT:
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1

OUTPUT:
3

In the above example, third row contains maximum number of 1’s ie, four 1’s

Time Complexity: O(mlogn),

where m is the number of rows and n is the number of columns

In this method, the main idea is to do binary search in each row and find the index where 1 has occured for the first time. The output is the row which has the least index value.

Algorithm

1. Traverse through all the rows in the matrix

2. For each row, do binary search and find the index of the first occurrence of the 1 in that row
Binary search
a. If the mid element is 1 and mid-1 element is 0 then return mid index
b. If the mid element is 0, then do binary search on the right half ie, from mid+1 to n
c. else, do binary search on left half ie, from 0 to mid-1.

3. Return the row which has the least index.

C++ Program

#include <bits/stdc++.h>
#include <climits>
#define m 4
#define n 4
using namespace std;

//This function will return the index of the first one using binary search
int firstoneIndex(int arr[], int low, int high)
{
	if (low <= high)
	{
		int mid = low + (high - low)/2;

		if ((mid==0 || arr[mid -1]==0) && arr[mid]==1)
		{
			return mid;
		}
		else if(arr[mid]==0)
		{
			return firstoneIndex(arr, (mid+1), high);
		}
		else
		{
			return firstoneIndex(arr,low, (mid-1));
		}
	}
	return -1;
}
//In this function we will compare all indexes of first one
//we will print the row which has the least index
int maxOnes(int arr[m][n])
{
	int row = 0;
	int index = INT_MAX;
	for (int i = 0; i < m; ++i)
	{
		int first_index = firstoneIndex(arr[i],0,n-1);
		if (first_index != -1 && first_index<index)
		{
			index = first_index;
			row = i;
		}
	}
	cout<<"The row having maximum ones is "<<row<<endl;
	

}
int main()
{
	int arr[m][n] = {{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,1,1,1}};
	maxOnes(arr);
	return 0;
}

READ  Remove duplicates from sorted array

Time Complexity: O(m+n)

Algorithm

1. Traverse through all the rows in the matrix

2. Start from the right corner element in the first row, go left until you find a 0 and go to next row until you find a 1.

3. return the last row that you encounter.

C++ Program

#include <bits/stdc++.h>
#define m 4
#define n 4
using namespace std;
//In this function, we will go left until we find a 0 ie, j=j-1
//go to next row until we find a 1
int maxOnes(int arr[m][n])
{
	int row = 0;
	int index = INT_MAX;
	int j = n -1 ;
	for (int i = 0; i < m; ++i)
	{
		while(arr[i][j]==1 && j>=0) 
		{
		    j= j-1;
		    row = i;
		}
	}
	cout<<"The row having maximum ones is "<<row<<endl;
	

}
int main()
{
	int arr[m][n] = {{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,1,1,1}};
	maxOnes(arr);
	return 0;
}

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions