# Reconstruct a 2-Row Binary Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix)
Canonical: https://scaleengineer.com/dsa/problems/reconstruct-a-2-row-binary-matrix
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Matrix
**Companies:** [American Express](https://scaleengineer.com/companies/american-express), [Grab](https://scaleengineer.com/companies/grab)
---
## 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.

**Example 1:**

**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:**

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

**Example 3:**

**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`

# Approaches
## Brute-Force with Backtracking
This approach explores all possible ways to construct the matrix. For columns where the sum is 1, there are two choices: place the '1' in the upper row or the lower row. We can use recursion with backtracking to explore all these choices and see if any of them lead to a valid matrix that satisfies the `upper` and `lower` row sum constraints.
**Time:** O(2^N) in the worst case, where N is the number of columns. This occurs when most or all `colsum[i]` values are 1, creating a binary decision tree of depth N. · **Space:** O(N), where N is the number of columns. This space is used for storing the result matrix and for the recursion call stack, which can go up to a depth of N.
**Pros:** Guaranteed to find a solution if one exists.; It is a direct, albeit naive, implementation of the problem's search space.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.; The implementation is more complex than the greedy approach.
### Explanation
The brute-force method systematically tries every combination for placing `1`s. We can define a recursive function that builds the matrix column by column. For each column, it makes a decision based on `colsum[i]`. If `colsum[i]` is 0 or 2, the choice is forced. If `colsum[i]` is 1, the function tries both placing the `1` in the upper row and in the lower row, leading to two recursive calls. This process explores a decision tree. If a path in the tree leads to a state where all columns are filled and the `upper` and `lower` sum constraints are met, a solution is found. If a path leads to an invalid state (e.g., needing to place a `1` but the row's required sum is already met), it backtracks and tries another path.

```java
class Solution {
    List<List<Integer>> result;
    int n;
    int[] colsum;

    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        this.n = colsum.length;
        this.colsum = colsum;
        Integer[] upperRow = new Integer[n];
        Integer[] lowerRow = new Integer[n];
        this.result = new ArrayList<>();
        result.add(Arrays.asList(upperRow));
        result.add(Arrays.asList(lowerRow));

        if (solve(0, upper, lower)) {
            return result;
        }
        return new ArrayList<>();
    }

    private boolean solve(int col, int upper, int lower) {
        if (upper < 0 || lower < 0) {
            return false;
        }
        if (col == n) {
            return upper == 0 && lower == 0;
        }

        if (colsum[col] == 2) {
            result.get(0).set(col, 1);
            result.get(1).set(col, 1);
            if (solve(col + 1, upper - 1, lower - 1)) return true;
        } else if (colsum[col] == 0) {
            result.get(0).set(col, 0);
            result.get(1).set(col, 0);
            if (solve(col + 1, upper, lower)) return true;
        } else { // colsum[col] == 1
            // Try upper row
            result.get(0).set(col, 1);
            result.get(1).set(col, 0);
            if (solve(col + 1, upper - 1, lower)) return true;

            // Backtrack and try lower row
            result.get(0).set(col, 0);
            result.get(1).set(col, 1);
            if (solve(col + 1, upper, lower - 1)) return true;
        }
        
        return false;
    }
}
```
### Algorithm
- Initialize an empty `2 x n` matrix `result`.
- Create a recursive helper function, say `solve(col, u, l)`, that attempts to fill the matrix from column `col` given that we still need to place `u` ones in the upper row and `l` ones in the lower row.
- **Base Case**: If `col == n` (all columns processed), check if `u == 0` and `l == 0`. If both are zero, a valid solution has been found, return `true`. Otherwise, return `false`.
- **Recursive Step** for column `col`:
  - If `u` or `l` is negative, it's an invalid path, return `false`.
  - Based on `colsum[col]`:
    - If `colsum[col] == 0`: Set `result[0][col] = 0`, `result[1][col] = 0`. Recurse with `solve(col + 1, u, l)`.
    - If `colsum[col] == 2`: Set `result[0][col] = 1`, `result[1][col] = 1`. Recurse with `solve(col + 1, u - 1, l - 1)`.
    - If `colsum[col] == 1`: This is a choice point. 
      1. Try placing `1` in the upper row: Set `result[0][col] = 1`, `result[1][col] = 0`. Recurse with `solve(col + 1, u - 1, l)`. If this call returns `true`, a solution is found, so return `true`.
      2. If not, backtrack and try placing `1` in the lower row: Set `result[0][col] = 0`, `result[1][col] = 1`. Recurse with `solve(col + 1, u, l - 1)`. If this call returns `true`, return `true`.
  - If no recursive path from the current state finds a solution, return `false`.
- The initial call is `solve(0, upper, lower)`. If it returns `true`, the `result` matrix holds the solution; otherwise, no solution exists.

## One-Pass Greedy with Pre-validation
A greedy approach can solve this problem efficiently in linear time. The core idea is to first check for obvious impossibility conditions. If the input is potentially valid, we can construct the matrix in a single pass. We handle the deterministic columns (where sum is 0 or 2) and then greedily fill the ambiguous columns (where sum is 1) by prioritizing one row until its required sum is met, then filling the other row.
**Time:** O(N), where N is the number of columns. The algorithm iterates through the `colsum` array a constant number of times. · **Space:** O(N), where N is the number of columns, required to store the `2 x N` result matrix.
**Pros:** Highly efficient with linear time complexity.; Simple to implement once the logic is understood.; Passes all constraints within the time limit.
**Cons:** The logic requires careful pre-validation to ensure the greedy choice is always valid.
### Explanation
This optimal approach avoids backtracking by making smart, greedy choices. It first validates if a solution is even possible. The total number of `1`s, given by `upper + lower`, must equal the total sum of `colsum`. Also, for every column with a sum of 2, we must place a `1` in both the upper and lower rows. If `upper` or `lower` is less than the number of such columns, it's impossible.

Once these conditions are verified, we know a solution can be constructed. We iterate through the columns one last time to build the result. For columns with sum 2, we place `1`s in both rows. For columns with sum 1, we greedily place a `1` in the upper row as long as it still needs `1`s (i.e., `upper > 0`). Once the upper row is full, we place the remaining `1`s in the lower row. Because of our initial checks, we are guaranteed to have just enough `1`s to complete the matrix correctly.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        long sum = 0;
        int twos = 0;
        for (int x : colsum) {
            sum += x;
            if (x == 2) {
                twos++;
            }
        }

        if (sum != upper + lower || upper < twos || lower < twos) {
            return new ArrayList<>();
        }

        upper -= twos;
        lower -= twos;

        List<Integer> upperRow = new ArrayList<>();
        List<Integer> lowerRow = new ArrayList<>();

        for (int c : colsum) {
            if (c == 2) {
                upperRow.add(1);
                lowerRow.add(1);
            } else if (c == 0) {
                upperRow.add(0);
                lowerRow.add(0);
            } else { // c == 1
                if (upper > 0) {
                    upperRow.add(1);
                    lowerRow.add(0);
                    upper--;
                } else {
                    upperRow.add(0);
                    lowerRow.add(1);
                    lower--;
                }
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        result.add(upperRow);
        result.add(lowerRow);
        return result;
    }
}
```
### Algorithm
- **Pre-validation**: First, perform some checks to quickly identify impossible cases.
  - Calculate the total sum of `colsum`. If it's not equal to `upper + lower`, no solution is possible, so return an empty list.
  - Count the number of columns where `colsum[i] == 2`. Let this be `twos`. A `1` must be placed in both rows for these columns. Thus, if `upper < twos` or `lower < twos`, it's impossible. Return an empty list.
