> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Build a Matrix With Conditions Python Solution

> Tested Python solution for LeetCode 2392 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 2392, Hard. Topics: Array, Graph Theory, Topological Sort, Matrix. [View on LeetCode](https://leetcode.com/problems/build-a-matrix-with-conditions/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2392   # by problem number
lcpy gen -s build_a_matrix_with_conditions   # by problem name
```

## Problem

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

* a 2D integer array `rowConditions` of size `n` where `rowConditions[i] = [above_i, below_i]`, and
* a 2D integer array `colConditions` of size `m` where `colConditions[i] = [left_i, right_i]`.

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 `above_i` should appear in a **row** that is strictly **above** the row at which the number `below_i` appears for all `i` from `0` to `n - 1`.
* The number `left_i` should appear in a **column** that is strictly **left** of the column at which the number `right_i` appears for all `i` from `0` to `m - 1`.

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

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/07/06/gridosdrawio.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.
```

```
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 \<= 10^4
* rowConditions\[i].length == colConditions\[i].length == 2
* 1 \<= above\_i, below\_i, left\_i, right\_i \<= k
* above\_i != below\_i
* left\_i != right\_i

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/build_a_matrix_with_conditions/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/build_a_matrix_with_conditions/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import defaultdict, deque


class Solution:
    # Time: O(k + n + m)
    # Space: O(k + n + m)
    def build_matrix(
        self, k: int, row_conditions: list[list[int]], col_conditions: list[list[int]]
    ) -> list[list[int]]:
        def topological_order(conditions: list[list[int]]) -> list[int]:
            graph: dict[int, list[int]] = defaultdict(list)
            indegree = [0] * (k + 1)
            for above, below in conditions:
                graph[above].append(below)
                indegree[below] += 1

            queue = deque(node for node in range(1, k + 1) if indegree[node] == 0)
            order: list[int] = []

            while queue:
                node = queue.popleft()
                order.append(node)
                for neighbor in graph[node]:
                    indegree[neighbor] -= 1
                    if indegree[neighbor] == 0:
                        queue.append(neighbor)

            return order if len(order) == k else []

        row_order = topological_order(row_conditions)
        if not row_order:
            return []

        col_order = topological_order(col_conditions)
        if not col_order:
            return []

        column_index = {number: idx for idx, number in enumerate(col_order)}
        matrix = [[0] * k for _ in range(k)]
        for row, number in enumerate(row_order):
            matrix[row][column_index[number]] = number

        return matrix
```

## Complexity

| Time         | Space        |
| ------------ | ------------ |
| O(k + n + m) | O(k + n + m) |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).