Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Row With Maximum Ones(easy)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a binary matrix that has dimensions m * n, consisting of ones and zeros. Determine the row that contains the highest number of ones and return two values: the zero-based index of this row and the actual count of ones it possesses.

If there is a tie, i.e., multiple rows contain the same maximum number of ones, we must select the row with the lowest index.

Examples

Example 1:

  • Input: [[1, 0], [1, 1], [0, 1]]
  • Expected Output: [1, 2]
  • Justification: The second row [1, 1] contains the most ones, so the output is [1, 2].

Example 2:

  • Input: [[0, 1, 1], [0, 1, 1], [1, 1, 1]]
  • Expected Output: [2, 3]
  • Justification: The third row [1, 1, 1] has the most ones, leading to the output [2, 3].

Example 3:

  • Input: [[1, 0, 1], [0, 0, 1], [1, 1, 0]]
  • Expected Output: [0, 2]
  • Justification: Both the first and third rows contain two ones, but we choose the first due to its lower index, resulting in [0, 2].

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • mat[i][j] is either 0 or 1.

Solution

The fundamental task is to identify the row with the maximum number of ones and simultaneously track the number of ones in this row.

To solve this problem, we will systematically examine each row of a given binary matrix to identify the row with the highest number of 1s. The solution involves iterating over each row, counting the 1s present, and comparing this count with the highest number of 1s recorded so far. We maintain two variables: one for the highest count of 1s encountered, and another for the index of the row where this occurred. This method ensures we check every element in the matrix precisely once, leading to an efficient approach in determining the row that contains the maximum number of 1s.

Step-by-Step Algorithm

  1. Initialize Variables: Set up two variables: maxOnesCount, initially 0, for tracking the maximum number of 1s found in any row; and maxOnesIdx, initially 0, for storing the index of the row with this maximum count.

  2. Iterate Through Each Row: Loop through each row of the matrix. For every row, perform the following steps:

    a. Count 1s in the Current Row: Initialize a counter for the number of 1s in this row. Traverse through each element of the row, incrementing the counter for each 1 encountered.

    b. Update Maximum Count and Row Index: If the count of 1s in the current row exceeds maxOnesCount, update maxOnesCount with the new count and set maxOnesIdx to the current row's index.

  3. Handling No 1s Scenario: If no 1s are found in the entire matrix, maxOnesIdx and maxOnesCount remain 0.

  4. Return the Result: At the end of the iteration, return [maxOnesIdx, maxOnesCount].

Algorithm Walkthrough

Image
  • Initialize maxOnesIdx to 0 and maxOnesCount to 0.
  • Loop through each row:
    • Row 0 [1, 0, 1]: Count of ones = 2. It is greater than maxOnesCount so update maxOnesIdx to 0 and maxOnesCount to 2.
    • Row 1 [0, 0, 1]: Count of ones = 1. It is not greater than maxOnesCount, no update occurs.
    • Row 2 [1, 1, 0]: Count of ones = 2. It is equal to maxOnesCount, so no update occurs to maintain the smallest index.
  • Return [maxOnesIdx, maxOnesCount] which yields [0, 2].

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Outer loop (rows): The outer loop iterates through each row of the matrix. If there are M rows, this loop runs O(M) times.

  • Inner loop (columns): For each row, the inner loop counts the number of ones by iterating through all the columns. If each row has N columns, the inner loop runs O(N) times for each row.

  • Therefore, the total time complexity is O(M \times N), where M is the number of rows and N is the number of columns in the matrix.

Overall time complexity: O(M \times N).

Space Complexity

  • Constant space: The algorithm uses a few additional variables (maxOnesIdx, maxOnesCount, and onesCount), all of which require constant space, O(1).

  • The result array new int[]{maxOnesIdx, maxOnesCount} also takes constant space, O(1).

Overall space complexity: O(1).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible