Build a matrix with conditions

Array Graph Theory Topological Sort Matrix

79.3% acceptance

Feb 25, 2026

1503

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;


fn topo_sort_mat(k: usize, conds: &[Vec<i32>]) -> Option<Vec<usize>> {
  let mut indeg = vec![0usize; k + 1];
  let mut adj = vec![vec![]; k + 1];
  for c in conds {
    adj[c[0] as usize].push(c[1] as usize);
    indeg[c[1] as usize] += 1;
  }
  let mut queue = VecDeque::new();
  for i in 1..=k { if indeg[i] == 0 { queue.push_back(i); } }
  let mut order = vec![];
  while let Some(u) = queue.pop_front() {
    order.push(u);
    for &v in &adj[u] {
      indeg[v] -= 1;
      if indeg[v] == 0 { queue.push_back(v); }
    }
  }
  if order.len() == k { Some(order) } else { None }
}

impl Solution {
  pub fn build_matrix(k: i32, row_conditions: Vec<Vec<i32>>, col_conditions: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let k = k as usize;
    let row_order = match topo_sort_mat(k, &row_conditions) { Some(o) => o, None => return vec![] };
    let col_order = match topo_sort_mat(k, &col_conditions) { Some(o) => o, None => return vec![] };
    let mut row_pos = vec![0usize; k + 1];
    let mut col_pos = vec![0usize; k + 1];
    for (i, &v) in row_order.iter().enumerate() { row_pos[v] = i; }
    for (i, &v) in col_order.iter().enumerate() { col_pos[v] = i; }
    let mut matrix = vec![vec![0i32; k]; k];
    for v in 1..=k { matrix[row_pos[v]][col_pos[v]] = v as i32; }
    matrix
  }
}