TheRealSamuel/LeetCodeProblem
0561
1{2 "id": 3795,3 "name": "zero_array_transformation_iv",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/zero-array-transformation-iv/",6 "date": "2025-03-09 00:00:00",7 "task_description": "You are given an integer array `nums` of length `n` and a 2D array `queries`, where `queries[i] = [li, ri, vali]`. Each `queries[i]` represents the following action on `nums`: Select a subset of indices in the range `[li, ri]` from `nums`. Decrement the value at each selected index by **exactly** `vali`. A **Zero Array** is an array with all its elements equal to 0. Return the **minimum** possible **non-negative** value of `k`, such that after processing the first `k` queries in **sequence**, `nums` becomes a **Zero Array**. If no such `k` exists, return -1. **Example 1:** **Input:** nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]] **Output:** 2 **Explanation:** **For query 0 (l = 0, r = 2, val = 1):** Decrement the values at indices `[0, 2]` by 1. The array will become `[1, 0, 1]`. **For query 1 (l = 0, r = 2, val = 1):** Decrement the values at indices `[0, 2]` by 1. The array will become `[0, 0, 0]`, which is a Zero Array. Therefore, the minimum value of `k` is 2. **Example 2:** **Input:** nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]] **Output:** -1 **Explanation:** It is impossible to make nums a Zero Array even after all the queries. **Example 3:** **Input:** nums = [1,2,3,2,1], queries = [[0,1,1],[1,2,1],[2,3,2],[3,4,1],[4,4,1]] **Output:** 4 **Explanation:** **For query 0 (l = 0, r = 1, val = 1):** Decrement the values at indices `[0, 1]` by `1`. The array will become `[0, 1, 3, 2, 1]`. **For query 1 (l = 1, r = 2, val = 1):** Decrement the values at indices `[1, 2]` by 1. The array will become `[0, 0, 2, 2, 1]`. **For query 2 (l = 2, r = 3, val = 2):** Decrement the values at indices `[2, 3]` by 2. The array will become `[0, 0, 0, 0, 1]`. **For query 3 (l = 3, r = 4, val = 1):** Decrement the value at index 4 by 1. The array will become `[0, 0, 0, 0, 0]`. Therefore, the minimum value of `k` is 4. **Example 4:** **Input:** nums = [1,2,3,2,6], queries = [[0,1,1],[0,2,1],[1,4,2],[4,4,4],[3,4,1],[4,4,5]] **Output:** 4 **Constraints:** `1 <= nums.length <= 10` `0 <= nums[i] <= 1000` `1 <= queries.length <= 1000` `queries[i] = [li, ri, vali]` `0 <= li <= ri < nums.length` `1 <= vali <= 10`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]",12 "output": "2 "13 },14 {15 "label": "Example 2",16 "input": "nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]",17 "output": "-1 "18 },19 {20 "label": "Example 3",21 "input": "nums = [1,2,3,2,1], queries = [[0,1,1],[1,2,1],[2,3,2],[3,4,1],[4,4,1]]",22 "output": "4 "23 },24 {25 "label": "Example 4",26 "input": "nums = [1,2,3,2,6], queries = [[0,1,1],[0,2,1],[1,4,2],[4,4,4],[3,4,1],[4,4,5]]",27 "output": ""28 }29 ],30 "private_test_cases": [31 {32 "input": [33 [34 904,35 59136 ],37 [38 [39 0,40 1,41 142 ],43 [44 0,45 0,46 247 ],48 [49 0,50 0,51 752 ],53 [54 1,55 1,56 157 ],58 [59 0,60 0,61 262 ],63 [64 1,65 1,66 267 ],68 [69 1,70 1,71 772 ],73 [74 1,75 1,76 477 ],78 [79 1,80 1,81 282 ],83 [84 1,85 1,86 287 ],88 [89 1,90 1,91 292 ],93 [94 0,95 0,96 597 ],98 [99 1,100 1,101 2102 ],103 [104 1,105 1,106 6107 ],108 [109 0,110 1,111 7112 ],113 [114 1,115 1,116 2117 ],118 [119 1,120 1,121 2122 ],123 [124 0,125 0,126 7127 ],128 [129 1,130 1,131 4132 ],133 [134 0,135 0,136 7137 ],138 [139 1,140 1,141 7142 ],143 [144 1,145 1,146 6147 ],148 [149 1,150 1,151 3152 ],153 [154 0,155 1,156 7157 ],158 [159 1,160 1,161 9162 ],163 [164 1,165 1,166 6167 ],168 [169 0,170 1,171 9172 ],173 [174 1,175 1,176 6177 ],178 [179 0,180 1,181 3182 ],183 [184 0,185 1,186 5187 ],188 [189 1,190 1,191 10192 ],193 [194 0,195 0,196 5197 ],198 [199 0,200 1,201 9202 ],203 [204 1,205 1,206 7207 ],208 [209 1,210 1,211 6212 ],213 [214 0,215 0,216 1217 ],218 [219 1,220 1,221 9222 ],223 [224 1,225 1,226 1227 ],228 [229 0,230 1,231 8232 ],233 [234 1,235 1,236 1237 ],238 [239 1,240 1,241 3242 ],243 [244 1,245 1,246 3247 ],248 [249 0,250 0,251 10252 ],253 [254 0,255 1,256 2257 ],258 [259 0,260 0,261 9262 ],263 [264 1,265 1,266 3267 ],268 [269 0,270 0,271 10272 ],273 [274 0,275 1,276 7277 ],278 [279 1,280 1,281 1282 ],283 [284 1,285 1,286 5287 ],288 [289 1,290 1,291 2292 ],293 [294 0,295 0,296 7297 ],298 [299 1,300 1,301 3302 ],303 [304 0,305 0,306 7307 ],308 [309 1,310 1,311 2312 ],313 [314 1,315 1,316 1317 ],318 [319 1,320 1,321 4322 ],323 [324 1,325 1,326 1327 ],328 [329 1,330 1,331 9332 ],333 [334 1,335 1,336 1337 ],338 [339 1,340 1,341 7342 ],343 [344 0,345 0,346 7347 ],348 [349 0,350 1,351 7352 ],353 [354 0,355 1,356 9357 ],358 [359 0,360 1,361 4362 ],363 [364 0,365 0,366 3367 ],368 [369 0,370 0,371 3372 ],373 [374 1,375 1,376 6377 ],378 [379 1,380 1,381 1382 ],383 [384 0,385 0,386 7387 ],388 [389 0,390 1,391 9392 ],393 [394 1,395 1,396 6397 ],398 [399 1,400 1,401 10402 ],403 [404 0,405 0,406 3407 ],408 [409 0,410 1,411 6412 ],413 [414 0,415 0,416 8417 ],418 [419 0,420 1,421 10422 ],423 [424 0,425 1,426 5427 ],428 [429 0,430 0,431 5432 ],433 [434 1,435 1,436 2437 ],438 [439 1,440 1,441 6442 ],443 [444 1,445 1,446 3447 ],448 [449 1,450 1,451 10452 ],453 [454 1,455 1,456 3457 ],458 [459 1,460 1,461 8462 ],463 [464 0,465 0,466 1467 ],468 [469 1,470 1,471 6472 ],473 [474 1,475 1,476 5477 ],478 [479 0,480 1,481 5482 ],483 [484 0,485 1,486 4487 ],488 [489 0,490 0,491 3492 ],493 [494 1,495 1,496 3497 ],498 [499 1,500 1,501 8502 ],503 [504 1,505 1,506 3507 ],508 [509 1,510 1,511 1512 ],513 [514 1,515 1,516 6517 ],518 [519 0,520 0,521 4522 ],523 [524 1,525 1,526 5527 ],528 [529 0,530 0,531 8532 ],533 [534 0,535 0,536 2537 ],538 [539 1,540 1,541 7542 ],543 [544 1,545 1,546 8547 ],548 [549 1,550 1,551 5552 ],553 [554 1,555 1,556 10557 ],558 [559 1,560 1,561 6562 ],563 [564 1,565 1,566 6567 ],568 [569 0,570 1,571 9572 ],573 [574 1,575 1,576 4577 ],578 [579 1,580 1,581 5582 ],583 [584 0,585 0,586 8587 ],588 [589 0,590 1,591 8592 ],593 [594 0,595 0,596 7597 ],598 [599 0,600 1,601 2602 ],603 [604 0,605 0,606 4607 ],608 [609 1,610 1,611 9612 ],613 [614 0,615 0,616 3617 ],618 [619 0,620 1,621 10622 ],623 [624 0,625 1,626 3627 ],628 [629 1,630 1,631 6632 ],633 [634 1,635 1,636 10637 ],638 [639 1,640 1,641 10642 ],643 [644 0,645 1,646 4647 ],648 [649 0,650 0,651 6652 ],653 [654 1,655 1,656 1657 ],658 [659 0,660 1,661 6662 ],663 [664 1,665 1,666 3667 ],668 [669 0,670 0,671 7672 ],673 [674 0,675 0,676 8677 ],678 [679 1,680 1,681 1682 ],683 [684 0,685 1,686 1687 ],688 [689 1,690 1,691 10692 ],693 [694 0,695 0,696 5697 ],698 [699 0,700 1,701 6702 ],703 [704 1,705 1,706 6707 ],708 [709 1,710 1,711 5712 ],713 [714 1,715 1,716 8717 ],718 [719 0,720 1,721 3722 ],723 [724 0,725 1,726 7727 ],728 [729 0,730 0,731 6732 ],733 [734 0,735 0,736 4737 ],738 [739 1,740 1,741 10742 ],743 [744 0,745 0,746 5747 ],748 [749 0,750 0,751 5752 ],753 [754 0,755 1,756 3757 ],758 [759 1,760 1,761 2762 ],763 [764 1,765 1,766 6767 ],768 [769 0,770 1,771 10772 ],773 [774 1,775 1,776 10777 ],778 [779 1,780 1,781 9782 ],783 [784 0,785 1,786 1787 ],788 [789 1,790 1,791 1792 ],793 [794 0,795 1,796 10797 ],798 [799 1,800 1,801 8802 ],803 [804 1,805 1,806 6807 ],808 [809 0,810 1,811 4812 ],813 [814 1,815 1,816 2817 ],818 [819 1,820 1,821 2822 ],823 [824 0,825 1,826 2827 ],828 [829 1,830 1,831 5832 ],833 [834 1,835 1,836 7837 ],838 [839 0,840 1,841 6842 ],843 [844 0,845 0,846 7847 ],848 [849 0,850 1,851 9852 ],853 [854 0,855 0,856 3857 ],858 [859 1,860 1,861 1862 ],863 [864 0,865 0,866 6867 ],868 [869 0,870 0,871 3872 ],873 [874 0,875 0,876 8877 ],878 [879 1,880 1,881 4882 ],883 [884 1,885 1,886 4887 ],888 [889 0,890 0,891 9892 ],893 [894 1,895 1,896 2897 ],898 [899 0,900 1,901 2902 ],903 [904 1,905 1,906 3907 ],908 [909 1,910 1,911 6912 ],913 [914 0,915 0,916 2917 ],918 [919 0,920 0,921 4922 ],923 [924 0,925 1,926 8927 ],928 [929 0,930 1,931 6932 ],933 [934 0,935 0,936 3937 ],938 [939 0,940 1,941 9942 ],943 [944 0,945 1,946 7947 ],948 [949 0,950 1,951 1952 ],953 [954 1,955 1,956 4957 ],958 [959 0,960 0,961 6962 ],963 [964 1,965 1,966 4967 ],968 [969 1,970 1,971 9972 ],973 [974 0,975 1,976 3977 ],978 [979 1,980 1,981 1982 ],983 [984 0,985 0,986 7987 ],988 [989 1,990 1,991 8992 ],993 [994 1,995 1,996 9997 ],998 [999 0,1000 0,1001 91002 ],1003 [1004 1,1005 1,1006 31007 ],1008 [1009 1,1010 1,1011 81012 ],1013 [1014 1,1015 1,1016 81017 ],1018 [1019 1,1020 1,1021 101022 ],1023 [1024 0,1025 0,1026 51027 ],1028 [1029 1,1030 1,1031 81032 ],1033 [1034 1,1035 1,1036 11037 ],1038 [1039 1,1040 1,1041 51042 ],1043 [1044 1,1045 1,1046 21047 ],1048 [1049 0,1050 0,1051 41052 ],1053 [1054 1,1055 1,1056 61057 ],1058 [1059 0,1060 1,1061 81062 ],1063 [1064 1,1065 1,1066 91067 ],1068 [1069 1,1070 1,1071 71072 ],1073 [1074 0,1075 1,1076 51077 ],1078 [1079 0,1080 0,1081 41082 ],1083 [1084 1,1085 1,1086 81087 ],1088 [1089 1,1090 1,1091 31092 ],1093 [1094 1,1095 1,1096 51097 ],1098 [1099 0,1100 0,1101 11102 ],1103 [1104 1,1105 1,1106 21107 ],1108 [1109 1,1110 1,1111 41112 ],1113 [1114 1,1115 1,1116 61117 ],1118 [1119 0,1120 0,1121 51122 ],1123 [1124 1,1125 1,1126 21127 ],1128 [1129 1,1130 1,1131 61132 ],1133 [1134 1,1135 1,1136 101137 ],1138 [1139 0,1140 0,1141 101142 ],1143 [1144 0,1145 1,1146 81147 ],1148 [1149 1,1150 1,1151 71152 ],1153 [1154 0,1155 1,1156 11157 ],1158 [1159 1,1160 1,1161 101162 ],1163 [1164 0,1165 1,1166 11167 ],1168 [1169 0,1170 0,1171 41172 ],1173 [1174 0,1175 1,1176 41177 ],1178 [1179 0,1180 1,1181 51182 ],1183 [1184 0,1185 1,1186 11187 ],1188 [1189 0,1190 0,1191 21192 ],1193 [1194 0,1195 0,1196 81197 ],1198 [1199 1,1200 1,