2392. Build a Matrix With Conditions


Problem Description

In this problem, we are tasked with constructing a k x k matrix where each number from 1 to k appears exactly once and the rest of the cells are filled with 0. The placement of numbers must follow certain conditions given by two 2D arrays: rowConditions and colConditions. rowConditions[i] = [above_i, below_i] indicates that the number above_i must be placed in a row above the number below_i. Similarly, colConditions[i] = [left_i, right_i] indicates that the number left_i must be placed in a column to the left of the number right_i.

The challenge lies in placing all numbers from 1 to k such that these above and left-below and right-side conditions are met simultaneously. If it's impossible to satisfy all conditions, we must return an empty matrix.

Intuition

The given problem has a natural correspondence to topological sorting, which is a linear ordering of vertices of a directed graph such that for every directed edge (u, v), vertex u comes before v in the ordering. Here, each vertex can represent a number from 1 to k, and the directed edges can represent the rows and columns ordering constraints provided by rowConditions and colConditions.

To arrive at the solution, we apply topological sort separately for the row and column conditions. This will give us a valid order for the rows and columns if a valid solution exists. If topological sort isn’t possible (which would indicate that there is a cycle in the graph of conditions), that implies there's no way to satisfy the conditions, and hence we return an empty matrix.

For the implementation of topological sort, we define a function f that does the following:

  1. Build a directed graph from the conditions given. We also maintain an in-degree count array to keep track of how many edges are coming into each node.
  2. Use a queue to maintain the nodes with an in-degree of 0. These nodes can immediately be added to the sorted result as there are no preceding nodes according to the conditions.
  3. When adding a node to the result, we also decrease the in-degrees of its connected nodes. If a node’s in-degree reaches 0, we add it to the queue as it’s ready to be part of the sorted result.
  4. If the resulting sorted array doesn't contain exactly k elements, we return None, signaling that a topological sort is not possible.

After carrying out the topological sort for both rowConditions and colConditions, we receive two ordered arrays, one for the rows and one for the columns. If either sort fails, we return an empty matrix. Otherwise, we use a mapping to translate column orders and populate the final answer matrix according to the sorted rows and columns.

Solution Approach

The solution for building the matrix adheres to a two-step approach using topological sorting. Let’s break down each step with its corresponding algorithms, data structures, and patterns applied:

  1. Topological Sorting via BFS (Breadth-First Search):

    Topological sort requires us to arrange nodes (in this case, numbers from 1 to k) such that for every directed edge (u, v), u is before v. We implement topological sorting through a modified BFS algorithm.

    • Graph Representation: We use a defaultdict of lists to create an adjacency list representation of a graph. The keys are our nodes (numbers) and the values are lists of adjacent nodes that must appear after the key node.

    • In-Degree Calculation: An array indeg is utilized to count how many edges point to each node. It essentially tells us if there are any conditions that need to be met before placing this node into our matrix.

    • Queue for Nodes with Zero In-Degree: A deque is utilized to keep track of the nodes that have no incoming edges (in-degree of 0). These are the nodes that can be placed immediately since there are no constraints on them.

    • BFS and Updating In-Degree: From the nodes in the queue, we perform a BFS. When a node is placed into the result, we iterate over its adjacent nodes in the graph, decrease their in-degree by one, and if any of these adjacent nodes now have an in-degree of 0, they are added to the queue.

    • Checking for a Successful Sort: If we cannot visit all k nodes during the topological sort (i.e., the resulting list is shorter than k), this indicates that there are cyclic dependencies and we cannot build a valid matrix. Therefore, we return None to indicate failure.

  2. Building the Result Matrix:

    Once we have a valid topological sort for both rows (rowConditions) and columns (colConditions), we proceed to populate our k x k matrix.

    • Mapping Columns: We create an array m that maps each number to its location in the column order. This allows us to know where to place each number in the matrix columns.

    • Populating the Matrix: With row and m giving us the row and column indices respectively, we iterate through the sorted row indices, and for each number, we use the column index from the mapping m. This is where we place the value v using ans[i][m[v]] = v.

    • Resulting Matrix: The result ans is the final k x k matrix that satisfies all the given conditions, filled with numbers from 1 to k, respecting the topological order, and with all remaining unfilled cells populated with zeroes.

In the case where either the row topological sort or column topological sort fails, we know that there is no valid solution and we return an empty matrix []. Otherwise, the filled ans matrix is returned as the solution.

Example Walkthrough

Let's go through an example to illustrate the solution approach described above. Assume we have a 3x3 matrix (k=3) and we need to place numbers 1, 2, and 3 in the matrix according to the given conditions.

