# Build a Matrix With Conditions
**Difficulty:** HARD
[External](https://leetcode.com/problems/build-a-matrix-with-conditions)
Canonical: https://scaleengineer.com/dsa/problems/build-a-matrix-with-conditions
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Matrix, Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/build-a-matrix-with-conditions/image0.png) 

**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
## Topological Sort by Repeatedly Finding Zero In-degree Nodes
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Optimal Approach using Kahn's Algorithm (BFS-based Topological Sort)
This approach is the standard and most efficient way to solve the problem. It also separates the row and column constraints into two independent topological sort subproblems. However, it uses Kahn's algorithm, a more efficient BFS-based method for topological sorting. By using a queue to maintain a set of nodes with zero in-degree, it avoids the costly repeated scanning of all nodes, leading to a faster sorting process.
**Time:** O(k^2 + n + m) - Building the graphs takes O(n) and O(m). The topological sort using Kahn's algorithm is O(k + n) for rows and O(k + m) for columns. Matrix construction is O(k^2). The overall complexity is determined by the largest term, which is often O(k^2) given the constraints. · **Space:** O(k^2 + n + m) - The space complexity is identical to the previous approach. O(k + n) and O(k + m) for the two graphs, O(k) for the queue and maps, and O(k^2) for the output matrix.
**Pros:** Highly efficient, using an optimal algorithm for topological sorting (O(V+E)).; It is a robust and standard pattern for solving problems involving ordering with dependencies.; Cleanly separates concerns, making the code modular and easy to understand.
**Cons:** Requires familiarity with Kahn's algorithm and queue-based processing, which might be slightly more complex to implement from scratch compared to the repeated search method.
### Explanation
This optimal solution refines the previous approach by using a more efficient algorithm for the topological sorting subproblem. The overall strategy of 'divide and conquer'—solving for row and column orderings separately—is retained. The key improvement is the implementation of the `topologicalSort` function using Kahn's algorithm.

Kahn's algorithm works as follows:
1.  Compute the in-degrees of all nodes (numbers 1 to `k`).
2.  Initialize a queue with all nodes that have an in-degree of 0. These are the numbers that can appear first in the ordering as they have no prerequisites.
3.  Process the nodes in the queue. When a node is processed, it's added to our topological order. Then, we consider it 'removed' from the graph. This means we decrement the in-degree of all its neighbors. 
4.  If decrementing a neighbor's in-degree makes it 0, that neighbor now has no remaining prerequisites, so it's added to the queue.
5.  This process continues until the queue is empty. If the final topological order contains all `k` nodes, a valid ordering was found. If not, the graph must contain a cycle, indicating contradictory conditions.

This BFS-style processing is highly efficient, visiting each node and edge once. After obtaining the row and column orderings, the matrix is constructed as before.

```java
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.size() < k || colOrder.size() < k) {
            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]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);

            for (int v : adj[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return order;
    }
}
```
### Algorithm
- Define a helper function `topologicalSort(k, conditions)` using Kahn's algorithm:
  - Build a graph (adjacency list) and an in-degree array from the `conditions`.
  - Initialize a queue and add all nodes with an in-degree of 0.
  - Initialize an empty list `order` to store the result.
  - While the queue is not empty:
    - Dequeue a node `u` and add it to the `order` list.
    - For each neighbor `v` of `u`, decrement its in-degree. If `v`'s in-degree becomes 0, enqueue `v`.
  - After the loop, if `order.size()` is less than `k`, a cycle was detected. Return an empty list.
  - Otherwise, return the `order` list.
- The main `buildMatrix` function logic remains the same:
  - Get `rowOrder` and `colOrder` by calling the efficient `topologicalSort` function.
  - If either ordering is incomplete, return an empty matrix.
  - Use the orderings to create position maps.
  - Construct and return the final matrix.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int k;
  vector<vector<int>> buildMatrix(int k, vector<vector<int>> &rowConditions,
                                  vector<vector<int>> &colConditions) {
    this->k = k;
    auto row = f(rowConditions);
    auto col = f(colConditions);
    if (row.empty() || col.empty())
      return {};
    vector<vector<int>> ans(k, vector<int>(k));
    vector<int> m(k + 1);
    for (int i = 0; i < k; ++i) {
      m[col[i]] = i;
    }
    for (int i = 0; i < k; ++i) {
      ans[i][m[row[i]]] = row[i];
    }
    return ans;
  }
  vector<int> f(vector<vector<int>> &cond) {
    vector<vector<int>> g(k + 1);
    vector<int> indeg(k + 1);
    for (auto &e : cond) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      ++indeg[b];
    }
    queue<int> q;
    for (int i = 1; i < k + 1; ++i) {
      if (!indeg[i]) {
        q.push(i);
      }
    }
    vector<int> res;
    while (!q.empty()) {
      for (int n = q.size(); n; --n) {
        int i = q.front();
        res.push_back(i);
        q.pop();
        for (int j : g[i]) {
          if (--indeg[j] == 0) {
            q.push(j);
          }
        }
      }
    }
    return res.size() == k ? res : vector<int>();
  }
};

```

### Python

```python
class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]: def f(cond): g = defaultdict(list) indeg = [0] * (k + 1) for a, b in cond: g[a]. append(b) indeg[b] += 1 q = deque([i for i, v in enumerate(indeg[1:], 1) if v == 0]) res = [] while q: for _ in range(len(q)): i = q . popleft() res . append(i) for j in g[i]: indeg[j] -= 1 if indeg[j] == 0: q . append(j) return None if len(res) != k else res row = f(rowConditions) col = f(colConditions) if row is None or col is None: return [] ans = [[0] * k for _ in range(k)] m = [0] * (k + 1) for i, v in enumerate(col): m[v] = i for i, v in enumerate(row): ans[i][m[v]] = v return ans

```