Background
This is a data structure and an interview question. It goes as follows -
"Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s."
or to put it another way each row will have either all 0's or all 1's or k 0's and (n-l) 1's given a 2D array of m*n. Also each k 0's are contiguous and same goes with (n-1) 1's. In short they are sorted. This is just to confuse the interviewee and do not give straight hint that we are dealing with sorted things here :)
Example is in screenshot below-
Note : This question is also in GeeksForGeeks site which has solution in C. I am just going to provide solution in Java. So lets get started.
Brute Force
Brute force is the worst complexity approach you can take. It gives solution... just not in efficient way. I believe you should always start with this approach. This helps you get a better hang of the problem and interviewer will know you can get things done. Efficiency is something you can always work on or get help of colleges or code reviewers (it will comes more fluently with experience). So always start with brute force approach.
For this brute force approach would be to iterate over all columns in each row and keep a count of maximum no of 1's in each row and index of that row. Finally return it when you are done with the looping. Time complexity for this would be O(m*n) for a 2D array of dimension m*n. So lets see how this would go.
/**
* @author athakur
* Brute force approach
*/
public class BruteForce {
public int compute(int[][] array)
{
int maxRowOnesIndex = 0;
int maxRowOnesCount = 0;
for(int i=0;i<array.length;i++)
{
int localMaxOnesCount = 0;
for(int j=0; j<array[i].length;j++)
{
if(array[i][j] == 1) {
localMaxOnesCount++;
}
}
if(localMaxOnesCount > maxRowOnesCount)
{
maxRowOnesCount = localMaxOnesCount;
maxRowOnesIndex = i;
}
}
return maxRowOnesIndex;
}
}
To use this methods class and test the working execute following code.
Output : 2
/**
* @author athakur
* Starter code for computing row with maximum 1's in a 2D array
*/
public class Compute {
public static void main(String args[])
{
int[][] array = new int[][]{{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,0,0,0}};
System.out.println(new BruteForce().compute(array));
}
}
Output : 2
That's the brute force method. As mentioned earlier it's time complexity is O(m*n) which is like the worst complexity. Can we do better than this? Sure we can :)
What is it that we can leverage here? We know that each row in the 2D array is sorted. We can easily to a binary search to find the leftmost 1. Count of 1st will be no of columns minus index of leftmost one. Now guess what the time complexity is for this approach?
It is O(m*logn). We iterate over each row (total of m rows) and then do a binary search on each row with log n complexity.
/**
* @author athakur
* Binary Search approach
*/
public class BinarySearch {
private int first(int[] array, int low, int high)
{
if(high >= low)
{
int mid = low + (high-low)/2;
if((mid == 0 || array[mid-1]==0) && (array[mid] == 1))
{
return mid;
}
else if(array[mid] == 0) {
return first(array, mid + 1, high);
}
else {
return first(array, low, mid-1);
}
}
return -1;
}
public int compute(int [][] array)
{
int maxRowOnesIndex = 0;
int maxRowOnesCount = 0;
for(int i=0; i< array.length;i++)
{
int onesIndex = first(array[i], 0, array[i].length-1);
if(onesIndex != -1)
{
int localMaxOnesCount = array.length - onesIndex;
if(localMaxOnesCount > maxRowOnesCount)
{
maxRowOnesCount = localMaxOnesCount;
maxRowOnesIndex = i;
}
}
}
return maxRowOnesIndex;
}
}
And run it with
/**
* @author athakur
* Starter code for computing row with maximum 1's in a 2D array
*/
public class Compute {
public static void main(String args[])
{
int[][] array = new int[][]{{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,0,0,0}};
System.out.println(new BinarySearch().compute(array));
}
}
Output :2
Note : 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.
So basically lets say 1st row has m 1's we will check for each for the subsequent row i whether array[i][n-m-1] is 1.