Suppose rowConditions and colConditions are given as follows:

1rowConditions = [[2, 3], [1, 2]]
2colConditions = [[1, 3], [2, 3]]

Step 1: Topological Sorting

We start with topological sorting for the rows and columns separately. We'll use a Breadth-First Search (BFS) algorithm for this sorting.

  • For rows:
  1. Build a graph from the rowConditions and calculate the in-degrees:

    • Node 2 should come before 3, and Node 1 should come before 2.
    • Graph: 1 -> 2 -> 3 (1 points to 2, and 2 points to 3)
    • In-degree: [0, 1, 1] since Node 1 has 0 in-degree (no conditions), Node 2 has 1 in-degree (from 1), and Node 3 has 1 in-degree (from 2).
  2. Perform BFS:

    • Queue: Start with Node 1 (in-degree 0).
    • Add Node 1 to the result, queue next is Node 2 (decrement in-degrees and check).
    • Add Node 2 to the result, queue next is Node 3 (decrement in-degrees and check).
  • For columns:
  1. Build a graph from the colConditions and calculate the in-degrees:

    • Graph similar to row graph: 1 -> 3, 2 -> 3
    • In-degree: [0, 0, 2] (Node 3 has 2 in-degrees, Node 1 and Node 2 have 0).
  2. Perform BFS:

    • Queue: Start with Node 1 and Node 2 (both have in-degree 0).
    • Add Node 1 and Node 2 to the result, queue next is Node 3.

Step 2: Building the Result Matrix

Now, we use the obtained topological sorts to fill in our matrix.

  • Row order from topological sort: [1, 2, 3]
  • Column order from topological sort: [1, 2, 3]

Create a mapping of column indices: m = [0, 1, 2]

We now populate the matrix ans, using the order from row and column topological sorts and the mapping m:

  • Place 1 at ans[0][m[0]], which is ans[0][0]
  • Place 2 at ans[1][m[1]], which is ans[1][1]
  • Place 3 at ans[2][m[2]], which is ans[2][2]

The remaining cells are filled with zeros. Our final matrix looks like this:

1ans = [
2    [1, 0, 0],
3    [0, 2, 0],
4    [0, 0, 3]
5]

This matrix satisfies the given row and column conditions:

  • Number 2 is below number 1 (row condition).
  • Number 3 is below number 2 (row condition).
  • Number 3 is to the right of number 1 (column condition).
  • Number 3 is to the right of number 2 (column condition).

In conclusion, the matrix ans is the valid configuration we were looking to construct based on the given rowConditions and colConditions. If at any point during the topological sorting step we found a cycle or could not visit all nodes, that would have indicated there is no valid matrix configuration, and the result would have been an empty matrix. But in this example, everything checks out and we successfully built the matrix.

Python Solution

1from collections import defaultdict, deque  # for using defaultdict and deque
2
3class Solution:
4    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
5      
6        # Helper function to find the topological order based on the given conditions
7        def find_topological_order(conditions):
8            graph = defaultdict(list)
9            indegree = [0] * (k + 1)
10          
11            # Create graph and indegree list
12            for u, v in conditions:
13                graph[u].append(v)
14                indegree[v] += 1
15
16            # Initialize queue with nodes having indegree 0
17            queue = deque([node for node in range(1, k+1) if indegree[node] == 0])
18            order = []
19          
20            # Perform BFS to validate and get the topological order
21            while queue:
22                node = queue.popleft()
23                order.append(node)
24                for neighbor in graph[node]:
25                    indegree[neighbor] -= 1
26                    if indegree[neighbor] == 0:
27                        queue.append(neighbor)
28          
29            # If we can't order exactly `k` elements, return None
30            return order if len(order) == k else None
31
32        # Find topological order for both rows and columns
33        row_order = find_topological_order(rowConditions)
34        column_order = find_topological_order(colConditions)
35
36        # If either row or column topological order is impossible, return an empty matrix
37        if row_order is None or column_order is None:
38            return []
39      
40        # Initialize the matrix to be returned
41        matrix = [[0] * k for _ in range(k)]
42        column_position = [0] * (k + 1)
43
44        # Fill in the column position for each element based on its order
45        for position, element in enumerate(column_order):
46            column_position[element] = position
47
48        # Place each element in the matrix based on the row and column orders
49        for i, elem_row in enumerate(row_order):
50            col = column_position[elem_row]
51            matrix[i][col] = elem_row
52
53        return matrix
54

Java Solution

