Find the Row with Maximum Number of 1’s

Problem Statement

In the “Find the Row with Maximum Number of 1’s” problem we have given a matrix(2D array) containing binary digits with each row sorted. Find the row which has the maximum number of 1’s.

Input Format

The first line containing two integers values n, m.

Next, n lines containing m space-separated integers(0 or 1).

Output Format

The first and only one line containing an integer denoting the row which has the maximum number of 1’s.

Constraints

• 1<=n,m<=10^3
• 0<=a[i][j]<=a[i][j+1]<=1

Example

4 4
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1

4

Explanation: In the above example, the 4th row contains the maximum number of 1’s i.e, four 1’s.

Algorithm

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

1. Traverse through all the rows in the matrix.

2. For each row, do a binary search and find the index of the first occurrence of the 1 in that row.
Binary search

• If the mid element is 1 and the mid-1 element is 0 then return mid-index.
• If the mid element is 0, then do a binary search on the right half ie, from mid+1 to n.
• else, do a binary search on the left half ie, from 0 to mid-1.

3. Return the row which has the least index.

Implementation

C++ Program to Find the Row with Maximum Number of 1’s

#include <bits/stdc++.h>
using namespace std;

int first(vector<int> v, int low, int high) 
{ 
  if(high >= low) 
  { 
    int mid = low+(high-low)/2; 
    if((mid==0||v[mid-1]==0)&&v[mid]==1) 
    {
        return mid;
    }
    else if(v[mid]==0) 
    {
        return first(v,mid+1,high);
    }
    else
    {
        return first(v,low,mid-1);
    }
  } 
  return -1; 
} 

int find_row(vector<vector<int> > v) 
{ 
    int n = v.size();
    int m = v[0].size();
    int max_row_index = 0, max = -1; 
    int index; 
  for(int i=0;i<n;i++) 
  { 
    index = first(v[i],0,m-1); 
    if((index!=-1) && (m-index>max)) 
    { 
      max = m-index; 
      max_row_index = i; 
    } 
  } 
  return max_row_index+1; 
} 

int main() 
{ 
    int n,m;
    cin>>n>>m;
    vector<vector<int> > v;
    for(int i=0;i<n;i++)
    {
        vector<int> temp;
        for(int j=0;j<m;j++)
        {
            int x;
            cin>>x;
            temp.push_back(x);
        }
        v.push_back(temp);
    }
  cout<<find_row(v); 
  return 0; 
} 

Java Program to Find the Row with Maximum Number of 1’s

import java.util.Random;
import java.util.Scanner;
class sum
{
    static int first(int v[], int low, int high)
    {
        if(high >= low) 
  { 
    int mid = low+(high-low)/2; 
    if((mid==0||v[mid-1]==0)&&v[mid]==1) 
    {
        return mid;
    }
    else if(v[mid]==0) 
    {
        return first(v,mid+1,high);
    }
    else
    {
        return first(v,low,mid-1);
    }
  } 
  return -1;
    }
    
    static int find_row(int a[][], int n, int m) 
    { 
  int max_row_index = 0, max = -1; 
  int index; 
  for(int i=0;i<n;i++) 
  { 
    index = first(a[i],0,m-1); 
    if((index!=-1) && (m-index>max)) 
    { 
      max = m-index; 
      max_row_index = i; 
    } 
  } 
  return max_row_index+1;
    }
    
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[][] = new int[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                a[i][j] = sr.nextInt();
            }
        }
        int ans = find_row(a,n,m);
        System.out.println(ans);
    }
}

4 4
0 0 1 1
0 1 1 1
0 0 0 1 
0 0 1 1

2

Complexity Analysis

Time Complexity

O(n*logm) where n is the number of rows and m is the number of columns. Here we apply binary search at every row which leads us to nlogm time complexity.

Space Complexity

O(1) because we don’t create any auxiliary space here because don’t store any big data here.