Last Updated: 27 Nov, 2020
Maximum 1s
Easy
Asked in companies
You are given a matrix ‘ARR’ with dimensions ‘N’ * ‘M’ and containing only 0s and 1s where each row is sorted.
Your task is to find the index of the row with a maximum number of 1s in it. Rows and columns are 0-indexed based.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of rows and the number of columns respectively.
Then each of the next N lines contains M elements.
Output format:
For each test case, return the index of the row, which has the maximum number of 1’s in it. If more than one row has the same number of 1’s, then return the row with the lowest index(consider 0-based indexing).
Output for each test case is printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 1000
1 <= N, M <= 500
Time Limit: 1 sec
Approaches
Approach:
- It is a brute force approach where we will traverse through each row one by one and count the number of 1’s present in each row and find the index of the row having the maximum number of 1’s.
- To find the index of the row with the maximum number of 1’s we will create a maxOnes variable initialized to -1. Whenever we update our maxOnes variable, we will also update our answer.
Algorithm:
- Create a variable maxOnes initialized to -1.
- Create another variable row initialized to -1.
- Now traverse for every row from i = 0 to i = N, and for each row, perform the following steps:
- Create a variable count initialized to 0 to count the number of ones in the current row.
- Now traverse over the columns for each current row from j = 0 to j = M and update count as count + ARR[i][j].
- If maxOnes is less than the count, update maxOnes with count and update the variable row with i.
- Finally, return row as the answer.
Approach:
- Since each row is sorted so we can apply binary search on each row to find the location where the first 1 comes in the row. Now the total number of 1’s in each row will be (M - index at which first 1 comes).
- To find the index of the row with the maximum number of 1’s we will create a maxOnes variable initialized to -1. Whenever we update our maxOnes variable, we will also update our answer.
Algorithm:
- Create a variable maxOnes initialized to -1.
- Create another variable row initialized to -1.
- Now traverse for every row from i = 0 to i = N, and for each row, perform the following steps:
- Do a binary search on the ith row to find the location of the first instance of 1 and store the answer in a variable index.
- Now create a variable count equal to (M - index) which we will store the total number of 1’s in that row.
- If maxOnes is less than the count, update maxOnes with count and update the variable row with i.
- Finally, return row as the answer.
Approach:
- The idea behind this approach is that we will find the row with the maximum number of 1’s in a single scan. This would be done by starting from the top right corner of the array ARR.
- We will keep two variables row which stores the index of the row with the maximum number of ones and currentColumn stores the index of the column till which we have traversed.
- Start from the top-right corner and if that current cell value is equal to 1 then move left in that row until we find a cell that contains a zero and update the values of row and currentColumn side by side. Also, keep in mind that the value of currentColumn should be greater than or equal to 0.
- And if the current cell value is equal to 1 then move to the next row.
- Consider the following example:
- We have ARR = {{0, 0, 1, 1}, {1, 1, 1, 1}}.
- So our row = -1 and currentColumn = 3(0-based indexing).
- We are initially in the 0th row at cell {0, 3} and there is a 1 so we move left in that row till we found a zero. So we find the 0 at cell {0, 1} and at this point our row = 0 and currentColumn = 1 and the total number of 1’s we found are = 2.
- Since we find the 0 at cell {0, 1} so we move to the next row. Here at cell {1, 1}, there is a 1 so we move towards the left and the cell {1,0} also contains 1 but now we can’t move left further so came out of the loop. At this point, our row = 1 and currentColumn = -1. Return the variable row with the value 1 as this row contains the maximum number of 1’s i.e 4.
Algorithm:
- Create a variable currentColum initialized to M-1.
- Create another variable row initialized to -1.
- Now traverse for every row from i = 0 to i = N, and for each row, perform the following steps:
- Till the value of currentColumn is greater than or equal to 0 and ARR[i][currentColumn] = 1 then perform following steps:
- Decrement currentColumn by 1.
- Update the row with i.
- Till the value of currentColumn is greater than or equal to 0 and ARR[i][currentColumn] = 1 then perform following steps:
- Finally, return row as the answer.