Skip to main content
Talentd

Build a Matrix With Conditions - Solution & Explanation

HardArrayGraphTopological SortMatrix11 min readAsked at: Google
Practice this problem

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

Approach Overview

Problem Overview: You must place numbers from 1..k in a k x k matrix. Some constraints require one number to appear above another (row conditions) or to the left of another (column conditions). The challenge is arranging each number exactly once so both sets of ordering constraints are satisfied.

Approach 1: Graph Representation and Topological Sort (O(k + R + C) time, O(k + R + C) space)

Model both constraint lists as directed graphs. One graph represents row precedence (a must appear above b), and another represents column precedence (a must appear left of b). Run a topological sort on each graph to compute a valid ordering of numbers for rows and columns. If either graph contains a cycle, no valid matrix exists.

After obtaining the two topological orders, map each number to its row index and column index. Create an empty k x k matrix and place number x at position (rowIndex[x], colIndex[x]). This works because the row ordering guarantees vertical constraints while the column ordering guarantees horizontal constraints. The algorithm processes each node and edge once, giving linear complexity relative to the number of constraints.

This approach relies heavily on graph modeling and topological sort. The matrix construction step is straightforward once both orderings are known.

Approach 2: Backtracking with Constraint Propagation (Exponential time, O(k^2) space)

Another way is to treat the matrix as a constraint satisfaction problem. Try placing numbers into cells while verifying that partial placements do not violate row or column precedence rules. When placing a value, propagate constraints by checking if the required relative positions are still possible. If a conflict appears, backtrack and try a different placement.

This method explores permutations of placements and prunes invalid states early using constraint checks. While workable for very small k, the search space grows rapidly and quickly becomes impractical. It mainly helps build intuition about how ordering constraints restrict placements in a matrix.

Recommended for interviews: The graph + topological sort approach is the expected solution. It converts ordering constraints into two independent DAG problems and solves them in linear time. Showing the brute-force backtracking idea demonstrates understanding of constraint satisfaction, but the optimal solution proves you recognize when a dependency problem should be solved with DAG ordering.

Approach 1: Graph Representation and Topological Sort

This approach involves representing row and column conditions as directed graphs. You perform a topological sort on these graphs to determine valid row and column positions for each number from 1 to k. If cycle detection reveals any contradictions, it indicates that it's impossible to build the matrix.

This code uses an adjacency list to represent dependencies between numbers. The algorithm then performs topological sorting using a queue and processes elements based on their dependencies.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The algorithm has a time complexity of O(k + n + m), where k is the size of the matrix, n is the number of row conditions, and m is the number of column conditions. The space complexity is O(k + n + m) for storing the conditions and dependencies.

Try this approach in the editor →

Approach 2: Backtracking with Constraints Propagation

This approach considers using backtracking to build the matrix. For each valid permutation of numbers, it ensures constraints are satisfied and adjusts dynamically by propagating constraints to subsequent steps.

The code uses recursion combined with backtracking to explore all permutations and uses constraint-checking to prune invalid paths efficiently.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(k!). Space complexity: O(k^2) due to matrix storage and recursive call stack.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Graph Representation and Topological Sort

The algorithm has a time complexity of O(k + n + m), where k is the size of the matrix, n is the number of row conditions, and m is the number of column conditions. The space complexity is O(k + n + m) for storing the conditions and dependencies.

Backtracking with Constraints Propagation

Time complexity: O(k!). Space complexity: O(k^2) due to matrix storage and recursive call stack.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Representation + Topological SortO(k + R + C)O(k + R + C)General and optimal solution when ordering constraints form DAG relationships
Backtracking with Constraint PropagationExponentialO(k^2)Useful for conceptual understanding or very small k where brute-force search is feasible

Video Solution

Build a Matrix With Conditions - Leetcode 2392 - Python • NeetCodeIO • 12,540 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Build a Matrix With Conditions easy or hard?
The problem is labeled Hard because it requires recognizing that two independent topological sorts can determine matrix coordinates. Candidates must correctly detect cycles, maintain ordering constraints, and combine the results into a valid matrix layout.
Build a Matrix With Conditions Python/Java solution
Most implementations build adjacency lists for row and column constraints, compute topological order using BFS (Kahn's algorithm), and then construct the matrix using index mappings. The same logic works in Python, Java, C++, C#, or JavaScript with minor syntax differences.
How to solve Build a Matrix With Conditions in O(n)?
Treat row and column constraints as two separate DAG ordering problems. Run topological sort on the row graph and the column graph to produce two valid sequences of numbers. Map each value to its row and column index and place it directly in a k×k matrix. Since each edge and node is processed once, the algorithm runs in linear time relative to the number of constraints.
What is the best approach for Build a Matrix With Conditions?
The optimal approach models row and column constraints as two directed graphs and performs topological sort on each. The row ordering determines vertical positions and the column ordering determines horizontal positions. If either graph contains a cycle, the constraints are impossible. This solution runs in O(k + R + C) time where R and C are the number of row and column conditions.
Is Build a Matrix With Conditions asked at Google/Amazon/Meta?
Problems involving topological ordering of constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often involve scheduling tasks, resolving dependencies, or validating precedence rules in graphs.
What data structure is used in Build a Matrix With Conditions?
The core data structures are adjacency lists for representing directed graphs and a queue for Kahn's topological sort algorithm. Additional arrays store in-degrees and map each value to its computed row and column index before filling the matrix.
What is the time complexity of Build a Matrix With Conditions?
Using the graph and topological sort approach, the complexity is O(k + R + C). Each node from 1..k is processed once and every constraint edge is visited during BFS or DFS topological sorting. Building the final matrix takes O(k^2) initialization but only O(k) placements.

Ready to solve this problem?

Practice Build a Matrix With Conditions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Course Schedule

Next

Course Schedule II