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;
}

No comments:

Post a Comment