Skip to content

1253. Reconstruct a 2-Row Binary Matrix 👍

  • Time:
  • Space: 
 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
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  vector<vector<int>> reconstructMatrix(int upper, int lower,
                                        vector<int>& colsum) {
    if (upper + lower != accumulate(colsum.begin(), colsum.end(), 0))
      return {};
    if (min(upper, lower) <
        ranges::count_if(colsum, [](int c) { return c == 2; }))
      return {};

    vector<vector<int>> ans(2, vector<int>(colsum.size()));

    for (int j = 0; j < colsum.size(); ++j)
      if (colsum[j] == 2) {
        ans[0][j] = 1;
        ans[1][j] = 1;
        --upper;
        --lower;
      }

    for (int j = 0; j < colsum.size(); ++j) {
      if (colsum[j] == 1 && upper > 0) {
        ans[0][j] = 1;
        --colsum[j];
        --upper;
      }

      if (colsum[j] == 1 && lower > 0) {
        ans[1][j] = 1;
        --lower;
      }
    }

    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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
    if (upper + lower != Arrays.stream(colsum).sum())
      return new ArrayList<>();

    int count = 0;
    for (int c : colsum)
      if (c == 2)
        ++count;

    if (Math.min(upper, lower) < count)
      return new ArrayList<>();

    int[][] ans = new int[2][colsum.length];

    for (int j = 0; j < colsum.length; ++j)
      if (colsum[j] == 2) {
        ans[0][j] = 1;
        ans[1][j] = 1;
        --upper;
        --lower;
      }

    for (int j = 0; j < colsum.length; ++j) {
      if (colsum[j] == 1 && upper > 0) {
        ans[0][j] = 1;
        --colsum[j];
        --upper;
      }

      if (colsum[j] == 1 && lower > 0) {
        ans[1][j] = 1;
        --lower;
      }
    }

    return new ArrayList(Arrays.asList(ans[0], ans[1]));
  }
}

 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
class Solution:
  def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
    if upper + lower != sum(colsum):
      return []
    if min(upper, lower) < colsum.count(2):
      return []

    ans = [[0] * len(colsum) for _ in range(2)]

    for j, c in enumerate(colsum):
      if c == 2:
        ans[0][j] = 1
        ans[1][j] = 1
        upper -= 1
        lower -= 1

    for j, c in enumerate(colsum):
      if c == 1 and upper > 0:
        ans[0][j] = 1
        c -= 1
        upper -= 1
      if c == 1 and lower > 0:
        ans[1][j] = 1
        lower -= 1

    return ans