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 2D boolean array of size m x n, where each row is sorted. Write program to find the row with the maximum number of 1s.
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 iterate through each row of the array and count the number of ones in each row. We can then keep track of the maximum number of ones seen so far and the index of the row with the maximum number of ones. At the end, we can return the index of the row with the maximum number of ones.
To implement this, we use two nested loops and three variables:
int rowWithMaxOnes(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;
}
def rowWithMaxOnes(X, row, col):
maxOneCount = 0
maxRowIndex = -1
for i in range(row):
rowOneCount = 0
for j in range(col):
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
}
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)
// Function to search the first index of 1 in the given row
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;
}
// Function to find the row with maximum number of 1s
int rowWithMaxOnes(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;
}
def searchFirstOne(X, l, r):
if l <= r:
mid = l + (r - l) // 2
if (X[mid - 1] == 0 or mid == 0) and X[mid] == 1:
return mid
elif X[mid] == 0:
return searchFirstOne(X, mid + 1, r)
else:
return searchFirstOne(X, l, mid - 1)
return -1
def rowWithMaxOnes(X, row, col):
maxOneCount = 0
maxRowIndex = -1
for i in range(row):
firstOneIndex = searchFirstOne(X[i], 0, col - 1)
rowOneCount = col - firstOneIndex
if firstOneIndex != -1 and rowOneCount > maxOneCount:
maxOneCount = rowOneCount
maxRowIndex = i
return maxRowIndex
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 rowWithMaxOnes(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;
}
def rowWithMaxOnes(X, row, col):
maxRowIndex = -1
currCol = col - 1
for i in range(row):
while currCol >= 0 and X[i][currCol] == 1:
currCol = currCol - 1
maxRowIndex = i
return maxRowIndex
There are two nested loops in the code and the 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.
Let's think from another perspective: When we are traversing any row from right to left, then all the columns in that path will be traversed once. Similarly, when we traverse any column from top to down, all the rows in that path will be traversed once.
So total loop iteration = Total number of rows + Total number of columns = m + n. At each loop iteration, we are doing O(1) operation. So time complexity = Total loop iteration * O(1) = (m + n) * O(1) = O(m + n).
We are using a constant number of variables, so space complexity = O(1)
Enjoy learning, Enjoy coding, Enjoy algorithms!