Find Valid Matrix Given Row and Column Sums Solution in Java

Problem Description

So, you want to create a matrix that satisfies certain row and column sums? Sounds easy, right? Just like trying to bake a cake without a recipe—sure, you can throw in some flour, sugar, and eggs, but good luck getting a cake that doesn’t resemble a pancake!

In this problem, you are given two arrays: rowSum and colSum. Your task is to fill a matrix such that the sum of each row matches the corresponding value in rowSum, and the sum of each column matches the corresponding value in colSum. It’s like trying to balance your budget while also keeping your friends happy—everyone wants a piece of the pie!

Code Solution


class Solution {
  public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
    final int m = rowSum.length;
    final int n = colSum.length;
    int[][] ans = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        ans[i][j] = Math.min(rowSum[i], colSum[j]);
        rowSum[i] -= ans[i][j];
        colSum[j] -= ans[i][j];
      }

    return ans;
  }
}

Approach

The approach here is as straightforward as a Sunday morning cartoon. We iterate through each cell of the matrix and fill it with the minimum of the remaining row and column sums. After placing a value, we update the respective row and column sums. This way, we ensure that we are always working with the most accurate sums, just like keeping track of your calories while trying to eat that entire pizza!

Time and Space Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. We are essentially visiting each cell of the matrix once.

Space Complexity: O(m * n) for storing the resulting matrix.

Real-World Example

Imagine you’re at a potluck dinner, and everyone has brought a dish. You need to make sure that each table has the right amount of food based on the number of guests. If one table has too much pasta and another has too little salad, you’ll have a culinary disaster on your hands! This problem is akin to ensuring that each table (row) has the right amount of food (sum) while also making sure that the total food available (column sums) is not exceeded.