Row with Maximum ones
Problem Statement
Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of ones in that row.
In case there are multiple rows that have the maximum count of ones, the row with the smallest row number should be selected.
Return an array containing the index of the row, and the number of ones in it.
Examples:
Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows have the same number of 1's. So we return the index of the smaller row, 0, and the maximum count of ones (1). So, the answer is [0,1].
Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So we return its index, 1, and the count. So, the answer is [1,2].
Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So the answer is [1,2].
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.
Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
To solve the problem of finding the row with the maximum number of ones, we need to check each row and count the number of ones it contains. Then, we can identify the row with the highest count of ones.
Let's see how we can approach this for a single row. We can start by initializing a variable called cur_count to 0. Then, as we traverse the row element by element, we increment cur_count whenever we encounter the value 1. This will give us the total count of ones in that row.
To count the number of ones in each row, we can use a loop that iterates from i = 0 to i = n-1 (since there are n rows indexed from 0 to n-1). For each row, we calculate the number of ones it contains. If the current row's count (maxCount) exceeds the maximum count so far (maxCount), we update cnt with the new value. Additionally, we update the maxRow variable with the current index i, indicating that this row contains the maximum number of ones. By the end of the loop, maxCount will store the maximum number of ones, and maxRow will identify the row that contains them.
Let's walk through an example:
Step 1: Initialize Variables
- maxCount = 0: Keeps track of the highest number of ones found so far.
- maxRow = 0: Stores the index of the row with the maximum number of ones. Initially let's assume it as 0.
Step 2: Loop through each row in the matrix
We loop through each row to count the number of ones and compare it with the current maximum.
Iteration 1: Row 0 ([0, 0])
- Start with curCount = 0 to count the ones in the current row.
- Traverse the row:
- mat[0][0] = 0 : No increment to curCount.
- mat[0][1] = 0 : No increment to curCount.
- Count for Row 0: curCount = 0.
- Compare curCount with maxCount :
- curCount (0) is not greater than maxCount (0), so no updates to maxCount or maxRow.
Iteration 2: Row 1 ([1, 1])
- Start with curCount = 0 to count the ones in the current row.
- Traverse the row:
- mat[1][0] = 1: Increment curCount to 1.
- mat[1][1] = 1: Increment curCount to 2.
- Count for Row 1: curCount = 2.
- Compare curCount with maxCount:
- curCount (2) is greater than maxCount (0), so update:
- maxCount = 2.
- maxRow = 1.
Iteration 3: Row 2 ([0, 0])
- Start with curCount = 0 to count the ones in the current row.
- Traverse the row:
- mat[2][0] = 0: No increment to curCount.
- mat[2][1] = 0: No increment to curCount.
- Count for Row 2: curCount = 0.
- Compare curCount with maxCount:
- curCount (0) is not greater than maxCount (2), so no updates to maxCount or maxRow.
Step 3: Return the Result
At the end of all iterations:
- maxRow = 1: The row with the maximum number of ones.
- maxCount = 2: The count of ones in that row.
The result is [maxRow, maxCount], which is [1, 2].
How to convert it in code:
- Initialize variables:
- Use maxCount to store the maximum number of ones found so far.
- Use maxRow to store the index of the row with the maximum number of ones.
- Iterate through the matrix row by row:
- For each row, use a nested loop to count the number of ones.
- Update if a new maximum is found:
- If the count of ones for the current row is greater than maxCount, update maxCount and maxRow.
- Return the result:
- Return a vector containing maxRow (index of the row) and maxCount (maximum count of ones).
Code Implementation
C++
// Solution class with the method to find the row with the maximum number of ones
class Solution {
public:
vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
int maxCount = 0; // To store the maximum count of ones
int maxRow = 0; // To store the index of the row with maximum ones
// Iterate through each row in the matrix
for (int i = 0; i < mat.size(); i++) {
int curCount = 0; // Count the number of ones in the current row manually
// Count ones in the current row
for (int j = 0; j < mat[i].size(); j++) {
if (mat[i][j] == 1) {
curCount++;
}
}
// Update maxCount and maxRow if a new maximum is found
if (curCount > maxCount) {
maxCount = curCount;
maxRow = i;
}
}
// Return the result as a vector
return {maxRow, maxCount};
}
};
Java
class Solution {
public int[] rowAndMaximumOnes(int[][] mat) {
int maxCount = 0; // To store the maximum count of ones
int maxRow = 0; // To store the index of the row with the maximum ones
// Iterate through each row
for (int i = 0; i < mat.length; i++) {
int curCount = 0; // Count of ones in the current row
// Count the ones in the current row
for (int j = 0; j < mat[i].length; j++) {
if (mat[i][j] == 1) {
curCount++;
}
}
// If the current row has more ones than the previous max, update maxRow and maxCount
if (curCount > maxCount) {
maxCount = curCount;
maxRow = i;
}
}
// Return the result as an array with the row index and the count of ones
return new int[] {maxRow, maxCount};
}
}
Python
class Solution(object):
def rowAndMaximumOnes(self, mat):
"""
:type mat: List[List[int]]
:rtype: List[int]
"""
max_count = 0 # To store the maximum number of ones found so far
max_row = 0 # To store the index of the row with the maximum number of ones
# Iterate through each row
for i in range(len(mat)):
cur_count = 0 # To count the number of ones in the current row
# Count the number of ones in the current row
for j in range(len(mat[i])):
if mat[i][j] == 1:
cur_count += 1
# If the current row has more ones than the previous maximum, update max_row and max_count
if cur_count > max_count:
max_count = cur_count
max_row = i
# Return the result as a list [max_row, max_count]
return [max_row, max_count]
Javascript
/**
* @param {number[][]} mat
* @return {number[]}
*/
var rowAndMaximumOnes = function(mat) {
let maxCount = 0; // To store the maximum number of ones found so far
let maxRow = 0; // To store the index of the row with the maximum number of ones
// Iterate through each row of the matrix
for (let i = 0; i < mat.length; i++) {
let curCount = 0; // Variable to count the ones in the current row
// Count the number of ones in the current row
for (let j = 0; j < mat[i].length; j++) {
if (mat[i][j] === 1) {
curCount++;
}
}
// Update maxCount and maxRow if the current row has more ones than the previous max
if (curCount > maxCount) {
maxCount = curCount;
maxRow = i;
}
}
// Return the result as an array [maxRow, maxCount]
return [maxRow, maxCount];
};
Bonus Tip
In C++, the Standard Template Library (STL) provides several useful functions that can help simplify the code, one of which is the std::count function. This function can be used to count the occurrences of a particular value in a given range.
For example, if we want to count how many 1's are in a row of the matrix, we can use std::count to do this more concisely.
Syntax: std::count(start_iterator, end_iterator, value_to_count);
Where:
- start_iterator is the iterator to the beginning of the range.
- end_iterator is the iterator to the end of the range.
- value_to_count is the value you want to count (in this case, 1).
Time Complexity : O(m*n)
To determine the time complexity, let’s break down the operations performed in the function:
- Outer Loop: The function iterates through each row of the matrix. The number of rows is denoted as m. So, the outer loop runs m times.
- Inner Loop: For each row, the function iterates through each element in that row. The number of elements (columns) in each row is denoted as n. So, for each row, the inner loop runs n times.
- Operations Inside the Inner Loop: Inside the inner loop, there’s a constant-time check (if condition), which takes O(1) time for each element. This means that for each element, the function performs a constant amount of work.
Total Time Complexity:
- The outer loop runs m times (one for each row).
- The inner loop runs n times for each row (one for each element in the row).
Thus, for every row, the inner loop performs n operations, and the outer loop runs m times. Therefore, the total number of operations is m×n.
Thus, the time complexity of the function is O(m×n).
Space Complexity: O(1)
- Input Space:
- The input is the matrix mat, which is a 2D array with dimensions m x n (where m is the number of rows and n is the number of columns).
- This matrix is passed as an argument to the function, so the space used by the input is not counted in the space complexity (since it is given as input).
- Auxiliary Space (Space used by the function itself):
- The function uses a few variables to track the state:
- maxCount: Stores the maximum count of ones found so far. This is a single integer, so it requires constant space, i.e., O(1).
- maxRow: Stores the index of the row with the maximum number of ones. This is also a single integer, requiring constant space, i.e., O(1).
- curCount: Stores the count of ones in the current row. Again, this is a single integer, requiring constant space, i.e., O(1).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.
The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.
Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.