Choose the maximum number of allowed range-decrement operations while still being able to turn the whole array into zero.
Problem
You are given an integer array nums and a list of operations queries, where each query describes a subarray range [l, r] that may be used to reduce elements in that range by 1.
You may select any subset of the queries. Each selected query can be applied at most once, and every application decreases every element in its range by 1.
Your goal is to keep enough queries so that after applying the chosen queries, every value in nums can be reduced to exactly 0 without any element going below 0.
Return the maximum number of queries you can remove while still making the array transformable to all zeros. If it is impossible to make the array all zeros, return -1.
Notes
- A query contributes
1decrement to every position in its interval. - Different queries may overlap.
- You may use a query or discard it; each query is independent.
This is the kind of problem where you need to reason about coverage over array positions and keep just enough ranges to satisfy each index.
Input Format
nums: an integer arrayqueries: an array of ranges, where each range is[l, r]and0 <= l <= r < nums.length
Interpret each query as a one-time range decrement by 1.
Output Format
Return an integer: the maximum number of queries that can be removed while still making it possible to reduce every element of nums to 0. If impossible, return -1.
Constraints
1 <= nums.length <= $10^{5}$0 <= nums[i]0 <= queries.length <= $10^{5}$- Each query is a valid inclusive range
- The intended solution should run in near-linear or
O(n log n)time
Example 1
Input
nums = [2,1,1] queries = [[0,1],[0,2],[1,2]]
Output
0
Explanation
All three queries are needed. One possible selection applies [0,1] and [0,2] to cover index 0 twice, and [1,2] plus [0,2] to cover the other indices as needed. Since every query is required, the maximum removable count is 0.
Example 2
Input
nums = [1,1,1] queries = [[0,1],[1,2]]
Output
-1
Explanation
Index 0 is covered only once, index 1 is covered twice, and index 2 is covered only once. However, there is no way to apply the available queries so that every index receives exactly the needed amount to reach zero.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.