Difficulty: Medium, Asked-in: Amazon, Microsoft, Paytm
Key takeaway: This is an excellent matrix problem to learn step by step time complexity optimization.
Given a boolean 2D array of size m x n, where each row is sorted. Find the row with the maximum number of 1s.
Examples
Input: X[][]
0 1 1 1
1 1 1 1 <- row with max number of 1's
0 0 1 1
0 0 0 0
Output: 1 (0-based indexing)
Input: X[][]
0 0 1 1
0 0 0 1
0 1 1 1 <- row with max number of 1's
0 0 0 1
Output: 2
A straightforward method is to do a row-wise linear search, count the number of 1s in each row, and track the row-index with a max 1 count. To implement this, we use two nested loops and three variables:
int row_with_max_ones(int X[][], int row, int col)
{
int maxOneCount = 0
int maxRowIndex = -1
for (int i = 0; i < row; i = i + 1)
{
int rowOneCount = 0
for (int j = 0; j < col; j = j + 1)
{
if (X[i][j] == 1)
rowOneCount = rowOneCount + 1
}
if (rowOneCount > maxOneCount)
{
maxOneCount = rowOneCount
maxRowIndex = i
}
}
return maxRowIndex
}
We are traversing each matrix element using nested loops and doing O(1) operation at each iteration. So time Complexity = n*m*O(1) = O(nm). We are using constant extra variables, so space complexity = O(1).
We already know that each row is sorted. Can we use this information to improve the time complexity? Let's think!
We declare four variables to track the count of 1's in a row(rowOneCount), overall max count of 1's (maxOneCount), index of the first occurrence of 1 (firstOneIndex), and row-index with max number of 1's (maxRowIndex). For accessing each row, we run a loop from i = 0 to row - 1:
if(firstOneIndex != -1 && rowOneCount > maxOneCount), we update the value of maxOneCount with rowOneCount and maxRowIndex with i.
if (firstOneIndex != -1 && rowOneCount > maxOneCount)
{
maxOneCount = rowOneCount
maxRowIndex = i
}
int row_with_max_ones(int X[][], int row, int col)
{
int maxOneCount = 0
int maxRowIndex = -1
for (int i = 0; i < row; i = i + 1)
{
int firstOneIndex = searchFirstOne(X[i], 0, col-1)
int rowOneCount = col - firstOneIndex
if (firstOneIndex != -1 && rowOneCount > maxOneCount)
{
maxOneCount = rowOneCount
maxRowIndex = i
}
}
return maxRowIndex
}
As mentioned above, we can apply the binary search to find the first occurrence of the one. For this, we are using recursive binary search where the base case occurs when l > r. So if(l <=r), we execute the following steps:
If the value at mid is 1 and the previous value at mid - 1 is 0, it means, the first 1 is present at the mid index. There is another corner case when the first one is present at the first position: if mid = 0 and X[mid] == 1. In both situations, we return mid-index as the first occurrence.
if ((X[mid - 1] == 0 || mid == 0) && X[mid] == 1)
return mid
Otherwise, if both the above conditions are false, then the mid index is at some 1, not the first occurrence. In other words, the first one will be present somewhere in the left half. So we need to search the occurrence of the first 1 in the left half using the same function recursively with l and mid - 1 as the left and right end.
else if (X[mid] == 0)
return searchFirstOne(X, mid + 1, r)
else
return searchFirstOne(X, l, mid - 1)
int searchFirstOne(int X[], int l, int r)
{
if (l <= r)
{
int mid = l + (r - l)/2
if ((X[mid - 1] == 0 || mid == 0) && X[mid] == 1)
return mid
else if (X[mid] == 0)
return searchFirstOne(X, mid + 1, r)
else
return searchFirstOne(X, l, mid - 1)
}
return -1
}
Time complexity = number of rows * time complexity of binary search to find first 1 in each row = n * O(logm) = O(nlogm), where n is the number of rows, and m is the number of columns.
We are using recursive binary search, so space complexity depends on the size of the call stack which is equal to the height of the recursion tree. Space complexity = O(logn) (Think!)
Can we improve the time complexity further? Think! Here are two observations from the given input matrix: 1) Each row is sorted, so all the 1's in any row will be lined up to the right end. 2) For the first 1 in any row, if there is a 1 in the same column in the next row, then the count of 1's in row <= count of 1's in the next row. The same idea applies to all the consecutive i and i + 1 rows.
So here is an exciting solution idea:
Now we run a loop from i = 0 to row - 1:
while (currCol >= 0 && X[i][currCol] == 1)
{
currCol = currCol - 1
maxRowIndex = i
}
int row_with_max_ones(int X[][], int row, int col)
{
int maxRowIndex = -1
int currCol = col - 1
for (int i = 0; i < row; i = i + 1)
{
while (currCol >= 0 && X[i][currCol] == 1)
{
currCol = currCol - 1
maxRowIndex = i
}
}
return maxRowIndex
}
There are two nested loops in the code, and time complexity looks O(mn), but this is not the correct analysis. If we observe closely, we traverse each row and column once, i.e outer loop traverses each row, and the inner loop traverses each column (Think!).
Let's think from another perspective: when we are traversing any row from left to right, then all the columns in that path will be traversed once. Similarly, when we travel any column from top to down, all the rows in that path will be traversed once. (Think!)
We are using a constant number of variables, so space complexity = O(1)
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.