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
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
}
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
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
}
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
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 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 (currCol >= 0 && X[i][currCol] == 1)
{
currCol = currCol - 1
maxRowIndex = i
}
Solution Pseudocode
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
}
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!
You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.
Given two integer arrays X[] and Y[], write a program to check if the arrays are equal or not. Two arrays are equal if they have the same elements in any order. If there are repeated elements, then counts of repeated elements must also be the same for both arrays.
Have you ever thought of any such service that could make our life easier by allowing us to store data over the internet and simultaneously allow others to access the same data? If it is so, then this is the perfect blog for you. Here, in this blog, we'll be discussing the PasteBin System. Here, the aim is to design a highly scalable service that could allow users to paste various content (images, text, etc.) over the internet and allow others to access the pasted content. So let's look at the formal definition of PasteBin.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!