Matrix Row and Column Sums: Find the Greatest

Computing row and column sums of a matrix, then finding the row and column with the greatest sum, is a two-accumulator nested-loop problem that appears in AMCAT and CoCubes coding sections as a warm-up before harder matrix problems.

The key insight: a single nested loop can update both the row accumulator and the column accumulator at each element, keeping the entire traversal to one pass instead of two.

What the Problem Asks

Given an m x n matrix of integers, the task is to compute:

• The sum of every row
• The sum of every column
• Which row has the greatest sum
• Which column has the greatest sum

Worked Example: 3x3 Matrix

Consider this input:

1  2  3
4  5  6
7  8  9

Row sums (left-to-right scan, one row at a time):

• Row 1: 1 + 2 + 3 = 6
• Row 2: 4 + 5 + 6 = 15
• Row 3: 7 + 8 + 9 = 24

Column sums (top-to-bottom scan, one column at a time):

• Column 1: 1 + 4 + 7 = 12
• Column 2: 2 + 5 + 8 = 15
• Column 3: 3 + 6 + 9 = 18

Row 3 holds the greatest row sum (24). Column 3 holds the greatest column sum (18). Notice the two results differ. The problem outputs them separately, not as a single value.

A common placement-test variation asks for the single greatest value across all six sums. For this matrix, that would still be 24 (row 3’s sum). Both interpretations share the same algorithm up to the final comparison.

Algorithm: Two Accumulators, One Pass

The standard approach uses two auxiliary arrays and a single nested traversal:

• Step 1: Declare rowSum[m] and colSum[n], both zero-initialised.
• Step 2: Traverse every element mat[i][j]. For each element, add it to rowSum[i] and to colSum[j] in the same step.
• Step 3: Scan rowSum from index 0 to m-1, tracking the index with the highest value. Call this maxR.
• Step 4: Scan colSum from index 0 to n-1, tracking the index with the highest value. Call this maxC.
• Step 5: Print rowSum[maxR] (greatest row sum) and colSum[maxC] (greatest column sum).

The zero-initialisation in Step 1 is correct for any integer matrix, including those with negative values. The accumulator sums a series of additions starting from 0. Do not initialise to the first element or to INT_MAX, since both are wrong for sum accumulation.

Steps 3 and 4 each run in O(m) and O(n) time, negligible against the O(m x n) traversal in Step 2. Total time is O(m x n).

Programs in C, Java, and Python

C

#include <stdio.h>
#define MAX 100

int main() {
    int m, n;
    printf("Enter rows and columns: ");
    scanf("%d %d", &m, &n);

    int mat[MAX][MAX];
    printf("Enter matrix elements:\n");
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &mat[i][j]);

    int rowSum[MAX] = {0};
    int colSum[MAX] = {0};

    /* Single pass: update both accumulators at each element */
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            rowSum[i] += mat[i][j];
            colSum[j] += mat[i][j];
        }

    for (int i = 0; i < m; i++)
        printf("Sum of row %d = %d\n", i + 1, rowSum[i]);
    for (int j = 0; j < n; j++)
        printf("Sum of column %d = %d\n", j + 1, colSum[j]);

    /* Find greatest row sum */
    int maxR = 0;
    for (int i = 1; i < m; i++)
        if (rowSum[i] > rowSum[maxR]) maxR = i;

    /* Find greatest column sum */
    int maxC = 0;
    for (int j = 1; j < n; j++)
        if (colSum[j] > colSum[maxC]) maxC = j;

    printf("Row %d has the greatest sum: %d\n", maxR + 1, rowSum[maxR]);
    printf("Column %d has the greatest sum: %d\n", maxC + 1, colSum[maxC]);

    return 0;
}

Java

public class MatrixRowColSum {
    public static void main(String[] args) {
        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int m = mat.length, n = mat[0].length;

        int[] rowSum = new int[m];
        int[] colSum = new int[n];

        /* Single pass: update both accumulators at each element */
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                rowSum[i] += mat[i][j];
                colSum[j] += mat[i][j];
            }

