TheRealSamuel/LeetCodeProblem
0561
1{2 "id": 3809,3 "name": "properties_graph",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/properties-graph/",6 "date": "2025-03-16 00:00:00",7 "task_description": "You are given a 2D integer array `properties` having dimensions `n x m` and an integer `k`. Define a function `intersect(a, b)` that returns the **number of distinct integers** common to both arrays `a` and `b`. Construct an **undirected** graph where each index `i` corresponds to `properties[i]`. There is an edge between node `i` and node `j` if and only if `intersect(properties[i], properties[j]) >= k`, where `i` and `j` are in the range `[0, n - 1]` and `i != j`. Return the number of **connected components** in the resulting graph. **Example 1:** **Input:** properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1 **Output:** 3 **Explanation:** The graph formed has 3 connected components: **Example 2:** **Input:** properties = [[1,2,3],[2,3,4],[4,3,5]], k = 2 **Output:** 1 **Explanation:** The graph formed has 1 connected component: **Example 3:** **Input:** properties = [[1,1],[1,1]], k = 2 **Output:** 2 **Explanation:** `intersect(properties[0], properties[1]) = 1`, which is less than `k`. This means there is no edge between `properties[0]` and `properties[1]` in the graph. **Constraints:** `1 <= n == properties.length <= 100` `1 <= m == properties[i].length <= 100` `1 <= properties[i][j] <= 100` `1 <= k <= m`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1",12 "output": "3 "13 },14 {15 "label": "Example 2",16 "input": "properties = [[1,2,3],[2,3,4],[4,3,5]], k = 2",17 "output": "1 "18 },19 {20 "label": "Example 3",21 "input": "properties = [[1,1],[1,1]], k = 2",22 "output": "2 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 [30 81,31 88,32 9,33 93,34 20,35 64,36 64,37 3,38 15,39 36,40 69,41 70,42 70,43 71,44 72,45 82,46 67,47 2,48 10,49 63,50 99,51 51,52 89,53 23,54 81,55 20,56 63,57 26,58 4,59 43,60 42,61 14,62 100,63 16,64 42,65 39,66 16,67 65,68 82,69 88,70 41,71 24,72 95,73 14,74 84,75 36,76 6,77 3,78 58,79 50,80 74,81 20,82 53,83 70,84 32,85 74,86 20,87 20,88 95,89 22,90 6,91 8,92 97,93 12,94 99,95 19,96 86,97 2,98 3399 ],100 [101 98,102 32,103 75,104 63,105 52,106 84,107 49,108 9,109 64,110 71,111 39,112 55,113 38,114 88,115 63,116 92,117 27,118 64,119 73,120 58,121 26,122 6,123 78,124 44,125 2,126 79,127 44,128 2,129 47,130 6,131 70,132 69,133 26,134 100,135 58,136 57,137 97,138 27,139 2,140 81,141 70,142 93,143 10,144 19,145 27,146 34,147 88,148 25,149 5,150 96,151 62,152 86,153 83,154 92,155 90,156 52,157 67,158 41,159 13,160 32,161 7,162 83,163 99,164 37,165 26,166 39,167 43,168 74,169 77170 ],171 [172 32,173 73,174 96,175 68,176 65,177 61,178 44,179 55,180 2,181 69,182 83,183 86,184 9,185 24,186 57,187 20,188 87,189 70,190 96,191 59,192 46,193 98,194 5,195 92,196 89,197 76,198 58,199 51,200 55,201 63,202 43,203 68,204 46,205 78,206 76,207 27,208 64,209 23,210 11,211 98,212 53,213 97,214 37,215 33,216 28,217 55,218 8,219 19,220 51,221 2,222 54,223 9,224 73,225 19,226 13,227 58,228 64,229 15,230 90,231 94,232 57,233 38,234 55,235 83,236 55,237 1,238 50,239 43,240 46241 ],242 [243 1,244 11,245 20,246 32,247 66,248 77,249 3,250 7,251 49,252 37,253 37,254 23,255 37,256 96,257 90,258 31,259 2,260 15,261 94,262 24,263 32,264 57,265 43,266 72,267 33,268 99,269 48,270 88,271 55,272 56,273 32,274 66,275 82,276 89,277 96,278 100,279 51,280 7,281 80,282 77,283 76,284 26,285 28,286 58,287 64,288 27,289 73,290 44,291 65,292 58,293 78,294 31,295 55,296 6,297 14,298 64,299 21,300 63,301 34,302 76,303 16,304 2,305 22,306 51,307 10,308 26,309 30,310 43,311 32312 ],313 [314 34,315 78,316 80,317 92,318 41,319 90,320 84,321 80,322 55,323 29,324 12,325 21,326 15,327 62,328 53,329 61,330 61,331 14,332 65,333 44,334 92,335 7,336 37,337 77,338 5,339 47,340 25,341 29,342 35,343 42,344 96,345 20,346 62,347 70,348 40,349 38,350 7,351 87,352 21,353 77,354 58,355 60,356 30,357 37,358 66,359 19,360 65,361 66,362 50,363 34,364 51,365 98,366 57,367 68,368 50,369 92,370 57,371 50,372 28,373 40,374 86,375 15,376 92,377 30,378 43,379 66,380 30,381 82,382 74383 ],384 [385 49,386 97,387 29,388 81,389 80,390 3,391 31,392 84,393 23,394 32,395 19,396 52,397 38,398 5,399 62,400 5,401 16,402 11,403 15,404 96,405 81,406 100,407 92,408 85,409 58,410 86,411 31,412 97,413 91,414 98,415 26,416 9,417 42,418 7,419 69,420 20,421 75,422 86,423 29,424 66,425 100,426 5,427 69,428 60,429 52,430 29,431 96,432 36,433 57,434 81,435 15,436 65,437 77,438 17,439 98,440 51,441 49,442 20,443 59,444 12,445 34,446 44,447 5,448 5,449 62,450 39,451 56,452 77,453 56454 ],455 [456 78,457 75,458 41,459 69,460 88,461 62,462 27,463 45,464 54,465 57,466 75,467 27,468 8,469 3,470 85,471 68,472 21,473 78,474 100,475 77,476 12,477 92,478 87,479 11,480 91,481 64,482 29,483 54,484 95,485 4,486 11,487 60,488 54,489 30,490 90,491 56,492 65,493 65,494 100,495 71,496 38,497 64,498 41,499 81,500 70,501 85,502 1,503 34,504 34,505 96,506 86,507 78,508 90,509 43,510 53,511 40,512 60,513 37,514 20,515 56,516 14,517 67,518 28,519 58,520 82,521 73,522 45,523 2,524 68525 ],526 [527 16,528 38,529 22,530 22,531 64,532 53,533 53,534 29,535 33,536 94,537 9,538 9,539 38,540 63,541 98,542 26,543 39,544 75,545 84,546 65,547 97,548 9,549 37,550 9,551 95,552 28,553 55,554 75,555 69,556 81,557 95,558 29,559 32,560 7,561 69,562 35,563 53,564 27,565 34,566 39,567 33,568 26,569 64,570 68,571 46,572 92,573 5,574 61,575 18,576 77,577 49,578 67,579 21,580 9,581 4,582 70,583 93,584 97,585 65,586 84,587 50,588 50,589 64,590 22,591 45,592 45,593 8,594 27,595 61596 ],597 [598 14,599 11,600 65,601 39,602 98,603 58,604 87,605 19,606 100,607 86,608 75,609 27,610 22,611 77,612 27,613 4,614 25,615 68,616 87,617 23,618 65,619 98,620 45,621 78,622 73,623 91,624 21,625 66,626 66,627 5,628 77,629 56,630 76,631 73,632 85,633 27,634 45,635 23,636 81,637 79,638 2,639 71,640 89,641 86,642 82,643 49,644 53,645 25,646 50,647 23,648 55,649 91,650 83,651 15,652 54,653 15,654 51,655 62,656 76,657 37,658 10,659 27,660 10,661 50,662 64,663 49,664 7,665 61,666 83667 ],668 [669 10,670 46,671 18,672 1,673 34,674 53,675 6,676 88,677 12,678 74,679 34,680 95,681 30,682 78,683 27,684 11,685 26,686 85,687 38,688 49,689 6,690 7,691 15,692 64,693 74,694 12,695 55,696 40,697 43,698 81,699 94,700 82,701 85,702 62,703 15,704 95,705 3,706 18,707 11,708 3,709 97,710 95,711 49,712 13,713 81,714 14,715 39,716 3,717 4,718 68,719 18,720 28,721 94,722 51,723 82,724 7,725 86,726 82,727 95,728 48,729 27,730 18,731 40,732 13,733 56,734 6,735 62,736 47,737 100738 ],739 [740 4,741 42,742 100,743 51,744 49,745 5,746 22,747 62,748 62,749 24,750 29,751 8,752 48,753 26,754 99,755 16,756 77,757 83,758 71,759 25,760 73,761 17,762 19,763 33,764 21,765 30,766 82,767 67,768 2,769 1,770 45,771 54,772 72,773 92,774 64,775 44,776 16,777 92,778 70,779 13,780 88,781 26,782 80,783 41,784 31,785 63,786 5,787 2,788 15,789 23,790 78,791 24,792 89,793 83,794 5,795 62,796 87,797 54,798 61,799 71,800 37,801 68,802 91,803 35,804 28,805 96,806 16,807 84,808 20809 ],810 [811 15,812 8,813 13,814 89,815 61,816 93,817 41,818 91,819 33,820 20,821 86,822 85,823 82,824 46,825 84,826 55,827 64,828 20,829 58,830 5,831 57,832 60,833 55,834 64,835 77,836 87,837 53,838 10,839 77,840 56,841 33,842 41,843 40,844 81,845 33,846 70,847 76,848 27,849 65,850 1,851 48,852 65,853 27,854 59,855 10,856 66,857 58,858 25,859 71,860 24,861 19,862 61,863 71,864 83,865 80,866 69,867 7,868 33,869 13,870 10,871 71,872 82,873 79,874 79,875 44,876 2,877 91,878 23,879 44880 ],881 [882 86,883 22,884 44,885 76,886 6,887 38,888 4,889 16,890 45,891 26,892 2,893 70,894 24,895 68,896 100,897 36,898 75,899 81,900 72,901 72,902 81,903 79,904 63,905 8,906 60,907 94,908 27,909 48,910 8,911 84,912 15,913 14,914 80,915 87,916 45,917 86,918 5,919 83,920 64,921 41,922 84,923 85,924 30,925 77,926 64,927 52,928 7,929 84,930 28,931 27,932 53,933 89,934 50,935 85,936 25,937 45,938 97,939 24,940 85,941 18,942 76,943 38,944 81,945 44,946 1,947 58,948 38,949 46,950 59951 ],952 [953 54,954 27,955 73,956 27,957 26,958 80,959 99,960 32,961 24,962 78,963 46,964 16,965 35,966 83,967 76,968 38,969 54,970 34,971 54,972 83,973 22,974 60,975 59,976 11,977 80,978 34,979 42,980 79,981 13,982 25,983 68,984 96,985 91,986 70,987 63,988 55,989 39,990 46,991 65,992 76,993 60,994 97,995 3,996 78,997 38,998 21,999 61,1000 37,1001 49,1002 43,1003 68,1004 3,1005 58,1006 51,1007 21,1008 56,1009 5,1010 5,1011 4,1012 86,1013 94,1014 87,1015 1,1016 56,1017 94,1018 89,1019 85,1020 65,1021 781022 ],1023 [1024 59,1025 36,1026 11,1027 48,1028 68,1029 46,1030 50,1031 84,1032 17,1033 47,1034 7,1035 79,1036 64,1037 77,1038 81,1039 16,1040 33,1041 54,1042 54,1043 28,1044 55,1045 10,1046 82,1047 19,1048 20,1049 11,1050 20,1051 4,1052 32,1053 91,1054 18,1055 32,1056 84,1057 89,1058 13,1059 68,1060 29,1061 49,1062 65,1063 71,1064 68,1065 53,1066 34,1067 32,1068 63,1069 72,1070 62,1071 76,1072 6,1073 70,1074 33,1075 1,1076 84,1077 99,1078 61,1079 70,1080 42,1081 76,1082 34,1083 79,1084 39,1085 63,1086 11,1087 72,1088 54,1089 40,1090 58,1091 76,1092 301093 ],1094 [1095 88,1096 11,1097 53,1098 34,1099 19,1100 22,1101 64,1102 78,1103 16,1104 51,1105 63,1106 5,1107 38,1108 58,1109 71,1110 24,1111 77,1112 97,1113 25,1114 2,1115 38,1116 98,1117 39,1118 15,1119 99,1120 91,1121 48,1122 86,1123 31,1124 80,1125 19,1126 61,1127 39,1128 59,1129 8,1130 82,1131 23,1132 79,1133 11,1134 95,1135 11,1136 68,1137 64,1138 11,1139 84,1140 32,1141 30,1142 46,1143 75,1144 91,1145 75,1146 87,1147 87,1148 75,1149 42,1150 76,1151 35,1152 46,1153 84,1154 6,1155 24,1156 16,1157 21,1158 8,1159 59,1160 88,1161 57,1162 50,1163 741164 ],1165 [1166 74,1167 28,1168 18,1169 9,1170 78,1171 95,1172 56,1173 15,1174 94,1175 47,1176 89,1177 32,1178 54,1179 51,1180 93,1181 55,1182 75,1183 84,1184 15,1185 16,1186 59,1187 90,1188 69,1189 34,1190 26,1191 29,1192 99,1193 3,1194 75,1195 97,1196 42,1197 15,1198 98,1199 19,1200 5,