Build a Matrix With Conditions

Build a Matrix With Conditions is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.

Problem statement

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

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 abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.

- The number lefti should appear in a column that is strictly left of the column at which the number righti 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 = [[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.

Example 2:

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 <= 104

- rowConditions[i].length == colConditions[i].length == 2

- 1 <= abovei, belowi, lefti, righti <= k

- abovei != belowi

- lefti != righti

Topics and companies

Topics: Array, Graph, Topological Sort, Matrix.

How to practise Build a Matrix With Conditions on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(k + n + m), where n = rowConditions.size(), m = colConditions.size(). Each topological sort is O(k + E), and E is at most n or m. The rest is O(k^2) for matrix construction. time and O(k^2) for the result matrix and adjacency matrix (for duplicate edge check), plus O(k) for in-degree and order arrays. space.

Open Build a Matrix With Conditions in the code editor, or read the Build a Matrix With Conditions editorial for a worked solution with its approach and complexity analysis.

Where Build a Matrix With Conditions sits in the DSA pattern sheet

Problems related to Build a Matrix With Conditions

Other problems that use the same Graph BFS - Topological Sort (Kahn's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.