How hard is LeetCode 2392. Build a Matrix With Conditions?

LeetCode 2392. Build a Matrix With Conditions is rated Hard on LeetCode.

What is the time complexity of LeetCode 2392. Build a Matrix With Conditions?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 2392. Build a Matrix With Conditions?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 2392. Build a Matrix With Conditions cover?

LeetCode 2392. Build a Matrix With Conditions is tagged Graph, Topological Sort, Array and Matrix on LeetCode.

Build a Matrix With Conditions — LeetCode 2392 Python Solution

HardGraphTopological SortArrayMatrix

Problem: #2392
Pattern: Topological Sort
Reading time: 6 min
Source: leetcode.com

The 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].

Example

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.

Python solution

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

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 2392. Build a Matrix With Conditions is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2392. Build a Matrix With Conditions?: LeetCode 2392. Build a Matrix With Conditions is rated Hard on LeetCode.
What is the time complexity of LeetCode 2392. Build a Matrix With Conditions?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 2392. Build a Matrix With Conditions?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 2392. Build a Matrix With Conditions cover?: LeetCode 2392. Build a Matrix With Conditions is tagged Graph, Topological Sort, Array and Matrix on LeetCode.