Build a Matrix With Conditions

Hard Top 250

Associated Patterns

Graphs Graphs

Interviewed At (Company Tags)

Google

External Reference View on LeetCode

Problem Description

You are given a positive integer k. You are also given:

A 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi] indicates that the number abovei must appear in a row that is strictly above the row at which belowi appears.
A 2D integer array colConditions of size m where colConditions[i] = [lefti, righti] indicates that the number lefti must appear in a column that is strictly to the left of the column at which righti appears.

All the elements from 1 to k must appear in the matrix exactly once. All other cells should contain 0.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

Examples

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: Row conditions: 1 is above 2, 3 is above 2. Col conditions: 2 is left of 1, 3 is left of 2. One valid matrix is: 3 0 0 0 0 1 0 2 0

Constraints

2 ≤ k ≤ 400
1 ≤ rowConditions.length, colConditions.length ≤ 10⁴
rowConditions[i].length == colConditions[i].length == 2
1 ≤ abovei, belowi, lefti, righti ≤ k
abovei != belowi
lefti != righti

Independent Row and Column Topological Sorts

The key insight is that row placements and column placements are completely independent of each other.

rowConditions defines a directed graph where edge u -> v means u must be placed in a row index smaller than v.
colConditions defines a directed graph where edge u -> v means u must be placed in a column index smaller than v.

We can run topological sort on both graphs separately:

rowOrder = topoSort(rowConditions)
colOrder = topoSort(colConditions)

If either graph contains a cycle (topoSort output size is less than k), it is impossible to satisfy the conditions. Return an empty matrix.

If both are valid DAGs:

Construct a k x k matrix filled with 0.
For each number val from 1 to k:
- Find its row index r (its position in rowOrder).
- Find its column index c (its position in colOrder).
- Place val at matrix[r][c].

Solution: Double Topological Sort

import java.util.*;

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

        if (rowOrder.size() < k || colOrder.size() < k) {
            return new int[0][0]; // cycle detected, impossible
        }

        int[] rowMap = new int[k + 1];
        for (int i = 0; i < k; i++) {
            rowMap[rowOrder.get(i)] = i;
        }

        int[] colMap = new int[k + 1];
        for (int i = 0; i < k; i++) {
            colMap[colOrder.get(i)] = i;
        }

        int[][] matrix = new int[k][k];
        for (int val = 1; val <= k; val++) {
            matrix[rowMap[val]][colMap[val]] = val;
        }

        return matrix;
    }

    private List<Integer> topoSort(int k, int[][] conditions) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= k; i++) adj.add(new ArrayList<>());
        int[] inDegree = new int[k + 1];

        for (int[] cond : conditions) {
            adj.get(cond[0]).add(cond[1]);
            inDegree[cond[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            order.add(curr);

            for (int neighbor : adj.get(curr)) {
                if (--inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return order;
    }
}

from collections import deque

class Solution:
    def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]:
        def topo_sort(conditions):
            adj = [[] for _ in range(k + 1)]
            in_degree = [0] * (k + 1)
            for u, v in conditions:
                adj[u].append(v)
                in_degree[v] += 1

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

            while queue:
                curr = queue.popleft()
                order.append(curr)
                for neighbor in adj[curr]:
                    in_degree[neighbor] -= 1
                    if in_degree[neighbor] == 0:
                        queue.append(neighbor)

            return order

        row_order = topo_sort(rowConditions)
        col_order = topo_sort(colConditions)

        if len(row_order) < k or len(col_order) < k:
            return []

        row_map = {val: i for i, val in enumerate(row_order)}
        col_map = {val: i for i, val in enumerate(col_order)}

        matrix = [[0] * k for _ in range(k)]
        for val in range(1, k + 1):
            matrix[row_map[val]][col_map[val]] = val

        return matrix

#include <vector>
#include <queue>

class Solution {
    std::vector<int> topoSort(int k, const std::vector<std::vector<int>>& conditions) {
        std::vector<std::vector<int>> adj(k + 1);
        std::vector<int> inDegree(k + 1, 0);

        for (const auto& cond : conditions) {
            adj[cond[0]].push_back(cond[1]);
            inDegree[cond[1]]++;
        }

        std::queue<int> q;
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) q.push(i);
        }

        std::vector<int> order;
        while (!q.empty()) {
            int curr = q.front(); q.pop();
            order.push_back(curr);

            for (int neighbor : adj[curr]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return order;
    }

public:
    std::vector<std::vector<int>> buildMatrix(int k, std::vector<std::vector<int>>& rowConditions,
                                             std::vector<std::vector<int>>& colConditions) {
        auto rowOrder = topoSort(k, rowConditions);
        auto colOrder = topoSort(k, colConditions);

        if ((int)rowOrder.size() < k || (int)colOrder.size() < k) {
            return {};
        }

        std::vector<int> rowMap(k + 1), colMap(k + 1);
        for (int i = 0; i < k; i++) {
            rowMap[rowOrder[i]] = i;
            colMap[colOrder[i]] = i;
        }

        std::vector<std::vector<int>> matrix(k, std::vector<int>(k, 0));
        for (int val = 1; val <= k; val++) {
            matrix[rowMap[val]][colMap[val]] = val;
        }

        return matrix;
    }
};

Complexity Analysis:

Time Complexity: O(K + R + C) where R is rowConditions.length and C is colConditions.length. Topological sort on both graphs takes linear time relative to nodes and condition edges.
Space Complexity: O(K + R + C) to store the condition graphs, in-degrees, and coordinate mappings.