2643. Row With Maximum Ones

EasyArrayMatrix
Leetcode Link

Problem Description

Given a matrix where each cell is either a 0 or a 1, we need to identify which row contains the most 1s. 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 1s. If there are multiple rows with the same maximum count of 1s, 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 1s 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 1s.

As we iterate over each row:

  1. We count the 1s,
  2. We compare this count with the current maximum (stored in ans[1]),
  3. 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 1s in that row. At the end of iteration, ans will contain the index of the desired row and the highest count of ones found.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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:

  1. Initialize an answer list ans = [0, 0]. The first element is the row index (initialized to 0) and the second element is the count of 1s (also initialized to 0).

  2. Iterate over each row in the matrix with a loop structure, keeping track of the current row index using Python's enumerate function.

    1for i, row in enumerate(mat):

  3. Within the loop, count the number of 1s in the current row. This is done by using the count method on the row list:

    1cnt = row.count(1)

  4. Check if the current row's 1s count (cnt) is greater than the maximum count of 1s found so far (ans[1]). If it is, then update the answer list with the current row index and the count:

    1if ans[1] < cnt:
2    ans = [i, cnt]

  5. Once all rows have been checked, the list ans contains the required index and the count of 1s. This list is then returned as the final output.

    1return 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Imagine we have the following matrix:

1matrix = [
2    [0, 1, 1, 0],
3    [0, 1, 1, 1],
4    [1, 1, 0, 0],
5    [0, 0, 0, 0]
6]

We need to identify which row has the most 1s.

  1. Initialize an answer list ans = [0, 0]. This list will hold the index of the row with the maximum 1s and the count of 1s in that respective row.

  2. Start iterating over each row in the matrix using enumerate:

    • For the first row (i=0), the count of 1s is 2.
      • ans remains [0, 0] because 2 (current row's 1s count) is not greater than 0 (maximum 1s count so far).
    • For the second row (i=1), the count of 1s is 3.
      • Update ans to [1, 3] because 3 is greater than the maximum 1s count so far, which was 0.
    • For the third row (i=2), the count of 1s is 2.
      • ans remains [1, 3] because 2 is not greater than 3 (current maximum 1s count).
    • The fourth row (i=3) has a count of 1s as 0.
      • ans remains [1, 3] since 0 is not greater than 3.

  3. Now that all rows have been checked, ans contains the index of the row with the maximum number of 1s 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 1s, 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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