        for (int i = 0; i < m; i++)
            System.out.println("Sum of row " + (i + 1) + " = " + rowSum[i]);
        for (int j = 0; j < n; j++)
            System.out.println("Sum of column " + (j + 1) + " = " + colSum[j]);

        int maxR = 0, maxC = 0;
        for (int i = 1; i < m; i++)
            if (rowSum[i] > rowSum[maxR]) maxR = i;
        for (int j = 1; j < n; j++)
            if (colSum[j] > colSum[maxC]) maxC = j;

        System.out.println("Row " + (maxR + 1) + " has the greatest sum: " + rowSum[maxR]);
        System.out.println("Column " + (maxC + 1) + " has the greatest sum: " + colSum[maxC]);
    }
}

Python

def row_col_sums(mat):
    m, n = len(mat), len(mat[0])
    row_sum = [0] * m
    col_sum = [0] * n

    # Single pass: update both accumulators at each element
    for i in range(m):
        for j in range(n):
            row_sum[i] += mat[i][j]
            col_sum[j] += mat[i][j]

    for i in range(m):
        print(f"Sum of row {i + 1} = {row_sum[i]}")
    for j in range(n):
        print(f"Sum of column {j + 1} = {col_sum[j]}")

    max_r = row_sum.index(max(row_sum))
    max_c = col_sum.index(max(col_sum))

    print(f"Row {max_r + 1} has the greatest sum: {row_sum[max_r]}")
    print(f"Column {max_c + 1} has the greatest sum: {col_sum[max_c]}")


# Sample run
mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
row_col_sums(mat)

Expected Output

For the 3x3 sample input, all three programs produce:

Sum of row 1 = 6
Sum of row 2 = 15
Sum of row 3 = 24
Sum of column 1 = 12
Sum of column 2 = 15
Sum of column 3 = 18
Row 3 has the greatest sum: 24
Column 3 has the greatest sum: 18

These values match the hand-derived calculation in the worked example above. Verify any alternative implementation against these specific numbers before submitting to a placement test.

Complexity Analysis

Time and space complexity of the single-pass approach:

Metric	Value	Explanation
Time	O(m x n)	Every element visited once in the nested loop
Auxiliary space	O(m+n)	rowSum array (m entries) plus colSum array (n entries)
Finding max row	O(m)	One linear scan of rowSum after traversal
Finding max column	O(n)	One linear scan of colSum after traversal

The dominant cost is the O(m x n) traversal. A two-pass approach (one loop for row sums, a separate loop for column sums) is O(2mn) = O(mn) asymptotically, but traverses the data twice. GeeksforGeeks covers how row-wise and column-wise traversal differ in cache efficiency on large matrices.

On a square matrix, the O(m+n) auxiliary space equals O(2n) = O(n). For a 1000 x 1000 matrix, that is 2000 integers, well within acceptable limits for placement-test constraints.

Placement Test Variations

AMCAT and CoCubes occasionally adjust the problem. The four most common variations:

• Greatest sum across all rows and columns combined: Take the single maximum across the union of all row sums and all column sums. For the sample matrix that is 24 (row 3’s sum). Add one comparison loop over both arrays after computing them.
• 0-indexed output: Some online judges expect row index 2 rather than row 3 when reporting the result. Read the problem statement carefully before submitting.
• Non-square matrix (m not equal to n): The algorithm handles this without modification. Ensure colSum is sized to n, not m.
• Tie-breaking: When two rows share the maximum sum, most problems expect the first (lowest-index) row. Update maxR only when rowSum[i] > rowSum[maxR], not when it is equal.

The equilibrium index problem applies the same initialise-accumulate-then-compare pattern to a 1D array; solving it first makes the 2D matrix version feel mechanical. Problems involving symmetric pairs in an array also reinforce the habit of tracking index-value relationships, which the max-finding step in this problem depends on.

The single-pass approach, updating both rowSum[i] and colSum[j] inside the same inner loop, is a design pattern that recurs across matrix-heavy code well beyond placement exercises. If the next step after matrix fundamentals is building with real APIs, TinkerLLM starts at ₹299 and puts the same loop intuition to work on LLM API calls rather than textbook inputs.