Build a Matrix with Conditions

Try to solve the Build a Matrix with Conditions problem.

Statement

You are given a positive integer kk, and you’re also given two conditions:

  • A 2D integer array rowConditions of size nn, where rowConditions[i] = [above[i], below[i]]. This means that above[i] must appear in a row above below[i] in the final matrix.

  • A 2D integer array colConditions of size mm, where colConditions[i] = [left[i], right[i]]. This means that left[i] must appear in a column to the left of right[i] in the final matrix.

Both arrays contain integers from 11 to kk.

Your task is to build a k×kk \times k matrix that contains all the integers from 11 to kk exactly once, while the remaining cells can be filled with zeros.

The matrix should also satisfy the following conditions:

  • For each ii from 00 to n−1n-1, the integer above[i] must appear in a row strictly above below[i].

  • For each ii from 00 to m−1m-1, the integer left[i] must appear in a column strictly to the left of right[i].

Return any matrix that meets these conditions. If no valid matrix exists, return an empty matrix.

Constraints:

  • 2≤k≤4002 \leq k \leq 400

  • 1≤1 \leq rowConditions.length, colConditions.length ≤104\leq 10^4

  • rowConditions[i].length == colConditions[i].length =2= 2

  • 1≤1 \leq above[i], below[i], left[i], right[i] ≤k\leq k

  • above[i] ≠\neq below[i]

  • left[i] ≠\neq right[i]

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.