build-a-matrix-with-conditions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a positive integer <code>k</code>. You are also given:

<ul>
	<li>a 2D integer array <code>rowConditions</code> of size <code>n</code> where <code>rowConditions[i] = [abovei, belowi]</code>, and</li>
	<li>a 2D integer array <code>colConditions</code> of size <code>m</code> where <code>colConditions[i] = [lefti, righti]</code>.</li>
</ul>

The two arrays contain integers from <code>1</code> to <code>k</code>.

You have to build a <code>k x k</code> matrix that contains each of the numbers from <code>1</code> to <code>k</code> exactly once. The remaining cells should have the value <code>0</code>.

The matrix should also satisfy the following conditions:

<ul>
	<li>The number <code>abovei</code> should appear in a row that is strictly above the row at which the number <code>belowi</code> appears for all <code>i</code> from <code>0</code> to <code>n - 1</code>.</li>
	<li>The number <code>lefti</code> should appear in a column that is strictly left of the column at which the number <code>righti</code> appears for all <code>i</code> from <code>0</code> to <code>m - 1</code>.</li>
</ul>

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

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/07/06/gridosdrawio.png" style="width: 211px; height: 211px;" />
<pre>
Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
Output: [[3,0,0],[0,0,1],[0,2,0]]
Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.
The row conditions are the following:
- Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.
- Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.
The column conditions are the following:
- Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.
- Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.
Note that there may be multiple correct answers.
</pre>

Example 2:

<pre>
Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
Output: []
Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.
No matrix can satisfy all the conditions, so we return the empty matrix.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= k &lt;= 400</code></li>
	<li><code>1 &lt;= rowConditions.length, colConditions.length &lt;= 104</code></li>
	<li><code>rowConditions[i].length == colConditions[i].length == 2</code></li>
	<li><code>1 &lt;= abovei, belowi, lefti, righti &lt;= k</code></li>
	<li><code>abovei != belowi</code></li>
	<li><code>lefti != righti</code></li>
</ul>

buildMatrix

Build a Matrix With Conditions

Course Schedule

course-schedule

课程表

Course Schedule II

course-schedule-ii

课程表 II

Find Eventual Safe States

find-eventual-safe-states

找到最终的安全状态

Loud and Rich

loud-and-rich

喧闹和富有

Graph

Topological Sort

Array

Matrix

给你一个 正&nbsp;整数&nbsp;<code>k</code>&nbsp;，同时给你：

<ul>
	<li>一个大小为 <code>n</code>&nbsp;的二维整数数组&nbsp;<code>rowConditions</code>&nbsp;，其中&nbsp;<code>rowConditions[i] = [abovei, belowi]</code>&nbsp;和</li>
	<li>一个大小为 <code>m</code>&nbsp;的二维整数数组&nbsp;<code>colConditions</code>&nbsp;，其中&nbsp;<code>colConditions[i] = [lefti, righti]</code>&nbsp;。</li>
</ul>

两个数组里的整数都是&nbsp;<code>1</code>&nbsp;到&nbsp;<code>k</code>&nbsp;之间的数字。

你需要构造一个&nbsp;<code>k x k</code>&nbsp;的矩阵，<code>1</code>&nbsp;到&nbsp;<code>k</code>&nbsp;每个数字需要&nbsp;恰好出现一次&nbsp;。剩余的数字都是&nbsp;<code>0</code>&nbsp;。

矩阵还需要满足以下条件：

<ul>
	<li>对于所有 <code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;之间的下标&nbsp;<code>i</code>&nbsp;，数字&nbsp;<code>abovei</code>&nbsp;所在的 行&nbsp;必须在数字&nbsp;<code>belowi</code>&nbsp;所在行的上面。</li>
	<li>对于所有 <code>0</code>&nbsp;到 <code>m - 1</code>&nbsp;之间的下标&nbsp;<code>i</code>&nbsp;，数字&nbsp;<code>lefti</code>&nbsp;所在的 列&nbsp;必须在数字&nbsp;<code>righti</code>&nbsp;所在列的左边。</li>
</ul>

返回满足上述要求的 任意&nbsp;矩阵。如果不存在答案，返回一个空的矩阵。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/07/06/gridosdrawio.png" style="width: 211px; height: 211px;">

<pre>输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 1 在第 1 行，数字 2 在第 2&nbsp;行，1 在 2 的上面。
- 数字 3 在第 0&nbsp;行，数字 2 在第 2&nbsp;行，3 在 2 的上面。
列要求如下：
- 数字 2 在第 1&nbsp;列，数字 1 在第 2&nbsp;列，2 在 1 的左边。
- 数字 3 在第 0&nbsp;列，数字 2 在第 1&nbsp;列，3 在 2 的左边。
注意，可能有多种正确的答案。
</pre>

示例 2：

<pre>输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= k &lt;= 400</code></li>
	<li><code>1 &lt;= rowConditions.length, colConditions.length &lt;= 104</code></li>
	<li><code>rowConditions[i].length == colConditions[i].length == 2</code></li>
	<li><code>1 &lt;= abovei, belowi, lefti, righti &lt;= k</code></li>
	<li><code>abovei != belowi</code></li>
	<li><code>lefti != righti</code></li>
</ul>