#2392

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Build a Matrix With Conditions

Solve the matrix-building problem by using graph indegree and topological sorting to satisfy given row and column constraints.

array graph topological sort matrix

Problem Statement

You are given a positive integer k, along with two arrays representing row and column constraints. The goal is to construct a k x k matrix where each number from 1 to k appears exactly once, and the remaining positions are filled with zeros. The row and column conditions specify the relative positioning of certain numbers within the matrix.

Each condition in the row and column arrays relates to the positions of two numbers. For example, a condition [a, b] in the row array means that number a must appear in a row above number b, while a condition [a, b] in the column array means that number a must appear in a column to the left of number b. You need to determine if it's possible to build such a matrix. If not, return an empty matrix.

Examples

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

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: []

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

Solution Approach

Graph Representation

Represent the problem as a directed graph where each number from 1 to k is a node. Create directed edges based on the row and column conditions. Each condition establishes a dependency, which helps determine the relative order of the numbers.

Topological Sorting

Perform a topological sort on the graph. This step ensures that the order of numbers respects the constraints of both the rows and columns. If a cycle is detected, it's impossible to construct the matrix, and an empty matrix should be returned.

Matrix Construction

Once a valid topological order is found, construct the matrix by placing each number at the appropriate row and column. For each number in the topologically sorted order, place it in the matrix according to the remaining positions while respecting the constraints.

Complexity Analysis

Metric	Value
Time	O(max(k\cdot k,n))
Space	O(max(k\cdot k,n))

The time complexity is O(max(k * k, n)), where k is the matrix size and n is the total number of constraints. The space complexity is O(max(k * k, n)) due to the storage required for the matrix and graph representation.

What Interviewers Usually Probe

Candidate efficiently applies topological sorting for graph problems.
Candidate detects and handles cyclic dependencies in the graph.
Candidate constructs a matrix efficiently by leveraging graph-based ordering.

Common Pitfalls or Variants

Common pitfalls

Overlooking cyclic dependencies that make the matrix construction impossible.
Incorrectly implementing the topological sorting algorithm.
Misplacing numbers in the matrix after finding a valid topological order.

Follow-up variants

Implementing an algorithm for larger values of k (up to 400).
Handling a larger set of row and column constraints efficiently.
Modifying the problem to support partial matrix construction without fully satisfying constraints.

FAQ

How can topological sorting help in solving the "Build a Matrix With Conditions" problem?

Topological sorting helps by providing a valid order of numbers that satisfies both row and column conditions, ensuring that numbers are placed in the matrix without violating any constraints.

What happens if there is a cycle in the graph for this problem?

If there is a cycle in the graph, it indicates that the conditions are contradictory, and thus no valid matrix can be constructed. In this case, the output should be an empty matrix.

What is the time complexity of solving "Build a Matrix With Conditions"?

The time complexity is O(max(k * k, n)), where k is the matrix size and n is the number of row and column conditions.

How do I handle large values of `k` efficiently in this problem?

For large values of k, optimize the graph construction and topological sorting to avoid unnecessary complexity. Utilize adjacency lists and in-degree tracking to efficiently detect cycles and process nodes.

Can this problem be solved using a different approach besides topological sorting?

Topological sorting is the most direct approach due to the nature of the problem, but other graph algorithms, like depth-first search (DFS), could be used to detect cycles and generate a valid order.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

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

Continue Practicing

#2328 number of increasing paths in a grid #1728 cat and mouse ii #1632 rank transform of a matrix