Scale Engineer

Build a Matrix With Conditions

Hard
#2177Time: O(k^2 + n + m) - Building the graph for row conditions takes O(n) and for column conditions takes O(m). The topological sort for rows takes O(k^2 + n) due to the O(k) scan inside a loop that runs `k` times. Similarly, it's O(k^2 + m) for columns. Constructing the final matrix takes O(k^2). The total complexity is dominated by the sorting and matrix construction.Space: O(k^2 + n + m) - We need O(k + n) space for the row condition graph and O(k + m) for the column condition graph. The maps for row and column positions take O(k) space. The final matrix requires O(k^2) space.
Algorithms
Topological Sort
Data structures
ArrayMatrixGraph

Prompt

You are given a positive integer k. You are also given:

  • a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and
  • a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].

The two arrays contain integers from 1 to k.

You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0.

The matrix should also satisfy the following conditions:

  • The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.
  • The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

 

Example 1:

Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
Output: [[3,0,0],[0,0,1],[0,2,0]]
Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.
The row conditions are the following:
- Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.
- Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.
The column conditions are the following:
- Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.
- Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.
Note that there may be multiple correct answers.

Example 2:

Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
Output: []
Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.
No matrix can satisfy all the conditions, so we return the empty matrix.

 

Constraints:

  • 2 <= k <= 400
  • 1 <= rowConditions.length, colConditions.length <= 104
  • rowConditions[i].length == colConditions[i].length == 2
  • 1 <= abovei, belowi, lefti, righti <= k
  • abovei != belowi
  • lefti != righti

Approaches

2 approaches with complexity analysis and trade-offs.

This approach correctly identifies that the problem can be split into two independent topological sort problems: one for determining the row ordering of numbers and another for the column ordering. It implements topological sort by repeatedly scanning all numbers to find a node with an in-degree of zero. While conceptually straightforward, this method of finding the next node in the topological order is less efficient than standard queue-based or DFS-based algorithms.

Algorithm

  • Define a helper function topologicalSort(k, conditions):
    • Build a graph using an adjacency list and an in-degree array for numbers 1 to k based on the given conditions.
    • Initialize an empty list order to store the sorted result.
    • Loop k times to find one number for the order in each iteration.
    • Inside the loop, iterate from 1 to k to find a number node that has an in-degree of 0 and has not been placed in the order list yet.
    • If no such node is found, it means there's a cycle in the dependencies. Return an empty list to indicate failure.
    • Add the found node to the order list. To mark it as 'processed', set its in-degree to a special value like -1.
    • For each neighbor of the node, decrement its in-degree.
    • After the main loop, if successful, return the order list.
  • In the main buildMatrix function:
    • Call topologicalSort for rowConditions to get rowOrder.
    • Call topologicalSort for colConditions to get colOrder.
    • If either rowOrder or colOrder is empty, it's impossible to build the matrix, so return an empty matrix.
    • Create two hashmaps, rowMap and colMap, to store the row and column index for each number from 1 to k.
    • Populate these maps using rowOrder and colOrder.
    • Create a k x k matrix initialized with zeros.
    • For each number i from 1 to k, place it in the matrix at matrix[rowMap.get(i)][colMap.get(i)].
    • Return the constructed matrix.

Walkthrough

The problem requires satisfying two separate sets of constraints: relative row positions and relative column positions. This suggests we can solve for the row and column placements independently. Each set of conditions, like [above, below] or [left, right], can be modeled as a directed edge in a graph where the numbers 1 to k are vertices. An edge u -> v means u must come before v in the ordering. Finding a valid sequence that respects these constraints is a classic topological sorting problem.

This approach implements a basic version of topological sort. For each of the k positions in the final ordering, it iterates through all k numbers to find one that can be placed next (i.e., one with an in-degree of 0). Once a valid number is found, it's added to the order, and the in-degrees of its dependent numbers are updated. This process is repeated for both row and column conditions. If a topological sort is possible for both, the two resulting orders are used to determine the exact (row, col) coordinates for each number in the final k x k matrix. If either sort fails (due to a cycle in conditions), no solution exists.

