2643. Row With Maximum Ones
Problem Description
Given a matrix where each cell is either a 0
or a 1
, we need to identify which row contains the most 1
s. The matrix is formatted as a list of lists in m x n
dimensions, where m
represents the number of rows and n
the number of columns.
Our goal is to find the row index (0-indexed) with the highest number of 1
s. If there are multiple rows with the same maximum count of 1
s, we prioritize the row with the smallest index.
For the output, we must return a list with two elements: the index of the row containing the maximum count of ones and the count of ones in that respective row.
Intuition
To arrive at the solution, we can iterate through each row of the matrix and count the number of 1
s in that row. We do this by using Python's built-in count
method on lists, which efficiently returns the number of occurrences of a particular elementāin this case, the numeral 1
.
We initialize a list ans
with two elements [0, 0]
. The first element represents the index of the row and the second element represents the count of 1
s.
As we iterate over each row:
- We count the
1
s, - We compare this count with the current maximum (stored in
ans[1]
), - If the count is higher, we update
ans
with the current row index and the new maximum count.
By scanning through the matrix once, we find the required row index and the number of 1
s in that row. At the end of iteration, ans
will contain the index of the desired row and the highest count of ones found.
Solution Approach
The implementation of the solution uses a straightforward algorithm that takes advantage of simple iteration and Python's built-in list operations to solve the problem efficiently.
Here is a step-by-step guide to the algorithm:
-
Initialize an answer list
ans = [0, 0]
. The first element is the row index (initialized to 0) and the second element is the count of1
s (also initialized to 0). -
Iterate over each row in the matrix with a loop structure, keeping track of the current row index using Python's
enumerate
function.for i, row in enumerate(mat):
-
Within the loop, count the number of
1
s in the current row. This is done by using thecount
method on the row list:cnt = row.count(1)
-
Check if the current row's
1
s count (cnt
) is greater than the maximum count of1
s found so far (ans[1]
). If it is, then update the answer list with the current row index and the count:if ans[1] < cnt: ans = [i, cnt]
-
Once all rows have been checked, the list
ans
contains the required index and the count of1
s. This list is then returned as the final output.return ans
By using this approach, the solution minimizes complexity by only passing through the matrix a single time, which gives it a time complexity of O(m*n), where m
is the number of rows and n
is the number of columns in the matrix. The space complexity is O(1) since no extra space is used proportionally to the size of the input, aside from the space needed to store the answer ans
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Imagine we have the following matrix:
matrix = [ [0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 0, 0], [0, 0, 0, 0] ]
We need to identify which row has the most 1
s.
-
Initialize an answer list
ans = [0, 0]
. This list will hold the index of the row with the maximum1
s and the count of1
s in that respective row. -
Start iterating over each row in the matrix using
enumerate
:- For the first row (
i=0
), the count of1
s is2
.ans
remains[0, 0]
because2
(current row's1
s count) is not greater than0
(maximum1
s count so far).
- For the second row (
i=1
), the count of1
s is3
.- Update
ans
to[1, 3]
because3
is greater than the maximum1
s count so far, which was0
.
- Update
- For the third row (
i=2
), the count of1
s is2
.ans
remains[1, 3]
because2
is not greater than3
(current maximum1
s count).
- The fourth row (
i=3
) has a count of1
s as0
.ans
remains[1, 3]
since0
is not greater than3
.
- For the first row (
-
Now that all rows have been checked,
ans
contains the index of the row with the maximum number of1
s and the count itself, which is[1, 3]
.
Thus, the output is [1, 3]
, meaning the second row (0
-indexed) has the most number of 1
s, which are 3
in total.
Solution Implementation
1class Solution:
2 def row_and_maximum_ones(self, matrix: List[List[int]]) -> List[int]:
3 # Initialize a variable to keep track of the row index
4 # with the maximum number of ones, and the number of ones in that row.
5 result = [0, 0]
6
7 # Enumerate over the rows of the matrix.
8 for i, row in enumerate(matrix):
9 # Count the number of ones in the current row.
10 ones_count = row.count(1)
11
12 # If the count of ones in the current row is greater than
13 # the maximum found so far, update the result.
14 if result[1] < ones_count:
15 result = [i, ones_count] # Store the current row index and the count of ones.
16
17 return result # Return the result list containing the row index and the maximum count of ones.
18
1class Solution {
2
3 /**
4 * This method finds the row with the maximum number of ones in a binary matrix.
5 * @param mat A binary matrix of integers where each integer is either 0 or 1.
6 * @return An array containing the index of the row with the maximum number of ones
7 * and the count of ones in that row.
8 */
9 public int[] rowAndMaximumOnes(int[][] mat) {
10 int[] result = new int[2]; // Holds the index of the row and maximum number of ones.
11
12 for (int rowIndex = 0; rowIndex < mat.length; rowIndex++) { // Iterate over each row in the matrix.
13 int onesCount = 0; // Counter for number of ones in the current row.
14
15 for (int cellValue : mat[rowIndex]) { // Iterate over each element in the current row.
16 if (cellValue == 1) { // Check if the current element is a one.
17 onesCount++; // Increment the ones counter.
18 }
19 }
20
21 // Update result if the current row has more ones than previously found.
22 if (result[1] < onesCount) {
23 result[0] = rowIndex; // Set the index of the row with the most ones.
24 result[1] = onesCount; // Set the new maximum number of ones.
25 }
26 }
27
28 return result; // Return the array containing the row index and maximum number of ones.
29 }
30}
31
1class Solution {
2public:
3 // Function to find the row with the maximum number of ones and return that row index and count of ones in it
4 vector<int> rowAndMaximumOnes(vector<vector<int>>& matrix) {
5 vector<int> result(2); // Initialize result vector to store row index and max count of ones
6 int maxOnes = 0; // Variable to store the current maximum number of ones
7
8 // Iterate through each row in the matrix
9 for (int rowIndex = 0; rowIndex < matrix.size(); ++rowIndex) {
10 int onesCount = 0; // Variable to count the ones in the current row
11
12 // Count the number of ones in the current row
13 for (int element : matrix[rowIndex]) {
14 onesCount += element == 1;
15 }
16
17 // If the current row has more ones than the previous maximum, update the result
18 if (onesCount > maxOnes) {
19 result[0] = rowIndex; // Update row index
20 result[1] = onesCount; // Update max count of ones
21 maxOnes = onesCount; // Update max ones for comparison in subsequent iterations
22 }
23 }
24
25 // Return the result vector containing the index of the row and the maximum number of ones
26 return result;
27 }
28};
29
1// Function to find the row with the maximum number of ones in a binary matrix
2// and return an array containing the row index and the count of ones.
3function rowAndMaximumOnes(mat: number[][]): number[] {
4 // Initialize the answer array with the first element as the row index
5 // and the second element as the count of ones.
6 const answer: number[] = [0, 0];
7
8 // Iterate through each row of the matrix
9 for (let rowIndex = 0; rowIndex < mat.length; rowIndex++) {
10 // Count the number of ones in the current row by summing up the values
11 const onesCount = mat[rowIndex].reduce((total, value) => total + value, 0);
12
13 // If the count of ones in the current row is greater than the current maximum,
14 // update the answer array with the new row index and ones count
15 if (answer[1] < onesCount) {
16 answer[0] = rowIndex;
17 answer[1] = onesCount;
18 }
19 }
20
21 // Return the answer array with the row index and count of ones for the row with the maximum number of ones
22 return answer;
23}
24
Time and Space Complexity
The time complexity of the given code is O(m*n)
, where m
is the number of rows and n
is the number of columns in the matrix mat
. This is because the code iterates through each row with enumerate(mat)
and counts the number of 1
's in that row with row.count(1)
, which requires traversing the entire row.
The space complexity of the given code is O(1)
. The additional space used by the algorithm is constant and does not scale with the input size since only a fixed-size list ans
of length 2 is used to store the result and no other additional data structures are allocated.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!