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