1605. Find Valid Matrix Given Row and Column Sums


Problem Description

In this problem, you are provided with two arrays, rowSum and colSum. These arrays represent the sum of the elements in each row and column, respectively, of a 2D matrix. However, you are not given the actual values in the matrix, only these sums. Your goal is to reconstruct any 2D matrix that has non-negative integers and satisfies the given rowSum and colSum. The size of the matrix will be rowSum.length rows and colSum.length columns. You are guaranteed that there is at least one valid matrix that meets the requirements.

Intuition

To approach this problem, we can iterate through the matrix, starting from the top-left cell, and assign each cell a value that is the minimum between the current row's sum and the current column's sum. The intuition behind this strategy is that by assigning the minimum value, we are ensuring that we never exceed the sum requirements for either the row or the column.

By iteratively updating the sums, we are accounting for the value we've placed in each cell. When the minimum value is chosen, it reduces the remaining row or column sum without overshooting the required sum. After an allocation, we deduct the chosen value from both sums. This strategy preserves the constraints for every step since we only allocate as much as we can 'afford' from both the row and the column at that point.

The process continues until we've filled the entire matrix. At the end of this process, we have constructed a valid matrix that fulfills both row and column sum requirements because we've continuously deduct the allocated numbers from our sum arrays, ensuring that the end state satisfies the original conditions.

Learn more about Greedy patterns.

Solution Approach

The algorithm for the solution takes advantage of a simple greedy approach and basic properties of matrices. The following steps are involved in the solution:

  1. Initialize the matrix ans to be of size m x n, where m is the number of items in rowSum, and n is the number of items in colSum. All elements in ans are initialized to zero.

  2. Iterate through each element of matrix ans, index by i for the rows and j for the columns.

  3. For each element ans[i][j], calculate the minimum value between rowSum[i] and colSum[j], which indicates the allowable value for this position that satisfies both the row's and column's sum constraints.

  4. Assign ans[i][j] this minimum value, which is the greedy choice of allocating as much as possible to the current cell without exceeding the sums for its row and column.

  5. Decrease the value of rowSum[i] and colSum[j] by the amount just allocated to ans[i][j]. This step is important as it updates the remaining sums for the row and column, reflecting the fact that we've already used part of those sums for element ans[i][j].

  6. Continue this process throughout the entire matrix, filling in each element with the calculated value.

Data Structures:

  • A 2D array ans to store the matrix values that we are building.

  • The input arrays rowSum and colSum are modified in place to keep track of the remaining sums after each allocation.

Patterns and Properties Used:

  • Greedy approach: By constantly making the locally optimal choice of picking the minimum possible value for each cell, we build up to a globally optimal solution that meets all conditions.

  • Matrix properties: The solution exploits the property that each row and column in the matrix has a fixed sum, and any allocation in an individual cell affects both the row's and column's sum.

This approach guarantees that by the end, when all cells are filled, the remaining sums for both rows and columns will be zero, indicating that we've met all the rowSum and colSum constraints correctly. Our solution effectively constructs a valid matrix with non-negative integers that fits the given row and column sums.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

To illustrate the solution approach, let's consider a small example where we have rowSum = [5, 7] and colSum = [8, 4]. We need to construct a matrix that satisfies these row and column sums.

We'll follow the steps outlined in the solution approach:

  1. Initialize ans as a 2x2 matrix with all elements set to zero (since rowSum.length is 2 and colSum.length is 2):

    1ans = [
    2  [0, 0],
    3  [0, 0]
    4]
  2. Start iterating through the elements of the matrix. We begin with i = 0 (first row) and j = 0 (first column).

  3. Compute the minimum between rowSum[i] and colSum[j]. For ans[0][0], this minimum is min(5, 8) which equals 5.

  4. Assign ans[0][0] the value 5:

    1ans = [
    2  [5, 0],
    3  [0, 0]
    4]
  5. Subtract the allocated value from rowSum[0] and colSum[0]:

    • New rowSum = [0, 7]
    • New colSum = [3, 4]
  6. Repeat steps 2-5 for the next element, ans[0][1]:

    • The minimum of rowSum[0] and colSum[1] is min(0, 4) which equals 0.
    • ans[0][1] is set to 0.
    • rowSum and colSum remain the same since the allocated number is 0.
    1ans = [
    2  [5, 0],
    3  [0, 0]
    4]
  7. For ans[1][0], we take the minimum of rowSum[1] and colSum[0], which is min(7, 3) equals 3.

    • ans[1][0] is set to 3.

    • Update rowSum and colSum:

    • New rowSum = [0, 4]

    • New colSum = [0, 4]

    1ans = [
    2  [5, 0],
    3  [3, 0]
    4]
  8. Finally for ans[1][1], the minimum of rowSum[1] and colSum[1] is min(4, 4) equals 4.

    • ans[1][1] is set to 4.

    • Update rowSum and colSum:

    • New rowSum = [0, 0]

    • New colSum = [0, 0]

    1ans = [
    2  [5, 0],
    3  [3, 4]
    4]

