Find the row with Max 1s

From http://www.careercup.com/question?id=5700588635422720

 A 2-D array of 1's and 0's is given. Find the row with max 1's. The array is sorted row wise (all 0's in a row are followed by all 1's).





Naive Thinking: A first I just came up with all kinds of O(nm) solutions. For example scan column by column to find the first 1, or scan row by row and note down the earliest 1. Pretty bad, though, because O(n+m) solution did exists and there exists solution better than that.

An O(m+n) algorithm is kinda greedy. 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 class Solution{   
   public static void main(String args[]){   
    Solution s = new Solution();   
    int[][] matrix = {{0,0,0,1,1},   
        {0,0,1,1,1},   
        {0,0,0,0,1},   
        {0,0,0,1,1}};   
    System.out.println(s.findRowWithMaxOnes(matrix));   
   }   
   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;   
   }   
  }    

Improved Way: As you see, since the question gives the condition each row is sorted. That leads to binary search thinking. We can do a binary search to find the first 1 of current row instead of stepping forward once. That brings the run time to O(m+log n)

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