Maximum 1s

Easy
0/40
Average time to solve is 10m
profile
Contributed by
11 upvotes
Asked in companies
CIS - Cyber InfrastructureCIS - Cyber Infrastructure

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1 1
1
3 3
0 0 1
1 1 1
0 1 1
Sample Output 1:
0
1
Explanation for sample input 1:
For the first test case, 
Since the matrix has one row and one column. The only row, i.e., the 0th row, contains a 1. So the output is 0. 

For the second test case, 
Since the matrix has three rows and three columns. The number of ones in the 0th row is 1. The number of ones in the 1st row is 3, and the number of ones in the 2nd row is 2. So the output is 1.
Sample Input 2:
2
3 2
0 1
0 1
0 0
4 4
0 0 1 1
0 0 0 0
1 1 1 1 
0 0 1 1
Sample Output 2:
0
2
Explanation for sample input 2:
For the first test case, 
Since the matrix has 3 rows and 2 columns. The number of ones in the 0th row is 1. The number of ones in the 1st row is 1, and the number of ones in the 2nd row is 0. So the output is 0.

For the second test case, 
Since the matrix has 4 rows and 4 columns. The number of ones in the 0th row is 2. The number of ones in the 1st row is 0. The number of ones in the 2nd row is 4 and the number of ones in the 3rd row is 2. So the output is 2.
Hint

Traverse through each row and count the number of 1’s in it and find the maximum among them.

Approaches (3)
Brute Force

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.
Time Complexity

O(N*M), where ‘N’ is the number of rows, and the ‘M’ is the number of columns.

 

Since we are traversing over the matrix, which takes O(N*M) time. So overall, time complexity is O(N*M).

Space Complexity

O(1).

 

Since constant space is being used. So overall, space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximum 1s
Full screen
Console