TheRealSamuel/LeetCodeProblem
0574
1{2 "id": 3139,3 "name": "subarrays_distinct_element_sum_of_squares_ii",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/subarrays-distinct-element-sum-of-squares-ii/",6 "date": "2023-10-14 00:00:00",7 "task_description": "You are given a **0-indexed **integer array `nums`. The **distinct count** of a subarray of `nums` is defined as: Let `nums[i..j]` be a subarray of `nums` consisting of all the indices from `i` to `j` such that `0 <= i <= j < nums.length`. Then the number of distinct values in `nums[i..j]` is called the distinct count of `nums[i..j]`. Return _the sum of the **squares** of **distinct counts** of all subarrays of _`nums`. Since the answer may be very large, return it **modulo** `109 + 7`. A subarray is a contiguous **non-empty** sequence of elements within an array. **Example 1:** ``` **Input:** nums = [1,2,1] **Output:** 15 **Explanation:** Six possible subarrays are: [1]: 1 distinct value [2]: 1 distinct value [1]: 1 distinct value [1,2]: 2 distinct values [2,1]: 2 distinct values [1,2,1]: 2 distinct values The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 + 22 + 22 + 22 = 15. ``` **Example 2:** ``` **Input:** nums = [2,2] **Output:** 3 **Explanation:** Three possible subarrays are: [2]: 1 distinct value [2]: 1 distinct value [2,2]: 1 distinct value The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 = 3. ``` **Constraints:** `1 <= nums.length <= 105` `1 <= nums[i] <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,2,1]",12 "output": "15 "13 },14 {15 "label": "Example 2",16 "input": "nums = [2,2]",17 "output": "3 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 377024 ],25 "output": 126 },27 {28 "input": [29 6,30 4,31 5,32 9,33 10,34 7,35 3,36 8,37 7,38 539 ],40 "output": 100941 },42 {43 "input": [44 7197,45 68000,46 57766,47 32470,48 27843,49 132,50 73198,51 5653,52 59144,53 94736,54 58950,55 51478,56 40094,57 1299,58 25827,59 5997,60 55473,61 23101,62 99759,63 58270,64 53515,65 21686,66 26057,67 13189,68 53759,69 97844,70 3412,71 95805,72 29310,73 7833,74 44371,75 64917,76 69906,77 95573,78 93640,79 61907,80 87412,81 50451,82 25725,83 52245,84 94855,85 35414,86 91727,87 22922,88 95587,89 55626,90 82404,91 14465,92 63725,93 23444,94 52345,95 55495,96 36576,97 67702,98 34547,99 89354,100 91781,101 79419,102 1596,103 64172,104 15920,105 1802,106 54050,107 64913,108 69554,109 43153,110 34860,111 45455,112 80019,113 64604,114 8231,115 95801,116 98536,117 55403,118 35891,119 99643,120 3617,121 2682,122 49282,123 97214,124 46913,125 73939,126 46810,127 90939,128 35487,129 11725,130 83563,131 83958,132 9146,133 54135,134 51891,135 1627,136 30308,137 4851,138 28800,139 55659,140 57514,141 97659,142 99799,143 67626,144 54295,145 76315,146 48977,147 84155,148 31105,149 96972,150 95654,151 46039,152 71568,153 46394,154 21539,155 56564,156 62726,157 90664,158 75381,159 96289,160 19033,161 84760,162 67524,163 67679,164 25315,165 72759,166 66465,167 4693,168 38568,169 38337,170 94584,171 48303,172 54197,173 72779,174 96767,175 85457,176 76864,177 94543,178 49434,179 2236,180 48023,181 14549,182 63580,183 38516,184 34974,185 16955,186 30712,187 54251,188 46716,189 14911,190 78583,191 76267,192 52971,193 59048,194 80099,195 97221,196 83515,197 77319,198 30482,199 76348,200 51868,201 28011,202 32703,203 61828,204 87233,205 65588,206 40829,207 8405,208 86980,209 42866,210 99858,211 71833,212 36117,213 57432,214 48053,215 69825,216 14160,217 94588,218 16289,219 51514,220 52463,221 91449,222 937,223 44278,224 51623,225 30183,226 37647,227 82712,228 93629,229 20445,230 64018,231 78277,232 83237,233 50815,234 60017,235 94056,236 93570,237 13623,238 16272,239 24085,240 14464,241 72770,242 1616,243 81044,244 67263,245 28785,246 19733,247 11694,248 576,249 33675,250 98430,251 61493,252 2135,253 7856,254 43644,255 62079,256 70443,257 81330,258 79777,259 42319,260 5564,261 23304,262 68511,263 60693,264 23119,265 11050,266 81972,267 69857,268 7859,269 3438,270 19991,271 63143,272 90602,273 77547,274 94635,275 44803,276 46408,277 77475,278 62703,279 38507,280 33409,281 53386,282 15195,283 96272,284 47552,285 63653,286 53407,287 9174,288 51684,289 90716,290 95133,291 57260,292 89061,293 13507,294 89305,295 74222,296 80544,297 95740,298 42873,299 77380,300 95537,301 66081,302 33034,303 20841,304 43074,305 26818,306 96154,307 70102,308 10542,309 12127,310 92440,311 30249,312 4582,313 84212,314 23073,315 57209,316 31642,317 55919,318 20456,319 77356,320 34151,321 61570,322 44179,323 70331,324 2623,325 49368,326 41817,327 16003,328 98304,329 913,330 72811,331 76406,332 1777,333 83199,334 50086,335 29112,336 37897,337 93250,338 93619,339 6205,340 3272,341 73498,342 37904,343 67978,344 68760,345 44436,346 89962,347 17982,348 51723,349 7058,350 54578,351 11482,352 38100,353 17260,354 60539,355 3420,356 18073,357 37032,358 65098,359 81054,360 96059,361 82742,362 38923,363 45915,364 95470,365 71354,366 75789,367 8617,368 25526,369 55388,370 87410,371 35379,372 63885,373 31376,374 46116,375 37061,376 89229,377 12783,378 43674,379 46183,380 93581,381 99246,382 610,383 86640,384 1438,385 48996,386 29392,387 12526,388 21877,389 935,390 56726,391 12698,392 30821,393 12553,394 69518,395 79046,396 64043,397 98613,398 88634,399 86426,400 56878,401 9216,402 44093,403 87745,404 79396,405 92059,406 95687,407 62065,408 54752,409 97583,410 46339,411 47839,412 96870,413 33437,414 92081,415 14811,416 97136,417 59074,418 23280,419 24592,420 73541,421 12304,422 23402,423 29580,424 6862,425 7050,426 27253,427 60658,428 96968,429 39652,430 55108,431 37453,432 40784,433 69424,434 60212,435 91970,436 35882,437 47224,438 87830,439 10959,440 68341,441 54234,442 73614,443 96294,444 13106,445 39442,446 747,447 55828,448 79384,449 13538,450 4900,451 50149,452 49315,453 86385,454 41495,455 68489,456 82336,457 4552,458 22271,459 4930,460 56738,461 37481,462 78952,463 16161,464 20906,465 13579,466 26319,467 18127,468 35343,469 89366,470 85781,471 30250,472 77598,473 20356,474 10504,475 47228,476 64150,477 48483,478 40260,479 26760,480 72607,481 36730,482 92427,483 1237,484 4056,485 4254,486 97451,487 84268,488 55178,489 33515,490 78662,491 48018,492 29383,493 99819,494 4546,495 42501,496 92347,497 37687,498 49183,499 5858,500 73119,501 91830,502 83050,503 6800,504 18094,505 69088,506 97165,507 22874,508 7284,509 62336,510 14840,511 30560,512 95616,513 16851,514 42744,515 92951,516 80274,517 72200,518 1329,519 51409,520 24443,521 22030,522 78796,523 77631,524 92227,525 43413,526 41211,527 20440,528 10516,529 24302,530 30416,531 82461,532 78578,533 80434,534 92044,535 33800,536 8353,537 81376,538 78117,539 46865,540 16007,541 52466,542 31488,543 34770,544 46282,545 82552,546 97204,547 73269,548 87186,549 90294,550 90912,551 43370,552 37952,553 7437,554 49242,555 92196,556 2628,557 41304,558 11077,559 93933,560 27980,561 33623,562 59986,563 38153,564 79725,565 71683,566 24209,567 79772,568 87538,569 13912,570 5176,571 60450,572 98279,573 59263,574 48916,575 331,576 17848,577 66768,578 80609,579 76466,580 13944,581 386,582 31348,583 13580,584 24715,585 86719,586 7883,587 47907,588 11235,589 39571,590 85064,591 68676,592 14104,593 16449,594 86331,595 32425,596 57954,597 97737,598 12359,599 64405,600 18371,601 75292,602 73906,603 90252,604 91376,605 78003,606 15758,607 68597,608 90309,609 96566,610 15779,611 45885,612 59346,613 77183,614 68518,615 87406,616 54990,617 54870,618 1360,619 69258,620 43199,621 26991,622 47820,623 90786,624 76775,625 77717,626 57459,627 92011,628 75926,629 14455,630 10693,631 73279,632 95835,633 2220,634 55296,635 51754,636 38146,637 65800,638 2587,639 75305,640 90353,641 2015,642 47858,643 95282,644 86029,645 86390,646 66762,647 1830,648 58490,649 62514,650 49400,651 98424,652 66983,653 66670,654 79742,655 66588,656 90882,657 6491,658 96284,659 37638,660 96085,661 81352,662 19066,663 13545,664 8001,665 90074,666 65083,667 77707,668 10150,669 61725,670 24154,671 47741,672 22892,673 84648,674 78545,675 95545,676 91712,677 64691,678 65697,679 21798,680 60568,681 14851,682 64430,683 82268,684 36564,685 33316,686 77891,687 64449,688 56619,689 21087,690 24351,691 84204,692 53877,693 13141,694 16831,695 37648,696 24246,697 1667,698 99815,699 93989,700 84817,701 5123,702 12782,703 97354,704 15687,705 50761,706 59482,707 20811,708 97206,709 95538,710 47220,711 59708,712 49888,713 75903,714 46512,715 24494,716 41800,717 95182,718 98497,719 93905,720 80826,721 18308,722 12278,723 56868,724 17417,725 49447,726 60814,727 68343,728 28909,729 79203,730 56280,731 46470,732 42481,733 80760,734 81894,735 33538,736 65595,737 29477,738 57967,739 37934,740 45745,741 28339,742 10758,743 8338,744 25444,745 863,746 77937,747 14420,748 18187,749 3271,750 63943,751 80272,752 82988,753 7930,754 27966,755 24588,756 89368,757 44588,758 27256,759 17238,760 17303,761 23512,762 61249,763 96756,764 81511,765 80190,766 18813,767 38273,768 14655,769 93205,770 69716,771 96832,772 98649,773 4630,774 46167,775 3157,776 87742,777 66800,778 19350,779 59261,780 61333,781 70568,782 82653,783 83668,784 24889,785 9507,786 90075,787 28344,788 3564,789 12898,790 16318,791 82546,792 64134,793 56015,794 3014,795 32741,796 99939,797 24572,798 86053,799 27892,800 48088,801 72240,802 66697,803 40033,804 83580,805 2140,806 31230,807 92122,808 16480,809 92934,810 10340,811 63309,812 5853,813 76845,814 32195,815 60082,816 21872,817 80655,818 19543,819 24160,820 71295,821 12453,822 93317,823 65273,824 49482,825 61949,826 18729,827 74540,828 97773,829 45943,830 55232,831 56255,832 31805,833 57163,834 31547,835 67822,836 89717,837 42820,838 30894,839 657,840 78238,841 70522,842 25288,843 90112,844 55912,845 78318,846 90124,847 98206,848 53695,849 92486,850 22351,851 39940,852 47612,853 50646,854 89737,855 64597,856 88800,857 96442,858 26957,859 45449,860 51434,861 60216,862 53057,863 3344,864 64768,865 48376,866 98636,867 3164,868 99103,869 17011,870 69867,871 41834,872 93888,873 44719,874 86563,875 11167,876 51970,877 3781,878 64946,879 23265,880 65843,881 35127,882 2827,883 19837,884 11403,885 20219,886 7737,887 14736,888 27066,889 7338,890 47794,891 44662,892 70953,893 43877,894 64617,895 18583,896 40254,897 2151,898 55967,899 23986,900 26622,901 77423,902 30672,903 81056,904 8953,905 14542,906 23921,907 98402,908 15856,909 38473,910 14977,911 50310,912 98990,913 87673,914 96218,915 20157,916 96962,917 85570,918 50939,919 23989,920 94728,921 80010,922 14074,923 80840,924 36408,925 35188,926 64023,927 14751,928 57171,929 16353,930 25043,931 97793,932 17960,933 45687,934 44314,935 16492,936 5151,937 57222,938 46205,939 95544,940 77936,941 14709,942 58079,943 44673,944 20858,945 89914,946 29527,947 99660,948 3337,949 25613,950 11898,951 83655,952 19651,953 29526,954 18116,955 43062,956 6240,957 53670,958 27244,959 70924,960 35947,961 21079,962 53932,963 90614,964 35813,965 68238,966 65018,967 56371,968 71526,969 81264,970 90496,971 13655,972 94224,973 63192,974 85679,975 42278,976 67841,977 46515,978 59571,979 59083,980 71334,981 63518,982 147,983 19939,984 48758,985 10389,986 93160,987 55298,988 56187,989 60868,990 43074,991 41718,992 97381,993 32202,994 82092,995 91413,996 2619,997 38635,998 58015,999 9119,1000 7657,1001 46799,1002 66422,1003 77652,1004 27320,1005 225,1006 88650,1007 1065,1008 82556,1009 53726,1010 32945,1011 35862,1012 12358,1013 93922,1014 31993,1015 47387,1016 16306,1017 38627,1018 17833,1019 44677,1020 82407,1021 4365,1022 95235,1023 94132,1024 60204,1025 11457,1026 14978,1027 4861,1028 23534,1029 71821,1030 66041,1031 79443,1032 85473,1033 63129,1034 54006,1035 42737,1036 81219,1037 68826,1038 68525,1039 86522,1040 62741,1041 62325,1042 22324,1043 14893,1044 39293,1045 35823,1046 67088,1047 31303,1048 29190,1049 50613,1050 93815,1051 88560,1052 86232,1053 75212,1054 14403,1055 95632,1056 98381,1057 42281,1058 11778,1059 87434,1060 83741,1061 72786,1062 16632,1063 48644,1064 39042,1065 30424,1066 32357,1067 42377,1068 72174,1069 24817,1070 82088,1071 20971,1072 88026,1073 3994,1074 89675,1075 98158,1076 19261,1077 15351,1078 37242,1079 73166,1080 96758,1081 94623,1082 17166,1083 31038,1084 63235,1085 94355,1086 94240,1087 10647,1088 44983,1089 77911,1090 29649,1091 10021,1092 67844,1093 42067,1094 26376,1095 23043,1096 68029,1097 57035,1098 41095,1099 49052,1100 76023,1101 85161,1102 20649,1103 85885,1104 11512,1105 60098,1106 97495,1107 63419,1108 37747,1109 56518,1110 47831,1111 8411,1112 44021,1113 27100,1114 73637,1115 96852,1116 93694,1117 84360,1118 39584,1119 16286,1120 38283,1121 66605,1122 78534,1123 15937,1124 6958,1125 65412,1126 54092,1127 67558,1128 57636,1129 73225,1130 40849,1131 36795,1132 46780,1133 22599,1134 50253,1135 30217,1136 69738,1137 18051,1138 39892,1139 95022,1140 447,1141 66368,1142 77349,1143 58862,1144 34759,1145 16210,1146 62074,1147 41787,1148 40074,1149 16524,1150 85228,1151 16506,1152 40820,1153 54289,1154 53371,1155 66698,1156 62205,1157 28956,1158 36507,1159 32364,1160 74763,1161 90175,1162 71097,1163 55316,1164 51835,1165 63599,1166 44857,1167 48533,1168 14214,1169 21841,1170 59384,1171 76494,1172 71819,1173 25033,1174 16678,1175 20399,1176 22106,1177 27906,1178 52188,1179 35991,1180 55003,1181 33098,1182 52081,1183 19117,1184 82292,1185 70740,1186 35767,1187 31548,1188 1830,1189 73606,1190 27387,1191 78547,1192 46283,1193 42188,1194 83874,1195 87871,1196 22287,1197 74644,1198 82526,1199 64882,1200 80827,