Problem

Given the following details of a matrix with n columns and 2 rows :

  • The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
  • The sum of elements of the 0-th(upper) row is given as upper.
  • The sum of elements of the 1-st(lower) row is given as lower.
  • The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Examples

Example 1

1
2
3

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation:[[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2

1
2

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3

1
2

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints

  • 1 <= colsum.length <= 10^5
  • 0 <= upper, lower <= colsum.length
  • 0 <= colsum[i] <= 2

Solution

Method 1 – Greedy Assignment

Intuition

Assign 1s in columns with colsum=2 first (must be 1 in both rows), then assign 1s in columns with colsum=1 to the row with more remaining sum. If at any point the assignment is impossible, return empty.

Approach

  1. Initialize two arrays for the upper and lower rows.
  2. For each column:
    • If colsum[i] == 2, set both rows to 1, decrement both upper and lower.
    • If colsum[i] == 1, assign 1 to the row with more remaining sum (prefer upper if equal), decrement that sum.
    • If colsum[i] == 0, set both to 0.
  3. If at any point upper or lower goes negative, or not both zero at the end, return empty.
  4. Otherwise, return the constructed matrix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<int> up(n), low(n);
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 2) {
                up[i] = low[i] = 1;
                --upper; --lower;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 1) {
                if (upper > 0) { up[i] = 1; --upper; }
                else { low[i] = 1; --lower; }
            }
        }
        if (upper != 0 || lower != 0) return {};
        return {up, low};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
    n := len(colsum)
    up := make([]int, n)
    low := make([]int, n)
    for i := 0; i < n; i++ {
        if colsum[i] == 2 {
            up[i], low[i] = 1, 1
            upper--
            lower--
        }
    }
    for i := 0; i < n; i++ {
        if colsum[i] == 1 {
            if upper > 0 {
                up[i] = 1
                upper--
            } else {
                low[i] = 1
                lower--
            }
        }
    }
    if upper != 0 || lower != 0 {
        return [][]int{}
    }
    return [][]int{up, low}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;
class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        int[] up = new int[n], low = new int[n];
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 2) {
                up[i] = low[i] = 1;
                upper--; lower--;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (colsum[i] == 1) {
                if (upper > 0) { up[i] = 1; upper--; }
                else { low[i] = 1; lower--; }
            }
        }
        if (upper != 0 || lower != 0) return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>()); ans.add(new ArrayList<>());
        for (int i = 0; i < n; ++i) { ans.get(0).add(up[i]); ans.get(1).add(low[i]); }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun reconstructMatrix(upper: Int, lower: Int, colsum: IntArray): List<List<Int>> {
        var up = upper
        var low = lower
        val n = colsum.size
        val row1 = MutableList(n) { 0 }
        val row2 = MutableList(n) { 0 }
        for (i in 0 until n) {
            if (colsum[i] == 2) {
                row1[i] = 1; row2[i] = 1
                up--; low--
            }
        }
        for (i in 0 until n) {
            if (colsum[i] == 1) {
                if (up > 0) { row1[i] = 1; up-- }
                else { row2[i] = 1; low-- }
            }
        }
        if (up != 0 || low != 0) return emptyList()
        return listOf(row1, row2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: list[int]) -> list[list[int]]:
        n = len(colsum)
        up = [0] * n
        low = [0] * n
        for i in range(n):
            if colsum[i] == 2:
                up[i] = low[i] = 1
                upper -= 1
                lower -= 1
        for i in range(n):
            if colsum[i] == 1:
                if upper > 0:
                    up[i] = 1
                    upper -= 1
                else:
                    low[i] = 1
                    lower -= 1
        if upper != 0 or lower != 0:
            return []
        return [up, low]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn reconstruct_matrix(mut upper: i32, mut lower: i32, colsum: Vec<i32>) -> Vec<Vec<i32>> {
        let n = colsum.len();
        let mut up = vec![0; n];
        let mut low = vec![0; n];
        for i in 0..n {
            if colsum[i] == 2 {
                up[i] = 1; low[i] = 1;
                upper -= 1; lower -= 1;
            }
        }
        for i in 0..n {
            if colsum[i] == 1 {
                if upper > 0 { up[i] = 1; upper -= 1; }
                else { low[i] = 1; lower -= 1; }
            }
        }
        if upper != 0 || lower != 0 { return vec![]; }
        vec![up, low]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
        const n = colsum.length;
        const up = Array(n).fill(0), low = Array(n).fill(0);
        for (let i = 0; i < n; ++i) {
            if (colsum[i] === 2) {
                up[i] = 1; low[i] = 1;
                upper--; lower--;
            }
        }
        for (let i = 0; i < n; ++i) {
            if (colsum[i] === 1) {
                if (upper > 0) { up[i] = 1; upper--; }
                else { low[i] = 1; lower--; }
            }
        }
        if (upper !== 0 || lower !== 0) return [];
        return [up, low];
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of colsum, since we scan the array twice.
  • 🧺 Space complexity: O(n), for the output matrix.