# Row With Maximum Ones
**Difficulty:** EASY
[External](https://leetcode.com/problems/row-with-maximum-ones)
Canonical: https://scaleengineer.com/dsa/problems/row-with-maximum-ones
**Data structures:** Array, Matrix
---
## Problem
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._

**Example 1:**

**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]. 

**Example 2:**

**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].

**Example 3:**

**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`.

# Approaches
## Brute-Force with Auxiliary Storage
This approach uses an auxiliary array to store the count of ones for each row. It first populates this array by iterating through the matrix, and then performs a second pass over the auxiliary array to find the row with the maximum number of ones.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. The first pass to count ones takes O(m * n) time, and the second pass to find the maximum takes O(m) time. The total time complexity is dominated by the first pass. · **Space:** O(m), as an auxiliary array of size `m` is used to store the count of ones for each row.
**Pros:** The logic is clearly separated into two steps: counting and finding the maximum, which might be easier to reason about.; The code is straightforward to write and understand.
**Cons:** It uses extra space of O(m), where m is the number of rows. This is inefficient compared to a constant space solution.; It requires two passes over the rows (one to populate the counts array, one to find the max), which is less performant than a single-pass solution.
### Explanation
The core idea is to separate the problem into two distinct phases: counting and finding the maximum.

First, we create an array, let's call it `ones_counts`, with the same number of elements as there are rows in the matrix. We then iterate through each row of the input matrix `mat`, count the number of `1`s, and store this count in the corresponding index of our `ones_counts` array.

After the first phase, `ones_counts[i]` will hold the number of ones in `mat[i]`. In the second phase, we simply iterate through the `ones_counts` array to find the maximum value. We keep track of the maximum count found so far and the index at which it occurred. The first time we encounter the maximum value, we record its index. Due to the tie-breaking rule (smallest row number), we don't update the index if we find another row with the same maximum count.

```java
class Solution {
    public int[] rowAndMaximumOnes(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] onesCounts = new int[m];

        for (int i = 0; i < m; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    count++;
                }
            }
            onesCounts[i] = count;
        }

        int maxOnes = -1;
        int rowIndex = -1;

        for (int i = 0; i < m; i++) {
            if (onesCounts[i] > maxOnes) {
                maxOnes = onesCounts[i];
                rowIndex = i;
            }
        }

        return new int[]{rowIndex, maxOnes};
    }
}
```
### Algorithm
*   Create an integer array `ones_counts` of size `m` (number of rows).
*   Iterate through the matrix from row `i = 0` to `m-1`.
*   For each row `i`, count the number of `1`s and store the result in `ones_counts[i]`.
*   Initialize `max_count = -1` and `result_index = -1`.
*   Iterate through `ones_counts` from `i = 0` to `m-1`.
*   If `ones_counts[i]` is greater than `max_count`, update `max_count` to `ones_counts[i]` and `result_index` to `i`.
*   Return `[result_index, max_count]`.

## Single-Pass Iteration
This is the most efficient approach, solving the problem in a single pass through the matrix. It maintains two variables to track the row index with the maximum ones and the count of those ones. By updating these variables as we iterate, we avoid the need for any extra storage.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. Every element in the matrix is visited exactly once. · **Space:** O(1), as it only uses a few variables to store the result and intermediate counts, irrespective of the matrix size.
**Pros:** Extremely efficient, using constant extra space O(1).; Solves the problem in a single pass, minimizing data traversal.; Simple to implement and understand.
**Cons:** There are no significant disadvantages to this approach as it is optimal for the given problem constraints.
### Explanation
This optimized approach combines the counting and comparison steps into a single loop. We iterate through each row of the matrix one by one. For each row, we calculate the number of ones it contains. Immediately after counting, we compare this count with the maximum count found so far.

We maintain two variables, `maxOnes` and `rowIndex`, initialized to track the maximum count and the corresponding row index. If the current row's one-count is strictly greater than `maxOnes`, we update `maxOnes` with the new count and `rowIndex` with the current row's index. This 'strictly greater' condition (`>`) elegantly handles the tie-breaking requirement: if a subsequent row has the same number of ones as the current maximum, no update occurs, thus preserving the smaller row index. This method processes the entire matrix in one go, making it optimal in terms of both time and space.

```java
class Solution {
    public int[] rowAndMaximumOnes(int[][] mat) {
        int maxOnes = -1;
        int rowIndex = -1;

        for (int i = 0; i < mat.length; i++) {
            int currentOnes = 0;
            for (int num : mat[i]) {
                if (num == 1) {
                    currentOnes++;
                }
            }
            if (currentOnes > maxOnes) {
                maxOnes = currentOnes;
                rowIndex = i;
            }
        }
        return new int[]{rowIndex, maxOnes};
    }
}
```
### Algorithm
*   Initialize `max_ones_count = -1` and `row_index = -1`.
*   Iterate through each row `i` of the matrix from `0` to `m-1`.
*   Inside the loop, initialize `current_ones_count = 0`.
*   Iterate through the elements of the current row `i` and increment `current_ones_count` for each `1` found.
*   After counting, check if `current_ones_count > max_ones_count`.
*   If it is, update `max_ones_count = current_ones_count` and `row_index = i`.
*   After the outer loop finishes, return `[row_index, max_ones_count]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] RowAndMaximumOnes(int[][] mat) {
        int[] ans = new int[2];
        for (int i = 0; i < mat.Length; i++) {
            int cnt = mat[i].Sum();
            if (ans[1] < cnt) {
                ans = new int[] {
                    i,
                    cnt
                };
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int[] rowAndMaximumOnes(int[][] mat) {
    int[] ans = new int[2];
    for (int i = 0; i < mat.length; ++i) {
      int cnt = 0;
      for (int x : mat[i]) {
        if (x == 1) {
          ++cnt;
        }
      }
      if (ans[1] < cnt) {
        ans[0] = i;
        ans[1] = cnt;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> rowAndMaximumOnes(vector<vector<int>> &mat) {
    vector<int> ans(2);
    for (int i = 0; i < mat.size(); ++i) {
      int cnt = 0;
      for (auto &x : mat[i]) {
        cnt += x == 1;
      }
      if (ans[1] < cnt) {
        ans[0] = i;
        ans[1] = cnt;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]: ans = [0, 0] for i, row in enumerate(mat): cnt = row . count(1) if ans[1] < cnt: ans = [i, cnt] return ans

```