Difficulty: Medium, Asked-in: Amazon, Microsoft, Paytm
Key takeaway: This is an excellent matrix problem that can be solved in linear time complexity. We are using the sorted order property and nested loops to improve the solution over the binary search approach.
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
Solution Idea
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:
Solution Pseudocode
Time and space complexity analysis
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).
Solution Idea
We already know that each row is sorted. Can we use this information to improve the time complexity? Let's think!
Solution Steps
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
}
Solution Pseudocode
Searching the first occurrence of 1: searchFirstOne(X[], l, r)
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)
Pseudocode: Searching the first occurrence of 1
Time and space complexity analysis
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!)
Solution Idea
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:
Solution Steps
Now we run a loop from i = 0 to row - 1:
while(curr_col >= 0 && X[i][curr_col] == 1)
{
curr_col = curr_col - 1
maxRowIndex = i
}
Solution Pseudocode
Time and space complexity analysis
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!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.