Row With Maximum Ones

Easy
298.

Row With Maximum Ones

Row With Maximum Ones is an easy coding problem on arrays and matrix, asked in Amazon and Microsoft interviews.

Given an m × n binary matrix mat, find the row with the most ones.

Return [rowIndex, count]. If several rows tie, return the one with the smallest index.

Example 1

Input
mat = [[0,1],[1,0]]
Output
[0,1]
Explanation
Both rows hold one 1, so the smaller index wins.

Example 2

Input
mat = [[0,0,0],[0,1,1]]
Output
[1,2]

Example 3

Input
mat = [[0,0],[1,1],[0,0]]
Output
[1,2]

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • mat[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var rowAndMaximumOnes = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Row With Maximum Ones — Solution in Python, Java & C++

Row With Maximum Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Row With Maximum Ones is an easy coding problem on arrays and matrix, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an m × n binary matrix mat, find the row with the most ones.

Return [rowIndex, count]. If several rows tie, return the one with the smallest index.

Example 1

Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows hold one 1, so the smaller index wins.

Example 2

Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]

Example 3

Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • mat[i][j] is 0 or 1.

Hints for Row With Maximum Ones

  1. Hint 1

    Since the entries are 0 and 1, a row's count of ones is just its sum.

  2. Hint 2

    Scan top to bottom and replace the best only on a strictly greater count — that is what keeps the smallest index on a tie.

How to solve Row With Maximum Ones

Each row's ones count is its sum; scan top to bottom and replace the best only on a strictly greater count.

Approach

  1. For each row, compute its sum.
  2. If the sum is greater than the best so far, record the row and the sum.
  3. Return [bestRow, bestCount].

Why it works

A strict comparison keeps the first row encountered among ties, which is the smallest index.

Complexity

  • Time — O(m · n)
  • Space — O(1)

Pitfalls

  • Initialise the best count to -1 so a matrix of all zeros returns row 0 with count 0.

Reference solution

Python

def rowAndMaximumOnes(mat):
    best_row, best_count = 0, -1
    for r, row in enumerate(mat):
        count = sum(row)
        if count > best_count:
            best_count = count
            best_row = r
    return [best_row, best_count]

Java

public static int[] rowAndMaximumOnes(int[][] mat) {
    int bestRow = 0, bestCount = -1;
    for (int r = 0; r < mat.length; r++) {
        int count = 0;
        for (int c = 0; c < mat[r].length; c++) count += mat[r][c];
        if (count > bestCount) {
            bestCount = count;
            bestRow = r;
        }
    }
    return new int[]{bestRow, bestCount};
}

C++

vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
    int bestRow = 0, bestCount = -1;
    for (int r = 0; r < (int) mat.size(); r++) {
        int count = 0;
        for (int v : mat[r]) count += v;
        if (count > bestCount) {
            bestCount = count;
            bestRow = r;
        }
    }
    return {bestRow, bestCount};
}

JavaScript

var rowAndMaximumOnes = function(mat) {
    let bestRow = 0, bestCount = -1;
    for (let r = 0; r < mat.length; r++) {
        let count = 0;
        for (let c = 0; c < mat[r].length; c++) count += mat[r][c];
        if (count > bestCount) {
            bestCount = count;
            bestRow = r;
        }
    }
    return [bestRow, bestCount];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal