FPEvalDataset/LeetCodeProblem
0305
1{2 "id": 3289,3 "name": "earliest_second_to_mark_indices_ii",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/earliest-second-to-mark-indices-ii/",6 "date": "2024-02-18 00:00:00",7 "task_description": "You are given two **1-indexed** integer arrays, `nums` and, `changeIndices`, having lengths `n` and `m`, respectively. Initially, all indices in `nums` are unmarked. Your task is to mark **all** indices in `nums`. In each second, `s`, in order from `1` to `m` (**inclusive**), you can perform **one** of the following operations: Choose an index `i` in the range `[1, n]` and **decrement** `nums[i]` by `1`. Set `nums[changeIndices[s]]` to any **non-negative** value. Choose an index `i` in the range `[1, n]`, where `nums[i]` is **equal** to `0`, and **mark** index `i`. Do nothing. Return _an integer denoting the **earliest second** in the range _`[1, m]`_ when **all** indices in _`nums`_ can be marked by choosing operations optimally, or _`-1`_ if it is impossible._ **Example 1:** ``` **Input:** nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3] **Output:** 6 **Explanation:** In this example, we have 7 seconds. The following operations can be performed to mark all indices: Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3]. Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0]. Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0]. Second 4: Mark index 1, since nums[1] is equal to 0. Second 5: Mark index 2, since nums[2] is equal to 0. Second 6: Mark index 3, since nums[3] is equal to 0. Now all indices have been marked. It can be shown that it is not possible to mark all indices earlier than the 6th second. Hence, the answer is 6. ``` **Example 2:** ``` **Input:** nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2] **Output:** 7 **Explanation:** In this example, we have 8 seconds. The following operations can be performed to mark all indices: Second 1: Mark index 1, since nums[1] is equal to 0. Second 2: Mark index 2, since nums[2] is equal to 0. Second 3: Decrement index 4 by one. nums becomes [0,0,1,1]. Second 4: Decrement index 4 by one. nums becomes [0,0,1,0]. Second 5: Decrement index 3 by one. nums becomes [0,0,0,0]. Second 6: Mark index 3, since nums[3] is equal to 0. Second 7: Mark index 4, since nums[4] is equal to 0. Now all indices have been marked. It can be shown that it is not possible to mark all indices earlier than the 7th second. Hence, the answer is 7. ``` **Example 3:** ``` **Input:** nums = [1,2,3], changeIndices = [1,2,3] **Output:** -1 **Explanation: **In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. Hence, the answer is -1. ``` **Constraints:** `1 <= n == nums.length <= 5000` `0 <= nums[i] <= 109` `1 <= m == changeIndices.length <= 5000` `1 <= changeIndices[i] <= n`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]",12 "output": "6 "13 },14 {15 "label": "Example 2",16 "input": "nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]",17 "output": "7 "18 },19 {20 "label": "Example 3",21 "input": "nums = [1,2,3], changeIndices = [1,2,3]",22 "output": "-1 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 65257025,30 981111714,31 153370586,32 280928168,33 161478681,34 36967425,35 87017066,36 489542510,37 89917332,38 753395267,39 41530261,40 699870415,41 280183478,42 769915567,43 730063748,44 891477175,45 934690052,46 109339391,47 54906416,48 494706753,49 554308297,50 717623354,51 705984860,52 312144288,53 882185891,54 131624852,55 397004780,56 383417946,57 562802361,58 403052609,59 350820349,60 538866346,61 842405784,62 702438782,63 358388437,64 615450072,65 464145234,66 145318002,67 749412310,68 795831601,69 127420794,70 360669360,71 316572059,72 761293369,73 513901075,74 627351395,75 356652667,76 581307865,77 247052156,78 104114409,79 488007981,80 13686951,81 959393704,82 747221814,83 562835879,84 684136936,85 953558741,86 663205564,87 513170368,88 149304644,89 187767620,90 104615177,91 849752903,92 717056041,93 787249355,94 78840304,95 948880125,96 887797931,97 968472499,98 483501708,99 139615142,100 282214838,101 44868806,102 557585472,103 309912349,104 88254233,105 570531085,106 461116169,107 809962769,108 787902309,109 386393013,110 434858092,111 484107810,112 427506444,113 529852418,114 414582505,115 787231322,116 781003096,117 543899001,118 311580106,119 107212899,120 344569741,121 885026094,122 86652465,123 43376046,124 321080808,125 943704707,126 867364979,127 765225329,128 150423180,129 952621034,130 131070103,131 313554978,132 797346814,133 675777690,134 435315498,135 824596411,136 796525767,137 101704595,138 857292606,139 714992080,140 777713922,141 79057771,142 8854470,143 787846837,144 338325749,145 438630273,146 139895194,147 68839657,148 423597644,149 157980960,150 447517256,151 525162634,152 327210526,153 804384456,154 134047651,155 63217435,156 324315672,157 970172519,158 655850216,159 716535595,160 813428739,161 815419040,162 877420485,163 321968955,164 534148895,165 9764227,166 228143286,167 140148488,168 574033299,169 951605788,170 871790229,171 468811120,172 876298283,173 410564069,174 683757275,175 365290897,176 358495763,177 388120478,178 251045433,179 267594235,180 679358519,181 931206300,182 462703326,183 202949390,184 760321448,185 323474024,186 823584054,187 65845532,188 736888631,189 463707403,190 981908969,191 470542487,192 504705388,193 578119207,194 294528167,195 771053806,196 883569628,197 599983885,198 134825453,199 114507229,200 953985723,201 100426844,202 402867318,203 448604510,204 578537358,205 282102409,206 22511976,207 885861229,208 60288791,209 493465976,210 545221003,211 642669166,212 466607794,213 968617901,214 218211181,215 878887614,216 344769736,217 356146395,218 820916934,219 6395811,220 322428705,221 508806430,222 388641049,223 339465388,224 576153540,225 63926769,226 93553309,227 296987913,228 599889232,229 832480204,230 99805534,231 679553246,232 647970411,233 123714750,234 528047391,235 601596741,236 529533578,237 435026747,238 911008222,239 274327190,240 250041057,241 235287868,242 746539011,243 14828572,244 14175125,245 174405031,246 33605364,247 452539159,248 191051208,249 175077289,250 23374800,251 639981372,252 675511223,253 155373100,254 620261399,255 726629551,256 486129150,257 206460074,258 287832240,259 523785810,260 428459265,261 882464823,262 321523992,263 904388486,264 697765216,265 568135643,266 954047317,267 933808432,268 752825607,269 511984428,270 97356180,271 143210418,272 276503349,273 973711044,274 556643322,275 85283872,276 801879168,277 853063792,278 99227938,279 552884291,280 582957654,281 436483464,282 906395958,283 610598165,284 394919581,285 18976190,286 135902817,287 867621810,288 148151719,289 391137175,290 768493896,291 421700469,292 115529278,293 841449157,294 979040303,295 259445247,296 362596887,297 843747166,298 420500219,299 399344173,300 173407296,301 437097720,302 896791162,303 869983243,304 263665797,305 19246210,306 223050499,307 729188867,308 204135091,309 401088715,310 232107572,311 178007347,312 782549738,313 792656945,314 519817124,315 685885213,316 584791603,317 428468627,318 722743080,319 257011444,320 503117455,321 411898558,322 515065196,323 406393557,324 113679341,325 726477837,326 662299187,327 107883139,328 888047756,329 686265413,330 290234346,331 639239997,332 450761185,333 320684696,334 733318650,335 811389452,336 499793235,337 297710835,338 224249829,339 770278773,340 639636437,341 170826002,342 14123305,343 869560376,344 527755787,345 294568955,346 972311925,347 169826995,348 109017651,349 43926527,350 379362841,351 793109335,352 636420525,353 792242869,354 717925806,355 95500211,356 862657114,357 16072654,358 334118506,359 646292432,360 629192196,361 432604787,362 555622484,363 282021394,364 759150394,365 272150904,366 61622492,367 793432480,368 106879849,369 344724743,370 303384861,371 330520172,372 852137152,373 66073773,374 594719463,375 205259256,376 312594248,377 756754310,378 927330001,379 390543279,380 328740307,381 6808867,382 814180538,383 761062830,384 228435804,385 829117355,386 415260350,387 35392414,388 819514750,389 8135329,390 81186309,391 967881304,392 873841753,393 617776501,394 281406516,395 280838929,396 221403026,397 785092042,398 462545320,399 256188888,400 246317043,401 677908245,402 295183240,403 977586702,404 496707849,405 772904806,406 246041736,407 931918593,408 451597246,409 969214624,410 202471126,411 366962648,412 575407662,413 962409986,414 797880038,415 29851971,416 369210688,417 818673340,418 408000548,419 461067160,420 53581711,421 802676974,422 602571652,423 165102184,424 61566191,425 569473619,426 609259426,427 377140512,428 992520573,429 343971223,430 747107163,431 408607094,432 506855020,433 757402243,434 863147860,435 721237120,436 693910912,437 652871399,438 846041178,439 631870462,440 600211907,441 304505174,442 729847516,443 704894020,444 573142334,445 885206748,446 312086509,447 154835441,448 75477526,449 793282640,450 390830050,451 203720823,452 523358282,453 50858598,454 853982163,455 457997732,456 630769832,457 127831839,458 491866860,459 258928943,460 253898889,461 128453878,462 974657966,463 188798506,464 880088548,465 591304134,466 720964985,467 195919860,468 300867887,469 172044817,470 801484810,471 862184310,472 893187149,473 778514998,474 845948578,475 831931806,476 704631558,477 883396885,478 281567087,479 675401975,480 565347320,481 469169960,482 181817905,483 992018861,484 603752073,485 572317784,486 276339130,487 491350935,488 120575209,489 475923838,490 543444066,491 159965078,492 82092022,493 344107968,494 589664603,495 129182522,496 83368041,497 816000423,498 471670876,499 817599995,500 923521510,501 876485486,502 152644196,503 484971744,504 142601627,505 28939174,506 338803582,507 205455584,508 54393990,509 433102866,510 421811895,511 722688019,512 922462708,513 642577178,514 288326842,515 236469082,516 226060652,517 282188020,518 171969269,519 575725717,520 931609596,521 358150463,522 21725554,523 812120508,524 748562381,525 977538500,526 359593334,527 860810549,528 491703032,529 398288368,530 593328081,531 963209990,532 918431011,533 785299467,534 570940706,535 159413968,536 754911633,537 376361543,538 115425407,539 151704896,540 614494226,541 970994480,542 988671622,543 311844131,544 190705764,545 125632989,546 787983453,547 512371784,548 603713054,549 426748694,550 623863987,551 198638835,552 600251472,553 790249150,554 833528671,555 519625699,556 542193315,557 771801671,558 105131124,559 965580325,560 262029164,561 871937119,562 477721010,563 579209591,564 760818388,565 684446161,566 713793351,567 849002830,568 454516412,569 837661985,570 382744795,571 146950385,572 636140836,573 224167991,574 63747691,575 342680628,576 845091629,577 802296921,578 996834897,579 570638397,580 346257235,581 580474417,582 654882543,583 823208756,584 509852380,585 909262945,586 753530500,587 414172605,588 999116747,589 96546195,590 41173092,591 323396566,592 967459721,593 521010263,594 178221743,595 88915254,596 582736278,597 970770145,598 870267172,599 530501213,600 547123710,601 829089348,602 149349830,603 215871777,604 413256876,605 829335634,606 27723483,607 962793100,608 114914481,609 404172139,610 297939531,611 41989264,612 885624084,613 603210863,614 379154331,615 458969221,616 787043748,617 193393801,618 426008401,619 773959533,620 837771909,621 228095938,622 862209446,623 256089337,624 477289120,625 742338197,626 239910259,627 893973420,628 249372380,629 126370069,630 772158402,631 825961768,632 322240308,633 677117117,634 836360285,635 73311140,636 793939164,637 281587490,638 502592088,639 393262036,640 866494365,641 105595356,642 228851692,643 959404247,644 577886913,645 601201510,646 713186169,647 364404960,648 598867513,649 601238436,650 770887616,651 423813742,652 323306475,653 488415561,654 775746366,655 239225787,656 483979916,657 237136617,658 478244186,659 932944687,660 904231789,661 905137419,662 648245330,663 796113817,664 307466237,665 448086459,666 284034010,667 252173714,668 588589938,669 899615784,670 339170047,671 320357532,672 464281313,673 393004968,674 423627698,675 11901841,676 356177592,677 329886630,678 262129967,679 560861605,680 634241973,681 110876929,682 331580344,683 242696787,684 579775984,685 668362213,686 637784892,687 824567933,688 869447947,689 890465288,690 137440689,691 875831878,692 733864329,693 801178051,694 757681205,695 331516693,696 616191558,697 681275777,698 333667845,699 465234643,700 865622909,701 655642701,702 173764224,703 176711089,704 483742491,705 799239165,706 187708915,707 113182399,708 781850239,709 576465247,710 535331541,711 197407166,712 152808108,713 704618290,714 572125407,715 669869590,716 953230070,717 147380701,718 761258908,719 736062824,720 386372616,721 42291189,722 787729243,723 964285728,724 883718967,725 866366240,726 181686783,727 178492325,728 678667418,729 294761771,730 793727609,731 141915653,732 214192524,733 728635453,734 775575192,735 951974693,736 624604065,737 380120267,738 411316786,739 169691946,740 42830487,741 200342142,742 25767823,743 402889370,744 870195422,745 895976774,746 891234833,747 489982583,748 772165948,749 814198368,750 838755153,751 195764595,752 441757921,753 970421067,754 520615878,755 634985542,756 933837602,757 749152,758 267857547,759 306678835,760 380853530,761 863456319,762 12973523,763 852966533,764 493174922765 ],766 [767 733,768 546,769 725,770 553,771 735,772 368,773 578,774 483,775 140,776 602,777 346,778 542,779 546,780 24,781 729,782 140,783 42,784 379,785 531,786 82,787 341,788 649,789 511,790 677,791 474,792 669,793 733,794 450,795 317,796 706,797 166,798 166,799 471,800 704,801 124,802 155,803 191,804 697,805 551,806 636,807 567,808 68,809 55,810 171,811 74,812 575,813 353,814 453,815 421,816 53,817 247,818 47,819 510,820 381,821 346,822 634,823 95,824 37,825 695,826 519,827 717,828 393,829 504,830 547,831 636,832 579,833 733,834 72,835 544,836 42,837 172,838 214,839 37,840 290,841 210,842 94,843 247,844 104,845 247,846 707,847 331,848 599,849 601,850 294,851 172,852 210,853 395,854 7,855 470,856 313,857 573,858 253,859 441,860 539,861 197,862 363,863 506,864 104,865 357,866 139,867 249,868 525,869 306,870 449,871 124,872 456,873 79,874 515,875 572,876 635,877 449,878 561,879 211,880 191,881 328,882 7,883 501,884 556,885 475,886 733,887 700,888 300,889 35,890 580,891 608,892 357,893 633,894 225,895 684,896 3,897 83,898 503,899 552,900 230,901 154,902 159,903 606,904 647,905 148,906 620,907 724,908 593,909 12,910 378,911 387,912 290,913 427,914 100,915 342,916 488,917 400,918 299,919 592,920 58,921 214,922 8,923 47,924 192,925 489,926 429,927 526,928 705,929 58,930 487,931 141,932 605,933 81,934 482,935 336,936 620,937 208,938 467,939 609,940 373,941 97,942 53,943 729,944 29,945 56,946 9,947 479,948 509,949 323,950 470,951 286,952 441,953 192,954 79,955 452,956 45,957 353,958 208,959 85,960 715,961 419,962 343,963 4,964 86,965 656,966 234,967 157,968 111,969 216,970 401,971 129,972 522,973 407,974 443,975 261,976 43,977 184,978 730,979 211,980 139,981 613,982 66,983 56,984 353,985 85,986 713,987 545988 ]989 ],990 "output": -1991 },992 {993 "input": [994 [995 744273357,996 91918119,997 272104127,998 455690611,999 620513250,1000 965579861,1001 186906238,1002 42159497,1003 402098607,1004 109442794,1005 200542472,1006 44912740,1007 994352226,1008 280293215,1009 942226211,1010 544491838,1011 685246783,1012 917440575,1013 447039776,1014 934287374,1015 661179884,1016 557288308,1017 768233794,1018 816453384,1019 442267870,1020 191916249,1021 372683530,1022 906571807,1023 91867669,1024 507968576,1025 273054577,1026 368218387,1027 978018100,1028 199771140,1029 575131178,1030 622613842,1031 865091551,1032 616067883,1033 652620208,1034 737945632,1035 688171967,1036 985028102,1037 853898181,1038 126001559,1039 632705628,1040 872102076,1041 566304267,1042 874673960,1043 251398235,1044 299256771,1045 376410877,1046 409755873,1047 726186886,1048 550057381,1049 359779596,1050 665879181,1051 201743855,1052 403018693,1053 52796718,1054 965300839,1055 521983855,1056 959346427,1057 947204404,1058 183351385,1059 174991484,1060 781108269,1061 472257654,1062 502021701,1063 941613704,1064 394526285,1065 994990232,1066 552172863,1067 338854855,1068 822470118,1069 187519836,1070 81376279,1071 333825203,1072 480563609,1073 431500548,1074 398185088,1075 11326236,1076 323166702,1077 307738005,1078 305187821,1079 70817041,1080 550893532,1081 555128084,1082 206815793,1083 990919183,1084 557694973,1085 752534514,1086 625890247,1087 233996612,1088 884814958,1089 477927709,1090 321869429,1091 85011989,1092 928670067,1093 863540674,1094 817741933,1095 401379426,1096 264588597,1097 305321666,1098 52905291,1099 640838040,1100 406090114,1101 63111038,1102 99879744,1103 926477384,1104 927600953,1105 561269300,1106 394210967,1107 602268850,1108 518050600,1109 121498273,1110 136511974,1111 528030119,1112 467600606,1113 404190110,1114 307182492,1115 250421392,1116 692207882,1117 490214700,1118 785972455,1119 441997397,1120 653236121,1121 751583219,1122 952026152,1123 761388808,1124 304340774,1125 305040710,1126 87735675,1127 69442979,1128 107278530,1129 998898308,1130 283097214,1131 38117219,1132 335376681,1133 46360103,1134 573793615,1135 769634773,1136 985941908,1137 763958295,1138 958237144,1139 503924618,1140 454376553,1141 835875502,1142 929173597,1143 654046352,1144 878933624,1145 833443762,1146 735354894,1147 711893915,1148 675368911,1149 449850982,1150 212134838,1151 925271975,1152 933556679,1153 967639900,1154 327579829,1155 690242195,1156 95517614,1157 288717081,1158 355140664,1159 524311049,1160 627740827,1161 800408585,1162 861978072,1163 641689985,1164 540529529,1165 500602789,1166 297590503,1167 527202704,1168 331218622,1169 296713632,1170 938006448,1171 198619768,1172 921996809,1173 53447306,1174 649591568,1175 243443275,1176 368295353,1177 210844152,1178 187722593,1179 248224659,1180 36370079,1181 584077036,1182 211319666,1183 339654060,1184 984535139,1185 798495094,1186 861311165,1187 295004583,1188 627504997,1189 53179497,1190 302793623,1191 687778191,1192 893171922,1193 886663603,1194 311706274,1195 99306605,1196 757451750,1197 411080300,1198 911162183,1199 134812612,1200 519979703,