Build a Matrix With Conditions

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.