1class Solution {
2    private int size;
3
4    // Function to construct the matrix based on given row and column conditions
5    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
6        this.size = k;
7        // Determine the order of elements based on row conditions
8        List<Integer> rowOrder = getOrder(rowConditions);
9        // Determine the order of elements based on column conditions
10        List<Integer> colOrder = getOrder(colConditions);
11      
12        // If we cannot satisfy either row or column conditions, return an empty matrix
13        if (rowOrder == null || colOrder == null) {
14            return new int[0][0];
15        }
16      
17        // Initialize the answer matrix with zeroes
18        int[][] matrix = new int[size][size];
19        // Array to store the column indices for the elements in the matrix
20        int[] columnMapping = new int[size + 1];
21        // Map the value to its corresponding column index
22        for (int i = 0; i < size; ++i) {
23            columnMapping[colOrder.get(i)] = i;
24        }
25        // Fill the matrix with the correct values at the right positions
26        for (int i = 0; i < size; ++i) {
27            matrix[i][columnMapping[rowOrder.get(i)]] = rowOrder.get(i);
28        }
29        // Return the fully constructed matrix
30        return matrix;
31    }
32
33    // Function to determine the order of elements based on conditions (edges of a directed graph)
34    private List<Integer> getOrder(int[][] conditions) {
35        // Graph to represent conditions
36        List<Integer>[] graph = new List[size + 1];
37        // Initialize lists for all vertices in the graph
38        Arrays.setAll(graph, element -> new ArrayList<>());
39        // Array to store the number of incoming edges (in-degree) for each vertex
40        int[] incomingEdges = new int[size + 1];
41      
42        // Build the graph based on the conditions
43        for (var edge : conditions) {
44            int from = edge[0], to = edge[1];
45            graph[from].add(to);
46            ++incomingEdges[to];
47        }
48      
49        // Queue to store the vertices with no incoming edges
50        Deque<Integer> queue = new ArrayDeque<>();
51        for (int i = 1; i <= size; ++i) {
52            if (incomingEdges[i] == 0) {
53                queue.offer(i);
54            }
55        }
56      
57        List<Integer> order = new ArrayList<>();
58        // Process vertices in topological order
59        while (!queue.isEmpty()) {
60            int vertex = queue.pollFirst();
61            order.add(vertex);
62            // Decrease the in-degree of neighboring vertices and add to queue if they have no incoming edges left
63            for (int neighbour : graph[vertex]) {
64                if (--incomingEdges[neighbour] == 0) {
65                    queue.offer(neighbour);
66                }
67            }
68        }
69      
70        // If the size of the order list equals the size k, we successfully found an order, otherwise return null
71        return order.size() == size ? order : null;
72    }
73}
74

C++ Solution

1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    int dimension;
7
8    // Helper function to process the topological sort on the given conditions
9    vector<int> topologicalSort(vector<vector<int>>& conditions) {
10        // Graph representation and array to track incoming edges
11        vector<vector<int>> graph(dimension + 1);
12        vector<int> inDegree(dimension + 1);
13
14        // Create graph and update in-degrees for each node
15        for (auto& edge : conditions) {
16            int from = edge[0], to = edge[1];
17            graph[from].push_back(to);
18            ++inDegree[to];
19        }
20
21        queue<int> queue;
22
23        // Initialize queue with nodes having no incoming edges
24        for (int i = 1; i <= dimension; ++i) {
25            if (inDegree[i] == 0) {
26                queue.push(i);
27            }
28        }
29
30        vector<int> sortedOrder;
31        // Perform topological sort
32        while (!queue.empty()) {
33            int count = queue.size();
34            while (count--) {
35                int node = queue.front();
36                sortedOrder.push_back(node);
37                queue.pop();
38                // Reduce in-degree for neighboring nodes and
39                // add them to the queue if their in-degree becomes zero
40                for (int neighbor : graph[node]) {
41                    if (--inDegree[neighbor] == 0) {
42                        queue.push(neighbor);
43                    }
44                }
45            }
46        }
47        // If the sorted order does not include all nodes, return an empty array
48        return sortedOrder.size() == dimension ? sortedOrder : vector<int>();
49    }
50
51    // Public method to build the desired matrix based on row and column conditions
52    vector<vector<int>> buildMatrix(int dimension, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
53        this->dimension = dimension;
54        // Perform topological sort on both row and column conditions
55        vector<int> rowOrder = topologicalSort(rowConditions);
56        vector<int> colOrder = topologicalSort(colConditions);
57
58        // If either sort fails, return an empty matrix
59        if (rowOrder.empty() || colOrder.empty()) return {};
60
61        // Initialize the answer matrix with the correct dimensions
62        vector<vector<int>> answer(dimension, vector<int>(dimension));
63        vector<int> colIndexMap(dimension + 1);
64
65        // Map the column order numbers to indices
66        for (int i = 0; i < dimension; ++i) {
67            colIndexMap[colOrder[i]] = i;
68        }
69
70        // Fill matrix using the sorted row and column orders
71        for (int i = 0; i < dimension; ++i) {
72            int rowIndex = i;
73            int colIndex = colIndexMap[rowOrder[i]];
74            answer[rowIndex][colIndex] = rowOrder[i];
75        }
76        return answer;
77    }
78};
79

