Scale Engineer

Reconstruct a 2-Row Binary Matrix

Med
#1169Time: 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.2 companies
Patterns
Greedy
Data structures
ArrayMatrix
Companies
American ExpressGrab

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The brute-force method systematically tries every combination for placing 1s. 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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem