Determine Whether Queries Can Zero Array
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an integer array `nums` of length `n` and a list of range queries `queries`, where each query is of the form `[l, r, val]`.
For a query `[l, r, val]`, you may independently choose a decrement amount for each index `i` in the range `l <= i <= r`, as long as the chosen decrement is between `0` and `val` inclusive. In other words, during this query, every element in the range can be decreased by any amount up to `val`, and different indices may use different decrement amounts.
Apply the queries in the given order. Return `true` if it is possible to make every element of `nums` equal to `0` after processing all queries; otherwise, return `false`.
Example:
- Input: `nums = [2, 0, 2]`, `queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]]`
- Output: `true`
Explanation:
- After the first query, one valid choice is to change `[2, 0, 2]` to `[1, 0, 1]`.
- After the second query, one valid choice is to change `[1, 0, 1]` to `[0, 0, 0]`.
- The remaining query can apply zero decrement everywhere, so the array stays all zeros.
Quick Answer: This question evaluates understanding of range-based array operations and feasibility under bounded per-index decrements, testing skills in interval reasoning, resource allocation across ranges, and constraint propagation.
You are given a non-negative integer array `nums` of length `n` and a list of range queries `queries`, where each query is `[l, r, val]` using 0-based inclusive indices.
For one query `[l, r, val]`, you may choose an integer decrement independently for every index `i` in the range `l <= i <= r`. For each covered index, the chosen decrement can be any value from `0` to `val` inclusive, and different indices may use different decrement amounts.
Apply the queries in the given order. Determine whether there exists some choice of decrements so that, after all queries are processed, every element of `nums` becomes exactly `0`.
Return `True` if it is possible, otherwise return `False`.
Constraints
- 0 <= n <= 2 * 10^5
- 0 <= len(queries) <= 2 * 10^5
- 0 <= nums[i] <= 10^9
- 0 <= val <= 10^9
- If n > 0, then every query satisfies 0 <= l <= r < n
Examples
Input: ([2, 0, 2], [[0, 2, 1], [0, 2, 1], [1, 1, 3]])
Expected Output: True
Explanation: Indices 0 and 2 are covered by two queries of value 1, giving total capacity 2 each. Index 1 already starts at 0. So every index can be reduced to exactly 0.
Input: ([4, 1, 3], [[0, 1, 2], [1, 2, 1]])