At this point, we have filled the matrix while satisfying the row and column sums described by rowSum and colSum. The final matrix is:

1ans = [
2  [5, 0],
3  [3, 4]
4]

And thus we have reconstructed any 2D matrix using the solution approach, successfully meeting the given rowSum and colSum requirements.

Solution Implementation

1class Solution:
2    def restoreMatrix(self, rowSums: List[int], colSums: List[int]) -> List[List[int]]:
3        # Get the number of rows and columns from the given sums
4        num_rows, num_cols = len(rowSums), len(colSums)
5      
6        # Initialize a matrix filled with zeros with dimensions (num_rows x num_cols)
7        matrix = [[0] * num_cols for _ in range(num_rows)]
8      
9        # Iterate through each cell in the matrix
10        for i in range(num_rows):
11            for j in range(num_cols):
12                # Determine the value at matrix[i][j] by taking the minimum between
13                # the current row sum and column sum, to satisfy both constraints
14                value = min(rowSums[i], colSums[j])
15                matrix[i][j] = value
16              
17                # Subtract the chosen value from the respective row sum and column sum
18                rowSums[i] -= value
19                colSums[j] -= value
20              
21        # Return the restored matrix that satisfies the row and column sums
22        return matrix
23
1class Solution {
2  
3    // Restores the matrix given the sum of every row and every column.
4    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
5        // Get the number of rows and columns from the size of the passed arrays
6        int rowCount = rowSum.length;
7        int colCount = colSum.length;
8      
9        // Initialize the matrix to return
10        int[][] restoredMatrix = new int[rowCount][colCount];
11
12        // Iterate over each cell in the matrix to calculate its value
13        for (int row = 0; row < rowCount; ++row) {
14            for (int col = 0; col < colCount; ++col) {
15                // Determine the minimum value to satisfy both rowSum and colSum constraints
16                int value = Math.min(rowSum[row], colSum[col]);
17                restoredMatrix[row][col] = value;
18              
19                // After setting the value for restoredMatrix[row][col], subtract it from 
20                // the corresponding rowSum and colSum to maintain the sum constraints
21                rowSum[row] -= value;
22                colSum[col] -= value;
23            }
24        }
25        // Return the restored matrix that matches the given row and column sums
26        return restoredMatrix;
27    }
28}
29
1#include <vector>
2#include <algorithm> // to use the std::min function
3
4class Solution {
5public:
6    // Restores a matrix based on given row and column sums.
7    // - row_sum represents the sum of the elements for each row.
8    // - col_sum represents the sum of the elements for each column.
9    std::vector<std::vector<int>> restoreMatrix(std::vector<int>& row_sum, std::vector<int>& col_sum) {
10        int rows = row_sum.size(); // Number of rows in the matrix.
11        int cols = col_sum.size(); // Number of columns in the matrix.
12        std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols));
13
14        // Iterate through each cell of the matrix
15        for (int i = 0; i < rows; ++i) {
16            for (int j = 0; j < cols; ++j) {
17                // Find the minimum value between the current row sum and column sum.
18                int value = std::min(row_sum[i], col_sum[j]);
19                matrix[i][j] = value; // Assign the calculated value to the current cell.
20
21                // Subtract the assigned value from both row and column sums.
22                row_sum[i] -= value; 
23                col_sum[j] -= value;
24            }
25        }
26
27        // The matrix is now restored such that it meets the row and column sums criteria.
28        return matrix;
29    }
30};
31
1function restoreMatrix(rowSums: number[], colSums: number[]): number[][] {
2    const numRows = rowSums.length; // Number of rows based on rowSums length
3    const numCols = colSums.length; // Number of columns based on colSums length
4  
5    // Initialize a 2D array 'matrix' with dimensions numRows x numCols filled with zeros
6    const matrix: number[][] = Array.from({ length: numRows }, () => new Array(numCols).fill(0));
7
8    // Iterate over each cell in the matrix
9    for (let i = 0; i < numRows; i++) {
10        for (let j = 0; j < numCols; j++) {
11            // Determine the minimum value between the current row sum and column sum
12            const minSum = Math.min(rowSums[i], colSums[j]);
13          
14            // Assign that minimum value to the current matrix cell
15            matrix[i][j] = minSum;
16          
17            // Update the remaining sum for the current row and column
18            rowSums[i] -= minSum;
19            colSums[j] -= minSum;
20        }
21    }
22  
23    // Return the constructed matrix
24    return matrix;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(m * n), where m is the number of rows and n is the number of columns. This is because the code contains two nested loops: the outer loop iterating over each row, and the inner loop iterating over each column. On each iteration, it performs a constant amount of work (calculating the minimum and updating rowSum and colSum).

Space Complexity

The space complexity of the code is O(m * n), this space is used to store the answer matrix ans. Other than that, the only extra space used is a constant amount for variables like x, i, j, and the space to copy and update the rowSum and colSum arrays, which does not depend on the size of the input and thus does not increase the order of space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