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

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.

Examples

Example 1: $$ \begin{bmatrix} 3 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 2 & 0 \end{bmatrix} $$

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.

Solution

Method 1 - Topological Sort using Kahn’s Algorithm

Here’s a step-by-step approach to solve this problem:

  1. Topologically Sort Rows: Use the rowConditions to find a valid order for the rows.
  2. Topologically Sort Columns: Use the colConditions to find a valid order for the columns.
  3. Build the Matrix: Use the sorted orders to place the numbers in the ( k \times k ) matrix.

Code

Java
public class Solution {

	public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
		List<Integer> rowOrder = topologicalSort(k, rowConditions);
		List<Integer> colOrder = topologicalSort(k, colConditions);

		// If either sorting fails (returns null), returns an empty matrix
		if (rowOrder == null || colOrder == null) {
			return new int[0][0];
		}

		// Convert row and column orders into positions
		Map<Integer, Integer> rowPosition = new HashMap<>();
		Map<Integer, Integer> colPosition = new HashMap<>();

		for (int i = 0; i < k; i++) {
			rowPosition.put(rowOrder.get(i), i);
			colPosition.put(colOrder.get(i), i);
		}

		// Construct the matrix
		int[][] matrix = new int[k][k];

		for (int num = 1; num <= k; num++) {
			int row = rowPosition.get(num);
			int col = colPosition.get(num);
			matrix[row][col] = num;
		}

		return matrix;
	}

	private List<Integer> topologicalSort(int k, int[][] conditions) {
		// Create graph and indegree arrays
		List<Integer> [] graph = new List[k + 1];
		int[] indegree = new int[k + 1];

		for (int i = 0; i <= k; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int[] condition: conditions) {
			int u = condition[0];
			int v = condition[1];
			graph[u].add(v);
			indegree[v]++;
		}

		// Kahn's algorithm for topological sorting
		Queue<Integer> queue = new LinkedList<>();
		List<Integer> sortedOrder = new ArrayList<>();

		for (int i = 1; i <= k; i++) {
			if (indegree[i] == 0) {
				queue.offer(i);
			}
		}

		while (!queue.isEmpty()) {
			int node = queue.poll();
			sortedOrder.add(node);

			for (int neighbor: graph[node]) {
				indegree[neighbor]--;

				if (indegree[neighbor] == 0) {
					queue.offer(neighbor);
				}
			}
		}

		// If sortedOrder doesn't contain k elements, return null (cycle detected)
		return sortedOrder.size() == k ? sortedOrder : null;
	}
}
Python
def build_matrix(k, rowConditions, colConditions):
    row_order = topological_sort(k, rowConditions)
    col_order = topological_sort(k, colConditions)

    if not row_order or not col_order:
        return []

    row_position = {num: i for i, num in enumerate(row_order)}
    col_position = {num: i for i, num in enumerate(col_order)}

    matrix = [[0] * k for _ in range(k)]
    for num in range(1, k + 1):
        matrix[row_position[num]][col_position[num]] = num

    return matrix


def topological_sort(k, conditions):
    graph = defaultdict(list)
    indegree = [0] * (k + 1)

    for u, v in conditions:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, k + 1) if indegree[i] == 0])
    sorted_order = []

    while queue:
        node = queue.popleft()
        sorted_order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(sorted_order) != k:
        return []
    return sorted_order

Complexity

  • ⏰ Time complexity: O(k), where k is 1 dimension of the matrix.
    • Graph construction - Constructing the adjacency list and indegree array takes O(E) times, where E is number of edges in graph, and in this problem E is proportional to k, may be around k at a time
    • Topological Sort using Kahn’s algorithm - Initializing the queue with nodes having indegree 0 takes O(V) time, where V is number of nodes. V = k in the problem. Processing each node using BFS takes O(V+E), and V and E are proportional to k, hence O(k)
  • 🧺 Space complexity: O(k)
    • Graph storage - requires O(V+E), which is O(k)
    • Queue for BFS requires O(V) ⇨ O(k)
    • Toposort for rows and columns required O(2V) ⇨ O(k)
    • Two HashMaps for row and column positions: O(V) ⇨ O(k)
    • Matching matrix takes O(k) times

Dry Run

Topological Sort for Rows

For rowConditions = [ [1, 2], [3, 2] ]:

Add edge 1 -> 2:

graph TD;
1 ---> 2
  
graph: {1 -> [2]} indegree: [0, 0, 1, 0]

Add edge 3 -> 2:

graph: {1 -> [2], 3 -> [2]} indegree: [0, 0, 2, 0]

graph TD;
1 ---> 2
3 ---> 2

Now, we apply Kahn’s Algorithm to find topological order. We can either get 1 -> 3 -> 2 or 3 -> 1 -> 2. We will use indegrees above:

  • Initialize queue with nodes having indegree 0: [1, 3]
  • Process node 1:
    • sortedOrder: [1]
    • for neighbor 2 -> indegree[2] = 2 - 1 = 1
    • Queue contains [3]
  • Process node 3:
    • sortedOrder: [1, 3]
    • for neighbor 2 -> indegree[2] = 1 - 1 = 0 ⇨ enqueue 2
    • Queue contains [2]
  • Process node 2:
    • sortedOrder: [1, 3, 2]
    • No neighbour remaining
    • Queue is empty []

Hence sortedOrder is [1, 3, 2].

Topological Sort for Columns

For colConditions = [ [2, 1], [3, 2] ]:

Add edge 2 -> 1:

graph LR;
2 ---> 1
  
graph: {1 -> [2]} indegree: [0, 1, 0, 0]

Add edge 3 -> 2:

graph: {1 -> [2], 3 -> [2]} indegree: [0, 1, 1, 0]

graph LR;
2 ---> 1
3 ---> 2

Now, we apply Kahn’s Algorithm to find topological order. We can either get 3 -> 2 -> 1. We will use in-degrees above:

  • Initialize queue with nodes having indegree 0: [3]
  • Process node 3:
    • sortedOrder: [3]
    • for neighbor 2 -> indegree[2] = 1 - 1 = 0 ⇨ enqueue 2
    • Queue contains [2]
  • Process node 2:
    • sortedOrder: [3, 2]
    • for neighbor 1 -> indegree[1] = 1 - 1 = 0 ⇨ enqueue 1
    • Queue contains [1]
  • Process node 1:
    • sortedOrder: [3, 2, 1]
    • No neighbour remaining
    • Queue is empty []

Hence sortedOrder is [3, 2, 1].

Construct the Matrix

We can map row and columns to positions:

rowPosition: {1: 0, 3: 1, 2: 2}
colPosition: {3: 0, 2: 1, 1: 2}

Lets place the numbers from 1 to 3.

For 1, place 1 at matrix[rowPosition[1]][colPosition[1]], rowPosition is 0, and colPosition is 2, so we will set our matrix:

[
   [0, 0, 1],
   [0, 0, 0],
   [0, 0, 0]
]

Similarly for 2, place 2 at matrix[rowPosition[2]][colPosition[2]], i.e. matrix[2][1] ⇨

[
   [0, 0, 1],
   [0, 0, 0],
   [0, 2, 0]
]

Place 3 at matrix[rowPosition[3]][colPosition[3]], i.e. matrix[1][0] ⇨

[
   [0, 0, 1],
   [3, 0, 0],
   [0, 2, 0]
]