TheRealSamuel/LeetCodeProblem
0561
1{2 "id": 3578,3 "name": "construct_2d_grid_matching_graph_layout",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/construct-2d-grid-matching-graph-layout/",6 "date": "2024-09-29 00:00:00",7 "task_description": "You are given a 2D integer array `edges` representing an **undirected** graph having `n` nodes, where `edges[i] = [ui, vi]` denotes an edge between nodes `ui` and `vi`. Construct a 2D grid that satisfies these conditions: The grid contains **all nodes** from `0` to `n - 1` in its cells, with each node appearing exactly **once**. Two nodes should be in adjacent grid cells (**horizontally** or **vertically**) **if and only if** there is an edge between them in `edges`. It is guaranteed that `edges` can form a 2D grid that satisfies the conditions. Return a 2D integer array satisfying the conditions above. If there are multiple solutions, return _any_ of them. **Example 1:** **Input:** n = 4, edges = [[0,1],[0,2],[1,3],[2,3]] **Output:** [[3,1],[2,0]] **Explanation:** **Example 2:** **Input:** n = 5, edges = [[0,1],[1,3],[2,3],[2,4]] **Output:** [[4,2,3,1,0]] **Explanation:** **Example 3:** **Input:** n = 9, edges = [[0,1],[0,4],[0,5],[1,7],[2,3],[2,4],[2,5],[3,6],[4,6],[4,7],[6,8],[7,8]] **Output:** [[8,6,3],[7,4,2],[1,0,5]] **Explanation:** **Constraints:** `2 <= n <= 5 * 104` `1 <= edges.length <= 105` `edges[i] = [ui, vi]` `0 <= ui < vi < n` All the edges are distinct. The input is generated such that `edges` can form a 2D grid that satisfies the conditions.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]",12 "output": "[[3,1],[2,0]] "13 },14 {15 "label": "Example 2",16 "input": "n = 5, edges = [[0,1],[1,3],[2,3],[2,4]]",17 "output": "[[4,2,3,1,0]] "18 },19 {20 "label": "Example 3",21 "input": "n = 9, edges = [[0,1],[0,4],[0,5],[1,7],[2,3],[2,4],[2,5],[3,6],[4,6],[4,7],[6,8],[7,8]]",22 "output": "[[8,6,3],[7,4,2],[1,0,5]] "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 11591,29 [30 [31 1238,32 853733 ],34 [35 4450,36 572637 ],38 [39 341,40 1024141 ],42 [43 4445,44 538245 ],46 [47 4722,48 735349 ],50 [51 9424,52 976853 ],54 [55 2695,56 833857 ],58 [59 2242,60 780461 ],62 [63 4943,64 600965 ],66 [67 2300,68 477669 ],70 [71 3354,72 643973 ],74 [75 448,76 1048877 ],78 [79 1725,80 747081 ],82 [83 1004,84 545885 ],86 [87 4997,88 962889 ],90 [91 6882,92 1121993 ],94 [95 5021,96 1115397 ],98 [99 3524,100 8139101 ],102 [103 7163,104 11057105 ],106 [107 3044,108 10720109 ],110 [111 1717,112 7178113 ],114 [115 2039,116 2533117 ],118 [119 2642,120 3735121 ],122 [123 3154,124 5603125 ],126 [127 330,128 7742129 ],130 [131 743,132 3939133 ],134 [135 2725,136 8873137 ],138 [139 1725,140 3282141 ],142 [143 6991,144 8479145 ],146 [147 1225,148 6342149 ],150 [151 860,152 1491153 ],154 [155 5249,156 5661157 ],158 [159 1670,160 6958161 ],162 [163 1593,164 5048165 ],166 [167 9512,168 11412169 ],170 [171 8447,172 11088173 ],174 [175 6,176 5551177 ],178 [179 2657,180 5147181 ],182 [183 3777,184 5178185 ],186 [187 4022,188 10644189 ],190 [191 2341,192 5850193 ],194 [195 8662,196 9929197 ],198 [199 3698,200 5070201 ],202 [203 10771,204 11228205 ],206 [207 5332,208 7766209 ],210 [211 8974,212 10955213 ],214 [215 7066,216 9188217 ],218 [219 245,220 8169221 ],222 [223 5441,224 7709225 ],226 [227 4224,228 7745229 ],230 [231 4569,232 11163233 ],234 [235 4774,236 5933237 ],238 [239 7184,240 8096241 ],242 [243 3379,244 9612245 ],246 [247 6118,248 10553249 ],250 [251 1881,252 7154253 ],254 [255 6695,256 10564257 ],258 [259 3472,260 6770261 ],262 [263 3589,264 7355265 ],266 [267 106,268 2698269 ],270 [271 4889,272 6041273 ],274 [275 6363,276 10734277 ],278 [279 1943,280 4999281 ],282 [283 2529,284 11512285 ],286 [287 3900,288 8910289 ],290 [291 5015,292 7843293 ],294 [295 3205,296 7365297 ],298 [299 629,300 8108301 ],302 [303 3949,304 8048305 ],306 [307 3054,308 4163309 ],310 [311 6158,312 6545313 ],314 [315 1374,316 5229317 ],318 [319 832,320 11096321 ],322 [323 149,324 1240325 ],326 [327 1683,328 6738329 ],330 [331 680,332 876333 ],334 [335 1853,336 3951337 ],338 [339 2599,340 5461341 ],342 [343 5967,344 9579345 ],346 [347 577,348 1128349 ],350 [351 6710,352 7408353 ],354 [355 2510,356 6143357 ],358 [359 8958,360 11495361 ],362 [363 4588,364 11539365 ],366 [367 10997,368 11301369 ],370 [371 10596,372 10957373 ],374 [375 5080,376 5585377 ],378 [379 2350,380 11523381 ],382 [383 3797,384 7253385 ],386 [387 6921,388 8759389 ],390 [391 4829,392 5185393 ],394 [395 1971,396 2078397 ],398 [399 2181,400 3608401 ],402 [403 5646,404 7659405 ],406 [407 135,408 379409 ],410 [411 4737,412 5596413 ],414 [415 2808,416 3706417 ],418 [419 5925,420 10457421 ],422 [423 8342,424 8903425 ],426 [427 365,428 1780429 ],430 [431 1553,432 6641433 ],434 [435 8614,436 10530437 ],438 [439 4682,440 7767441 ],442 [443 573,444 5866445 ],446 [447 294,448 6451449 ],450 [451 4502,452 8331453 ],454 [455 1947,456 6945457 ],458 [459 1513,460 10625461 ],462 [463 3565,464 10636465 ],466 [467 328,468 8664469 ],470 [471 1901,472 3567473 ],474 [475 7492,476 10022477 ],478 [479 539,480 9638481 ],482 [483 1198,484 2104485 ],486 [487 5118,488 10899489 ],490 [491 354,492 436493 ],494 [495 6670,496 10587497 ],498 [499 1912,500 10492501 ],502 [503 599,504 4404505 ],506 [507 6595,508 7969509 ],510 [511 2987,512 4364513 ],514 [515 2997,516 5052517 ],518 [519 5414,520 10668521 ],522 [523 438,524 2766525 ],526 [527 99,528 3300529 ],530 [531 1372,532 9989533 ],534 [535 1365,536 8818537 ],538 [539 4236,540 9878541 ],542 [543 6474,544 6861545 ],546 [547 9027,548 11584549 ],550 [551 3578,552 8188553 ],554 [555 9457,556 11168557 ],558 [559 1761,560 5785561 ],562 [563 8589,564 11358565 ],566 [567 6280,568 9247569 ],570 [571 5494,572 9092573 ],574 [575 1237,576 10703577 ],578 [579 1832,580 7880581 ],582 [583 6550,584 10828585 ],586 [587 203,588 6282589 ],590 [591 387,592 1673593 ],594 [595 5175,596 10278597 ],598 [599 6207,600 8210601 ],602 [603 3375,604 4072605 ],606 [607 5923,608 8451609 ],610 [611 4739,612 6715613 ],614 [615 704,616 7207617 ],618 [619 5802,620 10376621 ],622 [623 4432,624 9416625 ],626 [627 6550,628 7795629 ],630 [631 2346,632 9040633 ],634 [635 4265,636 4580637 ],638 [639 999,640 4122641 ],642 [643 937,644 3244645 ],646 [647 73,648 924649 ],650 [651 10525,652 10635653 ],654 [655 5456,656 5952657 ],658 [659 91,660 749661 ],662 [663 4136,664 5109665 ],666 [667 1069,668 8244669 ],670 [671 589,672 5163673 ],674 [675 26,676 10153677 ],678 [679 3265,680 11417681 ],682 [683 5975,684 8210685 ],686 [687 6940,688 10582689 ],690 [691 1990,692 8065693 ],694 [695 1491,696 6432697 ],698 [699 1897,700 5622701 ],702 [703 4378,704 8025705 ],706 [707 1093,708 3353709 ],710 [711 2853,712 10914713 ],714 [715 921,716 4589717 ],718 [719 7148,720 8252721 ],722 [723 3447,724 7866725 ],726 [727 28,728 7166729 ],730 [731 2860,732 4134733 ],734 [735 6215,736 8047737 ],738 [739 1428,740 9466741 ],742 [743 10946,744 11200745 ],746 [747 5246,748 8185749 ],750 [751 5251,752 8529753 ],754 [755 5143,756 9935757 ],758 [759 1751,760 4642761 ],762 [763 1405,764 10421765 ],766 [767 1535,768 9713769 ],770 [771 9470,772 10194773 ],774 [775 633,776 11073777 ],778 [779 4931,780 9463781 ],782 [783 3241,784 9087785 ],786 [787 1058,788 3897789 ],790 [791 6968,792 8442793 ],794 [795 1037,796 9436797 ],798 [799 90,800 6889801 ],802 [803 1308,804 7455805 ],806 [807 3918,808 6296809 ],810 [811 3833,812 10130813 ],814 [815 1987,816 9995817 ],818 [819 4537,820 8031821 ],822 [823 318,824 2552825 ],826 [827 4545,828 6394829 ],830 [831 87,832 175833 ],834 [835 3132,836 4606837 ],838 [839 1544,840 3009841 ],842 [843 4071,844 6511845 ],846 [847 8044,848 8551849 ],850 [851 0,852 930853 ],854 [855 6957,856 10131857 ],858 [859 8103,860 9131861 ],862 [863 2196,864 4103865 ],866 [867 4658,868 7210869 ],870 [871 8071,872 10347873 ],874 [875 9643,876 11411877 ],878 [879 5173,880 7841881 ],882 [883 2101,884 4216885 ],886 [887 757,888 9395889 ],890 [891 2746,892 4920893 ],894 [895 330,896 2912897 ],898 [899 8038,900 11338901 ],902 [903 5196,904 6512905 ],906 [907 5481,908 9125909 ],910 [911 30,912 9066913 ],914 [915 2433,916 3642917 ],918 [919 4797,920 5460921 ],922 [923 659,924 5073925 ],926 [927 7159,928 11369929 ],930 [931 10459,932 10657933 ],934 [935 5044,936 6091937 ],938 [939 7012,940 7155941 ],942 [943 1742,944 5222945 ],946 [947 288,948 6823949 ],950 [951 625,952 9626953 ],954 [955 1233,956 1403957 ],958 [959 281,960 9816961 ],962 [963 7526,964 9096965 ],966 [967 8374,968 10883969 ],970 [971 3300,972 6610973 ],974 [975 2734,976 3755977 ],978 [979 9588,980 10549981 ],982 [983 2849,984 8431985 ],986 [987 1425,988 11372989 ],990 [991 5372,992 8027993 ],994 [995 552,996 11218997 ],998 [999 3700,1000 67021001 ],1002 [1003 1607,1004 93191005 ],1006 [1007 506,1008 78401009 ],1010 [1011 473,1012 54481013 ],1014 [1015 49,1016 34001017 ],1018 [1019 2031,1020 83341021 ],1022 [1023 7913,1024 115851025 ],1026 [1027 3426,1028 38741029 ],1030 [1031 537,1032 63721033 ],1034 [1035 3215,1036 92891037 ],1038 [1039 1431,1040 36161041 ],1042 [1043 7043,1044 94501045 ],1046 [1047 7313,1048 110311049 ],1050 [1051 2803,1052 80321053 ],1054 [1055 695,1056 103411057 ],1058 [1059 10141,1060 112631061 ],1062 [1063 3895,1064 60151065 ],1066 [1067 373,1068 78461069 ],1070 [1071 1434,1072 106801073 ],1074 [1075 1890,1076 114851077 ],1078 [1079 9357,1080 104001081 ],1082 [1083 2242,1084 96581085 ],1086 [1087 3820,1088 41511089 ],1090 [1091 4379,1092 58351093 ],1094 [1095 7276,1096 81161097 ],1098 [1099 932,1100 64971101 ],1102 [1103 4168,1104 112501105 ],1106 [1107 4133,1108 57791109 ],1110 [1111 4370,1112 113841113 ],1114 [1115 2128,1116 104951117 ],1118 [1119 7206,1120 92251121 ],1122 [1123 3412,1124 94021125 ],1126 [1127 2813,1128 83191129 ],1130 [1131 972,1132 77741133 ],1134 [1135 970,1136 111111137 ],1138 [1139 8005,1140 103691141 ],1142 [1143 1040,1144 61881145 ],1146 [1147 8010,1148 107131149 ],1150 [1151 6291,1152 95991153 ],1154 [1155 1602,1156 115531157 ],1158 [1159 9129,1160 105191161 ],1162 [1163 4888,1164 70011165 ],1166 [1167 4275,1168 84641169 ],1170 [1171 37,1172 44631173 ],1174 [1175 570,1176 113421177 ],1178 [1179 1083,1180 55111181 ],1182 [1183 1334,1184 92941185 ],1186 [1187 3108,1188 78631189 ],1190 [1191 10836,1192 112491193 ],1194 [1195 1519,1196 82931197 ],1198 [1199 22,1200 6060