Find the First Query Prefix That Can Make an Array Zero

# Find the First Query Prefix That Can Make an Array Zero ### Problem You are given a nonnegative integer array `nums` and a list of queries. Query `[l, r, val]` allows you to decrease each `nums[i]` with `l <= i <= r` by any integer from `0` through `val`, inclusive. Choose the decrease independently for each index. The value `val` is a per-index limit, not a shared total budget for the range. Indices outside the range are unchanged. Return the smallest nonnegative `k` such that processing the first `k` queries in their given order can make every array element exactly zero. If no prefix can do so, return `-1`. You may choose zero decreases, and an initially zero array has answer `0`. ### C++ Interface ```cpp class Solution { public: int minZeroArray(vector<int>& nums, vector<vector<int>>& queries); }; ``` ### Examples #### Example 1 **Input:** `nums = [4,1], queries = [[0,1,2],[0,0,2],[1,1,1]]` **Output:** `2` **Explanation:** The first query can decrease the two indices by `2` and `1`, leaving `[2,0]`. The second query decreases index `0` by `2`, reaching zero. One query cannot suffice because it can decrease index `0` by at most `2`. #### Example 2 **Input:** `nums = [0,0], queries = [[0,1,3]]` **Output:** `0` **Explanation:** The array is already zero, so no queries need to be processed. ### Constraints - `1 <= nums.size() <= 100000` - `0 <= nums[i] <= 500000` - `1 <= queries.size() <= 100000` - Each query has exactly three integers. - `0 <= l <= r < nums.size()` for every query. - `1 <= val <= 5` ### Clarifying Questions - Must all indices in a query receive the same decrease? No, their decreases are independent. - Must the full allowed decrease be used? No, any amount from zero through the limit is allowed. - May queries be reordered or a different subset selected? No. The answer identifies a prefix in the original order. - Is it enough for elements to become nonpositive? No, every final value must equal zero. ### What a Strong Answer Covers - Respects independent per-index decreases and inclusive query ranges. - Establishes when a fixed prefix can make every element exactly zero. - Justifies that the returned prefix length is minimal, or that no prefix works. - Handles initially zero arrays, uncovered positive elements, and the full array/query limits. ### Follow-up Questions - Why can unused capacity be ignored safely? - Which part of the reasoning would fail if each query had one shared budget for its entire range? ```hint Consider one array position For a fixed prefix, add the allowed decreases from all queries covering that index. Because choices are independent, what condition must hold at every index? ``` ```hint Compare prefixes If a prefix works, adding another query cannot remove any available choices. Use this property while evaluating ranges without visiting every covered index separately. ```