Make Matrix Beautiful

JavaView on GFG

Time: O(n*m)

Space: O(n+m)

Problem Overview

Make all rows and columns have same sum with minimum increment operations.

See our study guide for structured GFG and LeetCode practice.

Intuition

Make all rows and columns have same sum with minimum increment operations.

Algorithm

1Target = max of all row sums and column sums. For each row: increment elements to reach target. Adjust columns accordingly.

Common Pitfalls

• Target is max(maxRowSum, maxColSum). Fill row by row; recalculate column sums. Total ops = n*target - sum(all elements).

Make Matrix Beautiful.java

Java

// Approach: Find each row and column max, then ensure every row/column sums to the global max.
// Time: O(n*m) Space: O(n+m)
class Solution {
    public static int balanceSums(int[][] mat) {
        int n = mat.length;

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

        // Calculate row and column sums
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rowSum[i] += mat[i][j];
                colSum[j] += mat[i][j];
            }
        }

        // Find the maximum sum among all row sums and column sums
        int maxSum = 0;
        for (int i = 0; i < n; i++) {
            maxSum = Math.max(maxSum, rowSum[i]);
            maxSum = Math.max(maxSum, colSum[i]);
        }

        // To make matrix beautiful, we need to make all row and column sums equal to
        // maxSum
        int operations = 0;
        for (int i = 0; i < n; i++)
            operations += maxSum - rowSum[i]; // Only row difference is enough since total increase should balance
                                              // column as well

        return operations;
    }
}

Was this solution helpful?