2392. Build a Matrix With Conditions - Explanation

Description

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.

Example 1:

Input: k = 3, rowConditions = [[2,1],[1,3]], colConditions = [[3,1],[2,3]]

Output: [[2,0,0],[0,0,1],[0,3,0]]

Example 2:

Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]

Output: []

Constraints:

2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 10,000
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]

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Topological Sort (DFS)

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def dfs(src, adj, visit, path, order):
            if src in path:
                return False
            if src in visit:
                return True
            visit.add(src)
            path.add(src)
            for nei in adj[src]:
                if not dfs(nei, adj, visit, path, order):
                    return False
            path.remove(src)
            order.append(src)
            return True

        def topo_sort(edges):
            adj = defaultdict(list)
            for src, dst in edges:
                adj[src].append(dst)

            visit, path = set(), set()
            order = []
            for src in range(1, k + 1):
                if src not in visit:
                    if not dfs(src, adj, visit, path, order):
                        return []
            return order[::-1]

        row_order = topo_sort(rowConditions)
        if not row_order: return []

        col_order = topo_sort(colConditions)
        if not col_order: return []

        val_to_row = {num: i for i, num in enumerate(row_order)}
        val_to_col = {num: i for i, num in enumerate(col_order)}
        res = [[0] * k for _ in range(k)]
        for num in range(1, k + 1):
            r, c = val_to_row[num], val_to_col[num]
            res[r][c] = num

        return res

Time & Space Complexity

Time complexity: $O(k ^ 2 + n + m)$
Space complexity:
- $O(k + n + m)$ extra space.
- $O(k ^ 2)$ space for the output matrix.

Where $n$ is the size of the array $rowConditions$ , $m$ is the size of the array $colConditions$ , and $k$ is the size of the output matrix.

2. Topological Sort (Kahn's Algorithm)

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo_sort(edges):
            indegree = [0] * (k + 1)
            adj = [[] for _ in range(k + 1)]
            for u, v in edges:
                adj[u].append(v)
                indegree[v] += 1

            order = []
            q = deque()
            for i in range(1, k + 1):
                if not indegree[i]:
                    q.append(i)

            while q:
                node = q.popleft()
                order.append(node)
                for nei in adj[node]:
                    indegree[nei] -= 1
                    if not indegree[nei]:
                        q.append(nei)

            return order

        row_order = topo_sort(rowConditions)
        if len(row_order) != k: return []

        col_order = topo_sort(colConditions)
        if len(col_order) != k: return []

        res = [[0] * k for _ in range(k)]
        colIndex = [0] * (k + 1)
        for i in range(k):
            colIndex[col_order[i]] = i

        for i in range(k):
            res[i][colIndex[row_order[i]]] = row_order[i]
        return res

Time & Space Complexity

Time complexity: $O(k ^ 2 + n + m)$
Space complexity:
- $O(k + n + m)$ extra space.
- $O(k ^ 2)$ space for the output matrix.

Where $n$ is the size of the array $rowConditions$ , $m$ is the size of the array $colConditions$ , and $k$ is the size of the output matrix.