Build a Matrix With Conditions - Practice Coding Problems

Build a Matrix With Conditions - Problem

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

a 2D integer array rowConditions of size n where rowConditions[i] = [above_i, below_i], and
a 2D integer array colConditions of size m where colConditions[i] = [left_i, right_i].

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 above_i should appear in a row that is strictly above the row at which the number below_i appears for all i from 0 to n - 1.
The number left_i should appear in a column that is strictly left of the column at which the number right_i appears for all i from 0 to m - 1.

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

Input & Output

Example 1 — Basic Case

$ Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]

› Output: [[3,0,0],[2,0,0],[1,0,0]]

💡 Note: Number 1 must be above 2, and 3 must be above 2 (row constraints). Number 2 must be left of 1, and 3 must be left of 2 (column constraints). One valid arrangement places 1 at (2,0), 2 at (1,0), and 3 at (0,0).

Example 2 — No Solution

$ Input: k = 3, rowConditions = [[1,2],[2,1]], colConditions = []

› Output: []

💡 Note: Impossible constraints: 1 must be above 2 AND 2 must be above 1. This creates a cycle, so no valid matrix exists.

Example 3 — Single Element

$ Input: k = 1, rowConditions = [], colConditions = []

› Output: [[1]]

💡 Note: Only one number to place with no constraints, so place 1 at position (0,0).

Constraints

2 ≤ k ≤ 400
1 ≤ rowConditions.length, colConditions.length ≤ 10⁴
rowConditions[i] = [above_i, below_i]
colConditions[i] = [left_i, right_i]
1 ≤ above_i, below_i, left_i, right_i ≤ k

Visualization

Tap to expand

Understanding the Visualization

Input Constraints

Row and column positioning rules for numbers 1 to k

Convert to Graphs

Transform constraints into directed dependency graphs

Build Matrix

Place numbers according to topologically sorted orderings

Key Takeaway

🎯 Key Insight: Convert positioning constraints to directed graphs and use topological sorting to find valid orderings

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to convert positioning constraints into directed graphs and use topological sorting to find valid orderings. Best approach uses topological sort to determine row and column orderings separately, then construct the matrix. Time: O(k + n + m), Space: O(k + n + m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(k! × k²)	O(k²)	Try all possible placements of numbers 1 to k in the matrix
Topological Sort	O(k + n + m)	O(k + n + m)	Use topological sorting to determine valid row and column orderings

Brute Force — Algorithm Steps

Generate all permutations of numbers 1 to k
For each permutation, try placing in all possible positions
Check if all row and column conditions are satisfied
Return first valid matrix or empty if none found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Positions

Create all possible (row,col) positions for k numbers

Try Each Permutation

For each arrangement, place numbers and check constraints

Validate Conditions

Check if row and column ordering constraints are satisfied

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int k, int** rowConditions, int rowSize, int** colConditions, int colSize, int* returnSize, int** returnColumnSizes) {
    // Brute force is too complex to implement in C for demo
    // Return empty matrix
    *returnSize = 0;
    *returnColumnSizes = NULL;
    return NULL;
}

int main() {
    int k;
    scanf("%d", &k);
    
    // For demo purposes, just print empty array
    printf("[]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k! × k²)

k! permutations, each requiring O(k²) time to place and validate

✓ Linear Growth

Space Complexity

O(k²)

Matrix storage plus recursion stack for permutation generation

✓ Linear Space

28.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler