Zero Array Range Decrements
MediumPrefix Sum · Adobe
You are given an integer array nums of length n and a list of queries, where queries[i] = [left_i, right_i] describes an inclusive index range.
Process the queries in order. For each query you may pick any subset of the indices in [left_i, right_i] (possibly none, possibly all) and decrease the value at each picked index by exactly 1.
Return True if it is possible to choose the subsets so that, after all queries are processed, every element of nums is 0. Otherwise return False.
Example 1
- Input:
- nums = [2,1,2], queries = [[0,2],[0,0],[2,2]]
- Output:
- True
- Explanation
- Index 0 is inside two queries ([0,2] and [0,0]), index 1 inside one, index 2 inside two. Each index can drop by at most its coverage, which is exactly 2, 1 and 2, so choosing every index in every query reaches all zeroes.
Example 2
- Input:
- nums = [1,0,2,0], queries = [[0,2],[1,3],[2,2]]
- Output:
- True
- Explanation
- Index 1 and index 3 are covered but need no decrement, so the queries simply leave them out of their chosen subsets. Index 2 is covered three times and only needs 2.
Example 3
- Input:
- nums = [0,3,0], queries = [[0,2],[1,1]]
- Output:
- False
- Explanation
- Index 1 must drop by 3, but only two queries include it, so it can never reach zero.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^51 <= queries.length <= 10^5queries[i].length == 20 <= left_i <= right_i < nums.length