Typescript Solution

1function buildMatrix(k: number, rowConditions: number[][], colConditions: number[][]): number[][] {
2    // Helper function to process conditions and perform topological sorting
3    function processConditions(conditions: number[][]): number[] {
4        // Create an adjacency list for the graph representing conditions
5        const graph = Array.from({ length: k + 1 }, () => []);
6        // Array to store in-degrees of each node
7        const inDegrees = new Array(k + 1).fill(0);
8      
9        // Populate the adjacency list and update in-degrees
10        for (const [from, to] of conditions) {
11            graph[from].push(to);
12            ++inDegrees[to];
13        }
14      
15        // Queue to manage nodes with in-degree of 0
16        const queue: number[] = [];
17        for (let i = 1; i < inDegrees.length; ++i) {
18            if (inDegrees[i] === 0) {
19                queue.push(i);
20            }
21        }
22      
23        // List to store the order of nodes after topological sorting
24        const order: number[] = [];
25        while (queue.length) {
26            for (let i = queue.length; i > 0; --i) {
27                const node = queue.shift();
28                order.push(node);
29                // Decrease in-degrees of adjacent nodes and enqueue if in-degree becomes 0
30                for (const adjacent of graph[node]) {
31                    if (--inDegrees[adjacent] === 0) {
32                        queue.push(adjacent);
33                    }
34                }
35            }
36        }
37      
38        // If the topologically sorted list has k elements, return it; otherwise, return empty array
39        return order.length === k ? order : [];
40    }
41
42    // Process the row conditions and column conditions through the helper function
43    const rowOrder = processConditions(rowConditions);
44    const colOrder = processConditions(colConditions);
45
46    // If we cannot find a valid order for either rows or columns, return an empty array
47    if (rowOrder.length === 0 || colOrder.length === 0) return [];
48
49    // Initialize the matrix with zeros
50    const matrix = Array.from({ length: k }, () => new Array(k).fill(0));
51  
52    // Mapping to store the index of each value in colOrder
53    const colIndexMap = new Array(k + 1).fill(0);
54    for (let i = 0; i < k; ++i) {
55        colIndexMap[colOrder[i]] = i;
56    }
57
58    // Fill the matrix using the order of rows and mapped column indices
59    for (let i = 0; i < k; ++i) {
60        matrix[i][colIndexMap[rowOrder[i]]] = rowOrder[i];
61    }
62
63    // Return the constructed matrix
64    return matrix;
65}
66

Time and Space Complexity

Time Complexity

The given code consists primarily of two parts: constructing the order of elements according to the input conditions (rowConditions and colConditions) and then building the matrix based on these orders.

  1. For constructing the order with the function f(cond):

    • It creates a graph where each element i points to the elements it must precede in sequence. The graph creation takes O(E) time where E is the total number of conditions in rowConditions or colConditions.
    • It initializes an indegree array indeg which takes O(k) time.
    • It processes each node exactly once using a queue to perform topological sort, which will be O(V + E), where V is the number of vertices (which is k) and E is the number of edges.
    • As f(cond) is called twice (once for rows and once for columns), the time complexity for this part is 2 * O(V + E) = O(2k + 2E) = O(k + E).
  2. For the construction of the answer matrix:

    • The code uses a map m to keep track of the index at which each value should be placed in the matrix, which takes O(k) time.
    • It then iterates over each element of row and places it in the correct position in the ans matrix, which takes O(k) time.

Overall, the time complexity of the code is determined by the topological sort and the construction of the result matrix, which would be O(k + E) + O(k) = O(k + E).

Space Complexity

The space complexity of the code is determined by:

  • The graph g and indegree array indeg which collectively take O(k + E) space.
  • The queue q used for storing intermediate values while doing topological sort, which in the worst case could store all k vertices, taking O(k) space.
  • The result array res that will contain k elements when the order is successfully constructed, taking O(k) space.
  • The answer matrix ans which is a k x k matrix, so it takes O(k^2) space.
  • Auxiliary space for the map m and variables used to iterate, which take O(k).

When added together, the space complexity is O(k + E) + O(k) + O(k) + O(k^2) + O(k) = O(k^2 + k + E).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