Showing posts with label maximum ones. Show all posts
Showing posts with label maximum ones. Show all posts

Monday, April 28, 2014

Find the row with maximum number of 1s

This is from the geeksforGeeks site:


Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
Example
Input matrix
0 1 1 1
0 0 1 1
1 1 1 1  // this row has maximum 1s
0 0 0 0

Output: 2

The solution is simple. for each row, we will start from the end and move backwards until 0 is found. and the starting position for each row is equal to the previous row's starting position of 1. 

public static int findMaxOnes(int[][] nums){
int max = nums[0].length-1;
int index = 0;
for(int i = 0; i<nums.length; i++){
for(int j = max; j>=0; j--){
if(nums[i][j]==0)
break;
max = j;
index = i;
}
}
return index;
}