Find the row with maximum number of 1s | GeeksforGeeks
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
http://siyang2notleetcode.blogspot.com/2015/02/find-row-with-max-1s.html
O(m+n)
Keep two pointers, one for row(i), one for column(j). Start from the very end of first row, each time encounter a 1, step forward(j--), each time encounter a 0, it means current row will have no chance have more 1 than m-j, thus go to next row, starting from j. That saves us the time from repeatedly scanning rows that are denied.
O(m+logn)
We can do a binary search to find the first 1 of current row instead of stepping forward once.
http://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/
http://comproguide.blogspot.com/2015/03/maximum-number-of-1s-in-any-row-of.html
Since each row is sorted, we can use Binary Search to count of 1s in each row. We find the index of first instance of 1 in each row. The count of 1s will be equal to total number of columns minus the index of first 1.
The above solution can be optimized further. Instead of doing binary search in every row, we first check whether the row has more 1s than max so far. If the row has more 1s, then only count 1s in the row. Also, to count 1s in a row, we don’t do binary search in complete row, we do search in before the index of last max.
http://blueocean-penn.blogspot.com/2014/04/find-row-with-maximum-number-of-1s.html
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
Following method works in O(m+n) time complexity in worst case.
Step1: Get the index of first (or leftmost) 1 in the first row.
Step2: Do following for every row after the first row
…IF the element on left of previous leftmost 1 is 0, ignore this row.
…ELSE Move left until a 0 is found. Update the leftmost index to this index and max_row_index to be the current row.
…IF the element on left of previous leftmost 1 is 0, ignore this row.
…ELSE Move left until a 0 is found. Update the leftmost index to this index and max_row_index to be the current row.
The time complexity is O(m+n) because we can possibly go as far left as we came ahead in the first step.
http://siyang2notleetcode.blogspot.com/2015/02/find-row-with-max-1s.html
O(m+n)
Keep two pointers, one for row(i), one for column(j). Start from the very end of first row, each time encounter a 1, step forward(j--), each time encounter a 0, it means current row will have no chance have more 1 than m-j, thus go to next row, starting from j. That saves us the time from repeatedly scanning rows that are denied.
public int findRowWithMaxOnes(int[][] array){
int n = array.length;
int m = n==0?0:array[0].length;
int i = 0, j = m-1;
int row = 0;
while(i < n && j >= 0){
if(array[i][j]==1){
row = i;
j--;
}else{
i++;
}
}
return row;
} int rowWithMax1s(bool mat[R][C]){ // Initialize first row as row with max 1s int max_row_index = 0; // The function first() returns index of first 1 in row 0. // Use this index to initialize the index of leftmost 1 seen so far int j = first(mat[0], 0, C-1); if (j == -1) // if 1 is not present in first row j = C - 1; for (int i = 1; i < R; i++) { // Move left until a 0 is found while (j >= 0 && mat[i][j] == 1) { j = j-1; // Update the index of leftmost 1 seen so far max_row_index = i; // Update max_row_index } } return max_row_index;}We can do a binary search to find the first 1 of current row instead of stepping forward once.
public int findRowWithMaxOnes(int[][] array){
int n = array.length;
int m = n==0?0:array[0].length;
int i = 0, j = m-1;
int row = 0;
while(i < n && j >= 0){
j = binarySearch(array[i], 0, j);
row = i;
i++;
while(i < n && array[i][j]==0) i++;
}
return row;
}
private int binarySearch(int[] arr, int begin, int end){
while(begin < end){
int middle = (begin+end)/2;
if(arr[middle] == 0 && arr[middle+1] == 1) return middle+1;
if(arr[middle] == 0) begin = middle+1;
else end = middle;
}
return begin;
}http://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/
int first(bool arr[], int low, int high){ if(high >= low) { // get the middle index int mid = low + (high - low)/2; // check if the element at middle index is first 1 if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) return mid; // if the element is 0, recur for right side else if (arr[mid] == 0) return first(arr, (mid + 1), high); else // If element is not first 1, recur for left side return first(arr, low, (mid -1)); } return -1;}// The main function that returns index of row with maximum number of 1s. int rowWithMax1s(bool mat[R][C]){ int max_row_index = 0, max = -1; // Initialize max values // Traverse for each row and count number of 1s by finding the index // of first 1 int i, index; for (i = 0; i < R; i++) { index = first (mat[i], 0, C-1); if (index != -1 && C-index > max) { max = C - index; max_row_index = i; } } return max_row_index;}The above solution can be optimized further. Instead of doing binary search in every row, we first check whether the row has more 1s than max so far. If the row has more 1s, then only count 1s in the row. Also, to count 1s in a row, we don’t do binary search in complete row, we do search in before the index of last max.
int rowWithMax1s(bool mat[R][C])
{
int i, index;
// Initialize max using values from first row.
int max_row_index = 0;
int max = first(mat[0], 0, C-1);
// Traverse for each row and count number of 1s by finding the index
// of first 1
for (i = 1; i < R; i++)
{
// Count 1s in this row only if this row has more 1s than
// max so far
// Count 1s in this row only if this row has more 1s than
// max so far
if (max != -1 && mat[i][C-max-1] == 1)
{
// Note the optimization here also
index = first (mat[i], 0, C-max);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
else {
max = first(mat[i], 0, C - 1);
}
}
return max_row_index;
}
http://comproguide.blogspot.com/2015/03/maximum-number-of-1s-in-any-row-of.html
Even more efficient approach can be as follows.
- Start with the right most element in the first row, keep counting the number of 1s until we reach zero.
- Move to the next row and start checking the elements from previous column
- If the element is zero, just move on to the next row
- Otherwise count the ones until we reach zero or the first column
- Repeat the above step for all the rows. At the end, we get the maximum number 1s.
This approach just runs in O(n+m) where n, m are the number of rows and columns respectively.
int getMaximum1_fast(vector< vector<int> > & matrix){int r,c;int result = 0;int nRows = matrix.size();int nCols = 0;if( nRows > 0 ){nCols = matrix[0].size();c = nCols-1;r = 0;while( r < nRows ){while( c >= 0 && matrix[r][c] == 1 ){c--;result++;}if( c < 0 ) //Optimize here, Maximum (i.e no of columns) is reached; we can breakbreak;r++;}}return result;}
int rowWithMax1s(bool mat[R][C]){ // Initialize first row as row with max 1s int max_row_index = 0; // The function first() returns index of first 1 in row 0. // Use this index to initialize the index of leftmost 1 seen so far int j = first(mat[0], 0, C-1) - 1; if (j == -1) // if 1 is not present in first row j = C - 1; for (int i = 1; i < R; i++) { // Move left until a 0 is found while (j >= 0 && mat[i][j] == 1) { j = j-1; // Update the index of leftmost 1 seen so far max_row_index = i; // Update max_row_index } } return max_row_index;}/* A function to find the index of first index of 1 in a boolean array arr[] */int first(bool arr[], int low, int high){ if(high >= low) { // get the middle index int mid = low + (high - low)/2; // check if the element at middle index is first 1 if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) return mid; // if the element is 0, recur for right side else if (arr[mid] == 0) return first(arr, (mid + 1), high); else // If element is not first 1, recur for left side return first(arr, low, (mid -1)); } return -1;}// The main function that returns index of row with maximum number of 1s. int rowWithMax1s(bool mat[R][C]){ int max_row_index = 0, max = -1; // Initialize max values // Traverse for each row and count number of 1s by finding the index // of first 1 int i, index; for (i = 0; i < R; i++) { index = first (mat[i], 0, C-1); if (index != -1 && C-index > max) { max = C - index; max_row_index = i; } } return max_row_index;}int rowWithMax1s(bool mat[R][C]){ int i, index; // Initialize max using values from first row. int max_row_index = 0; int max = C - first(mat[0], 0, C-1); // Traverse for each row and count number of 1s by finding the index // of first 1 for (i = 1; i < R; i++) { // Count 1s in this row only if this row has more 1s than // max so far if (mat[i][C-max-1] == 1) { // Note the optimization here also index = first (mat[i], 0, C-max); if (index != -1 && C-index > max) { max = C - index; max_row_index = i; } } } return max_row_index;}Read full article from Find the row with maximum number of 1s | GeeksforGeekspublic 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;}
