Row With Maximum Ones - Practice Coding Problems

Row With Maximum Ones - Problem

Array Matrix Easy

Given an 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.

Input & Output

Example 1 — Basic Case

$ Input: mat = [[0,1,1,1],[0,0,1,1],[0,0,0,1]]

› Output: [0,3]

💡 Note: Row 0 has 3 ones, Row 1 has 2 ones, Row 2 has 1 one. Maximum is 3 in row 0.

Example 2 — Tie Breaking

$ Input: mat = [[0,0],[1,1],[0,0]]

› Output: [1,2]

💡 Note: Only Row 1 has ones (2 ones), so return [1,2].

Example 3 — Multiple Ties

$ Input: mat = [[0,1],[1,0],[0,1]]

› Output: [0,1]

💡 Note: Rows 0, 1, and 2 all have 1 one each. Return smallest row index [0,1].

Constraints

1 ≤ m, n ≤ 100
mat[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 0s and 1s

Count Ones

Count 1s in each row

Find Maximum

Return [row_index, count] of row with most 1s

Key Takeaway

🎯 Key Insight: Process rows sequentially to naturally handle ties by preferring smaller indices

Asked in

M Microsoft 15 a Amazon 12

The key insight is to count ones in each row sequentially, which naturally handles tie-breaking by preferring earlier rows. Best approach is simple iteration with optional early exit optimization. Time: O(m×n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Early Exit on All Ones	O(m×n)	O(1)	Same counting approach but with early exit when we find a row with all ones
Brute Force - Count Ones in Each Row	O(m×n)	O(1)	Count ones in each row and track the row with maximum count

Optimized - Early Exit on All Ones — Algorithm Steps

Step 1: Initialize max count and row index tracking variables
Step 2: For each row, count ones and check if it equals column count
Step 3: If count equals columns, return immediately (optimal case)
Step 4: Otherwise update best row and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Rows

Count ones in each row sequentially

Check for All Ones

If count equals column count, exit early

Early Return

No need to check remaining rows

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int mat[][100], int rows, int cols, int* result) {
    int maxCount = -1;
    int maxRow = 0;
    
    for (int i = 0; i < rows; i++) {
        int count = 0;
        for (int j = 0; j < cols; j++) {
            count += mat[i][j];
        }
        if (count > maxCount) {
            maxCount = count;
            maxRow = i;
            // Early exit if we found all ones
            if (count == cols) {
                break;
            }
        }
    }
    
    result[0] = maxRow;
    result[1] = maxCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parser for 2D array
    int mat[100][100];
    int rows = 0, cols = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            cols = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '1') {
                    mat[rows][cols++] = *ptr - '0';
                }
                ptr++;
            }
            rows++;
        }
        ptr++;
    }
    
    int result[2];
    solution(mat, rows, cols, result);
    printf("[%d,%d]\n", result[0], result[1]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Worst case still checks all elements, best case exits after finding all-ones row

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for tracking variables

✓ Linear Space

24.0K Views

Medium Frequency

~8 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Early Exit on All Ones — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler