1605. Find Valid Matrix Given Row and Column Sums

Time: O(mn)

Space: O(mn)

Intuition

Find values of x, y, z given only row/column sum constraints and a grid with 0s and 1s. Multiple solutions exist; find any valid one.

Algorithm

1Set z = min of any cell. Compute remaining row/column sums. Distribute y and x greedily.

Common Pitfalls

•Any valid assignment works. Start with minimum cell value as z, then fill greedily.

1605.cs

// Approach: Greedy — fill each cell with min(rowSum[i], colSum[j]) and subtract from both.
// Time: O(mn) Space: O(mn)

public class Solution
{
    public int[][] RestoreMatrix(int[] rowSum, int[] colSum)
    {
        int m = rowSum.Length;
        int n = colSum.Length;
        int[][] ans = new int[m][];

        for (int i = 0; i < m; ++i)
            ans[i] = new int[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;
    }
}

Was this solution helpful?