FPEvalDataset/LeetCodeProblem
0305
1{2 "id": 2472,3 "name": "build_a_matrix_with_conditions",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/build-a-matrix-with-conditions/",6 "date": "1661040000000",7 "task_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]`, 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. **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:** 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. ``` **Example 2:** ``` **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. ``` **Constraints:** `2 <= k <= 400` `1 <= rowConditions.length, colConditions.length <= 104` `rowConditions[i].length == colConditions[i].length == 2` `1 <= abovei, belowi, lefti, righti <= k` `abovei != belowi` `lefti != righti`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]",12 "output": "[[3,0,0],[0,0,1],[0,2,0]] "13 },14 {15 "label": "Example 2",16 "input": "k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]",17 "output": "[] "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 113,24 [25 [26 94,27 7828 ],29 [30 92,31 332 ],33 [34 42,35 7336 ],37 [38 69,39 8640 ],41 [42 17,43 7944 ],45 [46 37,47 7448 ],49 [50 16,51 7152 ],53 [54 70,55 1356 ],57 [58 67,59 11260 ],61 [62 11,63 7364 ],65 [66 110,67 9668 ],69 [70 32,71 2772 ],73 [74 71,75 6676 ],77 [78 88,79 180 ],81 [82 87,83 384 ],85 [86 64,87 4688 ],89 [90 16,91 7092 ],93 [94 12,95 9496 ],97 [98 33,99 42100 ],101 [102 31,103 10104 ],105 [106 113,107 89108 ],109 [110 14,111 30112 ],113 [114 79,115 50116 ],117 [118 97,119 46120 ],121 [122 110,123 104124 ],125 [126 95,127 1128 ],129 [130 73,131 104132 ],133 [134 96,135 105136 ],137 [138 92,139 55140 ],141 [142 53,143 90144 ],145 [146 15,147 66148 ],149 [150 57,151 59152 ],153 [154 78,155 88156 ],157 [158 4,159 113160 ],161 [162 52,163 17164 ],165 [166 47,167 39168 ],169 [170 72,171 59172 ],173 [174 95,175 28176 ],177 [178 89,179 47180 ],181 [182 29,183 30184 ],185 [186 101,187 102188 ],189 [190 11,191 82192 ]193 ],194 [195 [196 110,197 87198 ],199 [200 37,201 65202 ],203 [204 58,205 20206 ],207 [208 69,209 105210 ],211 [212 34,213 40214 ],215 [216 67,217 64218 ],219 [220 113,221 67222 ],223 [224 9,225 81226 ],227 [228 42,229 79230 ],231 [232 77,233 52234 ],235 [236 54,237 34238 ],239 [240 101,241 55242 ],243 [244 13,245 52246 ],247 [248 4,249 105250 ],251 [252 50,253 10254 ],255 [256 7,257 91258 ],259 [260 46,261 67262 ],263 [264 54,265 65266 ],267 [268 51,269 73270 ],271 [272 54,273 43274 ],275 [276 53,277 28278 ],279 [280 84,281 23282 ],283 [284 99,285 14286 ],287 [288 35,289 73290 ],291 [292 112,293 70294 ],295 [296 74,297 55298 ],299 [300 105,301 88302 ],303 [304 93,305 84306 ],307 [308 31,309 87310 ],311 [312 93,313 30314 ],315 [316 79,317 20318 ],319 [320 1,321 51322 ],323 [324 86,325 11326 ],327 [328 91,329 2330 ],331 [332 7,333 27334 ],335 [336 101,337 102338 ],339 [340 19,341 44342 ],343 [344 51,345 59346 ],347 [348 11,349 26350 ],351 [352 35,353 51354 ],355 [356 72,357 31358 ],359 [360 64,361 51362 ],363 [364 113,365 71366 ],367 [368 57,369 113370 ],371 [372 62,373 60374 ],375 [376 94,377 23378 ],379 [380 47,381 1382 ],383 [384 72,385 94386 ],387 [388 27,389 59390 ],391 [392 67,393 68394 ],395 [396 46,397 16398 ],399 [400 74,401 30402 ],403 [404 29,405 6406 ],407 [408 43,409 100410 ],411 [412 69,413 68414 ],415 [416 112,417 32418 ],419 [420 9,421 15422 ],423 [424 108,425 112426 ],427 [428 103,429 49430 ],431 [432 36,433 49434 ],435 [436 86,437 11438 ],439 [440 80,441 12442 ],443 [444 86,445 49446 ],447 [448 60,449 80450 ],451 [452 61,453 39454 ],455 [456 31,457 47458 ]459 ]460 ],461 "output": [462 [463 0,464 0,465 0,466 0,467 0,468 0,469 0,470 0,471 0,472 0,473 0,474 0,475 0,476 0,477 0,478 0,479 0,480 0,481 0,482 0,483 0,484 0,485 0,486 0,487 0,488 0,489 0,490 0,491 0,492 0,493 0,494 0,495 0,496 0,497 0,498 0,499 0,500 0,501 0,502 0,503 0,504 0,505 0,506 0,507 0,508 0,509 0,510 0,511 0,512 0,513 0,514 0,515 0,516 0,517 0,518 0,519 0,520 0,521 0,522 0,523 0,524 0,525 0,526 0,527 0,528 0,529 0,530 0,531 0,532 0,533 0,534 0,535 0,536 0,537 0,538 0,539 0,540 0,541 0,542 0,543 0,544 0,545 0,546 0,547 0,548 0,549 0,550 0,551 0,552 0,553 0,554 0,555 2,556 0,557 0,558 0,559 0,560 0,561 0,562 0,563 0,564 0,565 0,566 0,567 0,568 0,569 0,570 0,571 0,572 0,573 0,574 0,575 0576 ],577 [578 0,579 4,580 0,581 0,582 0,583 0,584 0,585 0,586 0,587 0,588 0,589 0,590 0,591 0,592 0,593 0,594 0,595 0,596 0,597 0,598 0,599 0,600 0,601 0,602 0,603 0,604 0,605 0,606 0,607 0,608 0,609 0,610 0,611 0,612 0,613 0,614 0,615 0,616 0,617 0,618 0,619 0,620 0,621 0,622 0,623 0,624 0,625 0,626 0,627 0,628 0,629 0,630 0,631 0,632 0,633 0,634 0,635 0,636 0,637 0,638 0,639 0,640 0,641 0,642 0,643 0,644 0,645 0,646 0,647 0,648 0,649 0,650 0,651 0,652 0,653 0,654 0,655 0,656 0,657 0,658 0,659 0,660 0,661 0,662 0,663 0,664 0,665 0,666 0,667 0,668 0,669 0,670 0,671 0,672 0,673 0,674 0,675 0,676 0,677 0,678 0,679 0,680 0,681 0,682 0,683 0,684 0,685 0,686 0,687 0,688 0,689 0,690 0691 ],692 [693 0,694 0,695 5,696 0,697 0,698 0,699 0,700 0,701 0,702 0,703 0,704 0,705 0,706 0,707 0,708 0,709 0,710 0,711 0,712 0,713 0,714 0,715 0,716 0,717 0,718 0,719 0,720 0,721 0,722 0,723 0,724 0,725 0,726 0,727 0,728 0,729 0,730 0,731 0,732 0,733 0,734 0,735 0,736 0,737 0,738 0,739 0,740 0,741 0,742 0,743 0,744 0,745 0,746 0,747 0,748 0,749 0,750 0,751 0,752 0,753 0,754 0,755 0,756 0,757 0,758 0,759 0,760 0,761 0,762 0,763 0,764 0,765 0,766 0,767 0,768 0,769 0,770 0,771 0,772 0,773 0,774 0,775 0,776 0,777 0,778 0,779 0,780 0,781 0,782 0,783 0,784 0,785 0,786 0,787 0,788 0,789 0,790 0,791 0,792 0,793 0,794 0,795 0,796 0,797 0,798 0,799 0,800 0,801 0,802 0,803 0,804 0,805 0806 ],807 [808 0,809 0,810 0,811 0,812 0,813 0,814 0,815 0,816 0,817 0,818 0,819 0,820 0,821 0,822 0,823 0,824 0,825 0,826 0,827 0,828 0,829 0,830 0,831 0,832 0,833 0,834 0,835 0,836 0,837 0,838 0,839 0,840 0,841 0,842 0,843 0,844 0,845 0,846 0,847 0,848 0,849 0,850 0,851 0,852 0,853 0,854 0,855 0,856 0,857 0,858 0,859 0,860 0,861 0,862 0,863 0,864 0,865 0,866 0,867 0,868 0,869 0,870 0,871 0,872 0,873 0,874 0,875 0,876 0,877 6,878 0,879 0,880 0,881 0,882 0,883 0,884 0,885 0,886 0,887 0,888 0,889 0,890 0,891 0,892 0,893 0,894 0,895 0,896 0,897 0,898 0,899 0,900 0,901 0,902 0,903 0,904 0,905 0,906 0,907 0,908 0,909 0,910 0,911 0,912 0,913 0,914 0,915 0,916 0,917 0,918 0,919 0,920 0921 ],922 [923 0,924 0,925 0,926 7,927 0,928 0,929 0,930 0,931 0,932 0,933 0,934 0,935 0,936 0,937 0,938 0,939 0,940 0,941 0,942 0,943 0,944 0,945 0,946 0,947 0,948 0,949 0,950 0,951 0,952 0,953 0,954 0,955 0,956 0,957 0,958 0,959 0,960 0,961 0,962 0,963 0,964 0,965 0,966 0,967 0,968 0,969 0,970 0,971 0,972 0,973 0,974 0,975 0,976 0,977 0,978 0,979 0,980 0,981 0,982 0,983 0,984 0,985 0,986 0,987 0,988 0,989 0,990 0,991 0,992 0,993 0,994 0,995 0,996 0,997 0,998 0,999 0,1000 0,1001 0,1002 0,1003 0,1004 0,1005 0,1006 0,1007 0,1008 0,1009 0,1010 0,1011 0,1012 0,1013 0,1014 0,1015 0,1016 0,1017 0,1018 0,1019 0,1020 0,1021 0,1022 0,1023 0,1024 0,1025 0,1026 0,1027 0,1028 0,1029 0,1030 0,1031 0,1032 0,1033 0,1034 0,1035 01036 ],1037 [1038 0,1039 0,1040 0,1041 0,1042 8,1043 0,1044 0,1045 0,1046 0,1047 0,1048 0,1049 0,1050 0,1051 0,1052 0,1053 0,1054 0,1055 0,1056 0,1057 0,1058 0,1059 0,1060 0,1061 0,1062 0,1063 0,1064 0,1065 0,1066 0,1067 0,1068 0,1069 0,1070 0,1071 0,1072 0,1073 0,1074 0,1075 0,1076 0,1077 0,1078 0,1079 0,1080 0,1081 0,1082 0,1083 0,1084 0,1085 0,1086 0,1087 0,1088 0,1089 0,1090 0,1091 0,1092 0,1093 0,1094 0,1095 0,1096 0,1097 0,1098 0,1099 0,1100 0,1101 0,1102 0,1103 0,1104 0,1105 0,1106 0,1107 0,1108 0,1109 0,1110 0,1111 0,1112 0,1113 0,1114 0,1115 0,1116 0,1117 0,1118 0,1119 0,1120 0,1121 0,1122 0,1123 0,1124 0,1125 0,1126 0,1127 0,1128 0,1129 0,1130 0,1131 0,1132 0,1133 0,1134 0,1135 0,1136 0,1137 0,1138 0,1139 0,1140 0,1141 0,1142 0,1143 0,1144 0,1145 0,1146 0,1147 0,1148 0,1149 0,1150 01151 ],1152 [1153 0,1154 0,1155 0,1156 0,1157 0,1158 9,1159 0,1160 0,1161 0,1162 0,1163 0,1164 0,1165 0,1166 0,1167 0,1168 0,1169 0,1170 0,1171 0,1172 0,1173 0,1174 0,1175 0,1176 0,1177 0,1178 0,1179 0,1180 0,1181 0,1182 0,1183 0,1184 0,1185 0,1186 0,1187 0,1188 0,1189 0,1190 0,1191 0,1192 0,1193 0,1194 0,1195 0,1196 0,1197 0,1198 0,1199 0,1200 0,