TheRealSamuel/LeetCodeProblem
0561
1{2 "id": 2888,3 "name": "minimum_index_of_a_valid_split",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/minimum-index-of-a-valid-split/",6 "date": "1688860800000",7 "task_description": "An element `x` of an integer array `arr` of length `m` is **dominant** if **more than half** the elements of `arr` have a value of `x`. You are given a **0-indexed** integer array `nums` of length `n` with one **dominant** element. You can split `nums` at an index `i` into two arrays `nums[0, ..., i]` and `nums[i + 1, ..., n - 1]`, but the split is only **valid** if: `0 <= i < n - 1` `nums[0, ..., i]`, and `nums[i + 1, ..., n - 1]` have the same dominant element. Here, `nums[i, ..., j]` denotes the subarray of `nums` starting at index `i` and ending at index `j`, both ends being inclusive. Particularly, if `j < i` then `nums[i, ..., j]` denotes an empty subarray. Return _the **minimum** index of a **valid split**_. If no valid split exists, return `-1`. **Example 1:** ``` **Input:** nums = [1,2,2,2] **Output:** 2 **Explanation:** We can split the array at index 2 to obtain arrays [1,2,2] and [2]. In array [1,2,2], element 2 is dominant since it occurs twice in the array and 2 * 2 > 3. In array [2], element 2 is dominant since it occurs once in the array and 1 * 2 > 1. Both [1,2,2] and [2] have the same dominant element as nums, so this is a valid split. It can be shown that index 2 is the minimum index of a valid split. ``` **Example 2:** ``` **Input:** nums = [2,1,3,1,1,1,7,1,2,1] **Output:** 4 **Explanation:** We can split the array at index 4 to obtain arrays [2,1,3,1,1] and [1,7,1,2,1]. In array [2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5. In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5. Both [2,1,3,1,1] and [1,7,1,2,1] have the same dominant element as nums, so this is a valid split. It can be shown that index 4 is the minimum index of a valid split. ``` **Example 3:** ``` **Input:** nums = [3,3,3,3,7,2,2] **Output:** -1 **Explanation:** It can be shown that there is no valid split. ``` **Constraints:** `1 <= nums.length <= 105` `1 <= nums[i] <= 109` `nums` has exactly one dominant element.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,2,2,2]",12 "output": "2 "13 },14 {15 "label": "Example 2",16 "input": "nums = [2,1,3,1,1,1,7,1,2,1]",17 "output": "4 "18 },19 {20 "label": "Example 3",21 "input": "nums = [3,3,3,3,7,2,2]",22 "output": "-1 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 536294460,29 536294460,30 536294460,31 91064702,32 424304170,33 434374221,34 536294460,35 536294460,36 536294460,37 536294460,38 536294460,39 536294460,40 536294460,41 271282232,42 830847271,43 536294460,44 536294460,45 272255945,46 926639742,47 244024584,48 536294460,49 452897619,50 536294460,51 536294460,52 536294460,53 275463317,54 536294460,55 536294460,56 536294460,57 536294460,58 722380585,59 536294460,60 536294460,61 536294460,62 603460178,63 482082955,64 536294460,65 536294460,66 536294460,67 468411516,68 147622459,69 536294460,70 896359827,71 28285729,72 536294460,73 904895644,74 536294460,75 536294460,76 786100441,77 149663563,78 501301981,79 536294460,80 536294460,81 616456806,82 536294460,83 341170022,84 122388817,85 103884391,86 258851270,87 536294460,88 180670571,89 536294460,90 536294460,91 536294460,92 536294460,93 939436492,94 838830233,95 536294460,96 536294460,97 712080977,98 536294460,99 998492689,100 626210825,101 536294460,102 536294460,103 478334380,104 536294460,105 228311720,106 688856401,107 790283965,108 704948664,109 735877780,110 402402379,111 313765810,112 877549833,113 619285298,114 536294460,115 512576174,116 536294460,117 536294460,118 302179209,119 536294460,120 536294460,121 536294460,122 345274947,123 17102880,124 632137976,125 802350602,126 536294460,127 536294460,128 536294460,129 118101306,130 536294460,131 687631090,132 536294460,133 619960462,134 536294460,135 200860185,136 536294460,137 316185678,138 611253601,139 780962747,140 536294460,141 321008864,142 747375284,143 761227451,144 536294460,145 536294460,146 536294460,147 536294460,148 536294460,149 536294460,150 536294460,151 536294460,152 536294460,153 536294460,154 108786933,155 536294460,156 536294460,157 536294460,158 253084990,159 631567896,160 643838567,161 462680145,162 536294460,163 536294460,164 536294460,165 820185766,166 536294460,167 536294460,168 489876743,169 663273358,170 536294460,171 536294460,172 536294460,173 539253499,174 886000689,175 536294460,176 536294460,177 536294460,178 536294460,179 536294460,180 536294460,181 198312585,182 536294460,183 556950344,184 417924322,185 131608594,186 536294460,187 536294460,188 394154470,189 536294460,190 536294460,191 917885301,192 536294460,193 911743089,194 601106779,195 177843672,196 536294460,197 536294460,198 449815410,199 755756277,200 536294460,201 965585398,202 868042428,203 536294460,204 536294460,205 536294460,206 236716938,207 536294460,208 536294460,209 22295404,210 536294460,211 621377191,212 147413098,213 54452573,214 536294460,215 536294460,216 536294460,217 536294460,218 536294460,219 536294460,220 505500672,221 536294460,222 536294460,223 536294460,224 536294460,225 571793703,226 464761572,227 208675463,228 536294460,229 536294460,230 536294460,231 112571101,232 602642401,233 506806875,234 787868189,235 658987714,236 101459317,237 536294460,238 536294460,239 536294460,240 582739476,241 873741857,242 536294460,243 536294460,244 753713657,245 775640495,246 536294460,247 64662432,248 536294460,249 536294460,250 565124713,251 406350045,252 189880455,253 753566959,254 536294460,255 536294460,256 536294460,257 499649522,258 887012160,259 536294460,260 679057983,261 536294460,262 536294460,263 289583161,264 536294460,265 587252995,266 299794977,267 536294460,268 291095904,269 485160818,270 536294460,271 536294460,272 238288517,273 536294460,274 536294460,275 536294460,276 320424620,277 10376363,278 536294460,279 536294460,280 536294460,281 206593266,282 536294460,283 481696471,284 536294460,285 536294460,286 243479517,287 536294460,288 536294460,289 536294460,290 536294460,291 60578262,292 211144358,293 536294460,294 536294460,295 267981766,296 536294460,297 592655657,298 536294460,299 841527906,300 403204827,301 536294460,302 536294460,303 160811040,304 824487346,305 536294460,306 786662433,307 536294460,308 536294460,309 259614043,310 470526923,311 747025510,312 536294460,313 536294460,314 305590705,315 672765215,316 739535819,317 664624326,318 82682206,319 629732245,320 536294460,321 631613215,322 725127732,323 451095213,324 536294460,325 536294460,326 536294460,327 755601146,328 408763907,329 830694436,330 186999726,331 277075691,332 591929722,333 680622249,334 168046774,335 536294460,336 536294460,337 536294460,338 536294460,339 666251575,340 536294460,341 878058059,342 149372551,343 420835694,344 706521207,345 639020584,346 230397251,347 536294460,348 536294460,349 536294460,350 72532301,351 171885265,352 851045795,353 450793186,354 253367196,355 819798140,356 785597997,357 562272219,358 536294460,359 197040395,360 60606794,361 613675664,362 536294460,363 536294460,364 536294460,365 536294460,366 536294460,367 536294460,368 536294460,369 536294460,370 536294460,371 536294460,372 172090478,373 739280627,374 415141561,375 536294460,376 536294460,377 551740865,378 725013520,379 45479511,380 536294460,381 536294460,382 12598432,383 536294460,384 170914885,385 536294460,386 858015296,387 31884738,388 35415978,389 866589968,390 278019557,391 536294460,392 264582364,393 536294460,394 578857273,395 536294460,396 936667805,397 536294460,398 536294460,399 626321570,400 536294460,401 989852840,402 449673169,403 894803149,404 536294460,405 536294460,406 536294460,407 536294460,408 536294460,409 86137159,410 519104224,411 536294460,412 584190259,413 536294460,414 536294460,415 536294460,416 536294460,417 536294460,418 869926934,419 740666800,420 536294460,421 507869808,422 536294460,423 312506498,424 260310158,425 898181244,426 536294460,427 536294460,428 536294460,429 123542601,430 597171376,431 536294460,432 536294460,433 536294460,434 659709657,435 314780968,436 536294460,437 576454320,438 536294460,439 536294460,440 334113678,441 63666539,442 536294460,443 25367688,444 9135897,445 293388936,446 670928881,447 170470560,448 536294460,449 536294460,450 536294460,451 536294460,452 536294460,453 536294460,454 617512226,455 536294460,456 536294460,457 536294460,458 536294460,459 536294460,460 691205263,461 536294460,462 661773453,463 536294460,464 467539322,465 461814657,466 536294460,467 61408981,468 536294460,469 536294460,470 536294460,471 153506382,472 536294460,473 536294460,474 536294460,475 536294460,476 544252253,477 364485832,478 536294460,479 536294460,480 536294460,481 536294460,482 536294460,483 536294460,484 536294460,485 266764953,486 791190984,487 348812085,488 536294460,489 536294460,490 327694523,491 536294460,492 536294460,493 536294460,494 536294460,495 536294460,496 536294460,497 536294460,498 536294460,499 536294460,500 630445364,501 495851897,502 789354859,503 192271177,504 503608675,505 781861037,506 536294460,507 536294460,508 536294460,509 700940659,510 12084880,511 765507370,512 536294460,513 664780477,514 536294460,515 536294460,516 548509012,517 536294460,518 865097251,519 879048854,520 536294460,521 946424606,522 536294460,523 511066294,524 536294460,525 958768980,526 656051718,527 165700008,528 536294460,529 536294460,530 123766018,531 195012515,532 536294460,533 154286062,534 259272483,535 536294460,536 377332847,537 62354797,538 536294460,539 70309975,540 536294460,541 961405201,542 871687384,543 454397019,544 667227098,545 536294460,546 361162240,547 536294460,548 963164943,549 536294460,550 536294460,551 468074543,552 193822973,553 589061069,554 627865579,555 523330372,556 421594829,557 162629561,558 127007869,559 831586678,560 536294460,561 505370871,562 536294460,563 536294460,564 536294460,565 312902735,566 536294460,567 102756880,568 659235992,569 156839627,570 536294460,571 917727492,572 536294460,573 536294460,574 266977382,575 613344947,576 536294460,577 856912886,578 600853781,579 536294460,580 536294460,581 715758129,582 978103041,583 536294460,584 407784042,585 536294460,586 536294460,587 536294460,588 536294460,589 524685848,590 994150946,591 522209482,592 727656407,593 536294460,594 593153232,595 536294460,596 536294460,597 536294460,598 151620167,599 65629005,600 536294460,601 676714542,602 536294460,603 652271783,604 867328522,605 598750414,606 531355759,607 807145583,608 536294460,609 536294460,610 702893165,611 475554898,612 194203399,613 536294460,614 516980431,615 304651892,616 536294460,617 536294460,618 536294460,619 655289652,620 288589574,621 864571712,622 348028471,623 536294460,624 536294460,625 154054058,626 536294460,627 460345361,628 226560261,629 301546233,630 536294460,631 346513056,632 477167034,633 536294460,634 938886351,635 536294460,636 536294460,637 536294460,638 645672658,639 536294460,640 536294460,641 536294460,642 536294460,643 921966966,644 536294460,645 536294460,646 536294460,647 536294460,648 536294460,649 536294460,650 536294460,651 132655411,652 500825196,653 179353335,654 536294460,655 536294460,656 536294460,657 536294460,658 536294460,659 536294460,660 871039531,661 84354777,662 955851379,663 536294460,664 778286607,665 449614579,666 707178638,667 876201342,668 91998125,669 536294460,670 356910810,671 818646413,672 536294460,673 978086308,674 823325232,675 536294460,676 536294460,677 536294460,678 536294460,679 536294460,680 758634895,681 389463365,682 472776866,683 536294460,684 478631929,685 536294460,686 588153361,687 298190320,688 536294460,689 949737756,690 420394276,691 243256300,692 536294460,693 536294460,694 112290802,695 27363463,696 536294460,697 446197348,698 536294460,699 779813161,700 536294460,701 536294460,702 536294460,703 536294460,704 64960262,705 536294460,706 645487814,707 997337902,708 536294460,709 536294460,710 536294460,711 343268271,712 536294460,713 536294460,714 536294460,715 536294460,716 536294460,717 170384147,718 536294460,719 536294460,720 1488445,721 536294460,722 683360186,723 161489762,724 536294460,725 841047543,726 971645573,727 536294460,728 536294460,729 536294460,730 536294460,731 536294460,732 536294460,733 663611319,734 646453324,735 536294460,736 536294460,737 536294460,738 536294460,739 536294460,740 185654142,741 536294460,742 536294460,743 483598105,744 80558601,745 405558913,746 93587628,747 536294460,748 458430697,749 131791265,750 944051598,751 451254300,752 536294460,753 798584897,754 641133905,755 607717735,756 536294460,757 536294460,758 536294460,759 536294460,760 499185026,761 536294460,762 536294460,763 91192932,764 489004334,765 202433752,766 536294460,767 536294460,768 536294460,769 523025052,770 536294460,771 255857813,772 536294460,773 185729820,774 719734375,775 368903227,776 536294460,777 52704538,778 601094161,779 309153177,780 829907807,781 536294460,782 536294460,783 816316257,784 193130315,785 536294460,786 536294460,787 536294460,788 536294460,789 536294460,790 677545919,791 251241284,792 808182746,793 536294460,794 536294460,795 80891881,796 536294460,797 536294460,798 536294460,799 952098248,800 207871922,801 536294460,802 536294460,803 536294460,804 654613163,805 536294460,806 536294460,807 536294460,808 536294460,809 536294460,810 536294460,811 536294460,812 536294460,813 536294460,814 340445876,815 834379157,816 379461722,817 359212710,818 769530442,819 536294460,820 195574741,821 553585870,822 536294460,823 536294460,824 536294460,825 786427549,826 536294460,827 889628305,828 536294460,829 536294460,830 261166031,831 536294460,832 267138183,833 315499404,834 536294460,835 536294460,836 20310352,837 266078682,838 133374409,839 306620706,840 176547165,841 536294460,842 536294460,843 536294460,844 213709727,845 973201639,846 536294460,847 536294460,848 37800203,849 536294460,850 791873054,851 176916064,852 28294225,853 536294460,854 117706673,855 536294460,856 966031797,857 890420913,858 477571796,859 536294460,860 536294460,861 536294460,862 189310974,863 536294460,864 497415779,865 536294460,866 191005867,867 870334281,868 471770961,869 536294460,870 536294460,871 500728287,872 536294460,873 536294460,874 7742424,875 536294460,876 452784536,877 508217916,878 536294460,879 536294460,880 308222421,881 721749150,882 536294460,883 536294460,884 554128107,885 536294460,886 209071324,887 458741689,888 267996354,889 536294460,890 25277690,891 536294460,892 934933572,893 536294460,894 536294460,895 479686452,896 536294460,897 536294460,898 536294460,899 66298214,900 536294460,901 536294460,902 536294460,903 536294460,904 734151893,905 536294460,906 484429962,907 536294460,908 57012165,909 848058813,910 671615192,911 536294460,912 334759619,913 602414338,914 70086725,915 536294460,916 536294460,917 536294460,918 164960840,919 536294460,920 536294460,921 3505108,922 449609919,923 536294460,924 228756857,925 34957618,926 558155859,927 534995746,928 536294460,929 282545400,930 594771091,931 536294460,932 536294460,933 536294460,934 64994654,935 332177082,936 536294460,937 536294460,938 536294460,939 536294460,940 536294460,941 398998976,942 536294460,943 434611335,944 536294460,945 36244730,946 536294460,947 536294460,948 657418216,949 345493460,950 536294460,951 536294460,952 794979360,953 700121451,954 536294460,955 519553750,956 541635551,957 536294460,958 536294460,959 536294460,960 335577260,961 536294460,962 85835902,963 536294460,964 153525555,965 763760525,966 19215315,967 115289812,968 526149430,969 761017062,970 226024082,971 536294460,972 536294460,973 727926060,974 223113069,975 536294460,976 427735537,977 536294460,978 536294460,979 536294460,980 536294460,981 624567767,982 34990482,983 690457786,984 875208056,985 536294460,986 547996638,987 536294460,988 536294460,989 792815282,990 536294460,991 536294460,992 203566695,993 536294460,994 536294460,995 536294460,996 577868259,997 935390730,998 536294460,999 394385645,1000 536294460,1001 536294460,1002 581896788,1003 536294460,1004 153037910,1005 536294460,1006 536294460,1007 108131603,1008 369126210,1009 765035358,1010 536294460,1011 536294460,1012 536294460,1013 536294460,1014 536294460,1015 736498877,1016 439064588,1017 406677306,1018 831506170,1019 105037475,1020 536294460,1021 47697048,1022 340530652,1023 14003977,1024 536294460,1025 536294460,1026 456179387,1027 536294460,1028 536294460,1029 143509201,1030 536294460,1031 20309429,1032 399839714,1033 536294460,1034 536294460,1035 191546150,1036 536294460,1037 536294460,1038 536294460,1039 536294460,1040 536294460,1041 720781260,1042 536294460,1043 536294460,1044 536294460,1045 984926742,1046 728924582,1047 536294460,1048 120801700,1049 536294460,1050 605554399,1051 393414437,1052 536294460,1053 291113962,1054 794627868,1055 536294460,1056 536294460,1057 416655961,1058 536294460,1059 749511371,1060 820350038,1061 919591129,1062 291117884,1063 918657933,1064 899412032,1065 536294460,1066 536294460,1067 536294460,1068 725675179,1069 516452832,1070 536294460,1071 922437290,1072 405244088,1073 536294460,1074 536294460,1075 536294460,1076 536294460,1077 536294460,1078 536294460,1079 417283224,1080 536294460,1081 536294460,1082 342482701,1083 536294460,1084 536294460,1085 536294460,1086 536294460,1087 54878389,1088 536294460,1089 536294460,1090 536294460,1091 536294460,1092 536294460,1093 536294460,1094 536294460,1095 626925401,1096 776173363,1097 536294460,1098 827132283,1099 578121884,1100 536294460,1101 536294460,1102 536294460,1103 536294460,1104 536294460,1105 536294460,1106 267873830,1107 536294460,1108 519615713,1109 245878166,1110 536294460,1111 536294460,1112 596445805,1113 559864555,1114 536294460,1115 145007120,1116 82535630,1117 536294460,1118 204460436,1119 536294460,1120 305174277,1121 536294460,1122 238065477,1123 750764051,1124 536294460,1125 536294460,1126 536294460,1127 721939955,1128 536294460,1129 536294460,1130 536294460,1131 944533802,1132 536294460,1133 393741456,1134 786876711,1135 724177550,1136 883494828,1137 426743675,1138 536294460,1139 593721110,1140 536294460,1141 7388601,1142 219913586,1143 536294460,1144 536294460,1145 720604544,1146 536294460,1147 917722874,1148 536294460,1149 536294460,1150 536294460,1151 536294460,1152 260104241,1153 536294460,1154 544722630,1155 536294460,1156 536294460,1157 622968634,1158 434876973,1159 536294460,1160 536294460,1161 437963860,1162 806759938,1163 451394630,1164 536294460,1165 692395771,1166 147014085,1167 536294460,1168 536294460,1169 754319562,1170 536294460,1171 288885798,1172 536294460,1173 536294460,1174 450383897,1175 49262116,1176 536294460,1177 536294460,1178 737420028,1179 912582319,1180 536294460,1181 558998956,1182 72035591,1183 536294460,1184 29286967,1185 90410462,1186 69092541,1187 536294460,1188 242416709,1189 536294460,1190 104204916,1191 536294460,1192 536294460,1193 221102624,1194 12822887,1195 135995608,1196 629409362,1197 536294460,1198 536294460,1199 536294460,1200 536294460,