class Solution {    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {        List<Integer> rowOrder = topologicalSort(k, rowConditions);        List<Integer> colOrder = topologicalSort(k, colConditions);         if (rowOrder.isEmpty() || colOrder.isEmpty()) {            return new int[0][0];        }         Map<Integer, Integer> rowMap = new HashMap<>();        for (int i = 0; i < k; i++) {            rowMap.put(rowOrder.get(i), i);        }         Map<Integer, Integer> colMap = new HashMap<>();        for (int i = 0; i < k; i++) {            colMap.put(colOrder.get(i), i);        }         int[][] matrix = new int[k][k];        for (int i = 1; i <= k; i++) {            matrix[rowMap.get(i)][colMap.get(i)] = i;        }         return matrix;    }     private List<Integer> topologicalSort(int k, int[][] conditions) {        List<Integer>[] adj = new ArrayList[k + 1];        int[] inDegree = new int[k + 1];        for (int i = 1; i <= k; i++) {            adj[i] = new ArrayList<>();        }         for (int[] condition : conditions) {            adj[condition[0]].add(condition[1]);            inDegree[condition[1]]++;        }         List<Integer> order = new ArrayList<>();        for (int i = 0; i < k; i++) {            int nodeToProcess = -1;            for (int j = 1; j <= k; j++) {                if (inDegree[j] == 0) {                    nodeToProcess = j;                    break;                }            }             if (nodeToProcess == -1) {                return new ArrayList<>(); // Cycle detected            }             order.add(nodeToProcess);            inDegree[nodeToProcess] = -1; // Mark as processed             for (int neighbor : adj[nodeToProcess]) {                inDegree[neighbor]--;            }        }         return order;    }}

Complexity

Time

O(k^2 + n + m) - Building the graph for row conditions takes O(n) and for column conditions takes O(m). The topological sort for rows takes O(k^2 + n) due to the O(k) scan inside a loop that runs `k` times. Similarly, it's O(k^2 + m) for columns. Constructing the final matrix takes O(k^2). The total complexity is dominated by the sorting and matrix construction.

Space

O(k^2 + n + m) - We need O(k + n) space for the row condition graph and O(k + m) for the column condition graph. The maps for row and column positions take O(k) space. The final matrix requires O(k^2) space.

Trade-offs

Pros

  • The logic is relatively easy to follow: find a valid item, place it, update dependencies, and repeat.

  • It correctly separates the problem into two manageable subproblems.

Cons

  • The topological sort implementation is inefficient. The nested loop structure for finding a zero in-degree node results in a time complexity of O(k^2) for the sorting part, which is slower than the standard O(k + E) algorithms.

  • For large k, this performance difference can be significant.

Solutions

class Solution {private  int k;public  int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {    this.k = k;    List<Integer> row = f(rowConditions);    List<Integer> col = f(colConditions);    if (row == null || col == null) {      return new int[0][0];    }    int[][] ans = new int[k][k];    int[] m = new int[k + 1];    for (int i = 0; i < k; ++i) {      m[col.get(i)] = i;    }    for (int i = 0; i < k; ++i) {      ans[i][m[row.get(i)]] = row.get(i);    }    return ans;  }private  List<Integer> f(int[][] cond) {    List<Integer>[] g = new List[k + 1];    Arrays.setAll(g, key->new ArrayList<>());    int[] indeg = new int[k + 1];    for (var e : cond) {      int a = e[0], b = e[1];      g[a].add(b);      ++indeg[b];    }    Deque<Integer> q = new ArrayDeque<>();    for (int i = 1; i < indeg.length; ++i) {      if (indeg[i] == 0) {        q.offer(i);      }    }    List<Integer> res = new ArrayList<>();    while (!q.isEmpty()) {      for (int n = q.size(); n > 0; --n) {        int i = q.pollFirst();        res.add(i);        for (int j : g[i]) {          if (--indeg[j] == 0) {            q.offer(j);          }        }      }    }    return res.size() == k ? res : null;  }}

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