- **Construction**: If the pre-validation passes, a solution can be constructed in a single pass.
  - Adjust `upper` and `lower` by subtracting `twos`: `upper -= twos`, `lower -= twos`. These are the remaining `1`s that need to be placed in columns where `colsum[i] == 1`.
  - Initialize an empty `2 x n` matrix `result`.
  - Iterate through `colsum` from `i = 0` to `n-1`:
    - If `colsum[i] == 2`: Place `1`s in both rows: `result[0][i] = 1`, `result[1][i] = 1`.
    - If `colsum[i] == 0`: Place `0`s in both rows: `result[0][i] = 0`, `result[1][i] = 0`.
    - If `colsum[i] == 1`: Greedily place a `1`.
      - If `upper > 0`, place the `1` in the top row: `result[0][i] = 1`, `result[1][i] = 0`. Decrement `upper`.
      - Else, place the `1` in the bottom row: `result[0][i] = 0`, `result[1][i] = 1`. Decrement `lower`.
- **Return Result**: Since the pre-validation checks ensure that we have exactly enough `1`s for the `colsum[i] == 1` columns, no further validation is needed. Return the constructed matrix.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
    int n = colsum.length;
    List<Integer> first = new ArrayList<>();
    List<Integer> second = new ArrayList<>();
    for (int j = 0; j < n; ++j) {
      int a = 0, b = 0;
      if (colsum[j] == 2) {
        a = b = 1;
        upper--;
        lower--;
      } else if (colsum[j] == 1) {
        if (upper > lower) {
          upper--;
          a = 1;
        } else {
          lower--;
          b = 1;
        }
      }
      if (upper < 0 || lower < 0) {
        break;
      }
      first.add(a);
      second.add(b);
    }
    return upper == 0 && lower == 0 ? List.of(first, second) : List.of();
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> reconstructMatrix(int upper, int lower,
                                        vector<int> &colsum) {
    int n = colsum.size();
    vector<vector<int>> ans(2, vector<int>(n));
    for (int j = 0; j < n; ++j) {
      if (colsum[j] == 2) {
        ans[0][j] = ans[1][j] = 1;
        upper--;
        lower--;
      }
      if (colsum[j] == 1) {
        if (upper > lower) {
          upper--;
          ans[0][j] = 1;
        } else {
          lower--;
          ans[1][j] = 1;
        }
      }
      if (upper < 0 || lower < 0) {
        break;
      }
    }
    return upper || lower ? vector<vector<int>>() : ans;
  }
};

```

### Python

```python
class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]: n = len(colsum) ans = [[0] * n for _ in range(2)] for j, v in enumerate(colsum): if v == 2: ans[0][j] = ans[1][j] = 1 upper, lower = upper - 1, lower - 1 if v == 1: if upper > lower: upper -= 1 ans[0][j] = 1 else: lower -= 1 ans[1][j] = 1 if upper < 0 or lower < 0: return [] return ans if lower == upper == 0 else []

```