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 operations `queries`, where each query is of the form `[l, r, val]`.
Process the queries in the given order. For each query `[l, r, val]`, you may independently choose, for every index `j` such that `l <= j <= r`, to decrease `nums[j]` by any integer amount from `0` to `val`, inclusive.
Requirements:
- The chosen decrease for each index in the range may be different.
- After every operation, all values in `nums` must remain non-negative.
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 = [1, 0, 1]`, `queries = [[0, 2, 1]]`
- Output: `true`
- Explanation: In the only query, decrease index `0` by `1`, index `2` by `1`, and leave index `1` unchanged. The array becomes `[0, 0, 0]`.
Quick Answer: This question evaluates competency in array manipulation, range updates, and feasibility under constraints, focusing on reasoning about sequential interval operations and per-index decrement decisions while maintaining non-negativity.
You are given a non-negative integer array `nums` and a list of range operations `queries`, where each query is `[l, r, val]`.
Process the queries in the given order. For each query, and for each index `j` with `l <= j <= r`, you may independently choose an integer decrease from `0` to `val` inclusive and subtract it from `nums[j]`.
The chosen decrease can be different for different indices in the same query. At all times, array values must stay non-negative.
Return `True` if it is possible to make every element of `nums` equal to `0` after all queries are processed. Otherwise, return `False`.
Constraints
- 0 <= len(nums) <= 2 * 10^5
- 0 <= len(queries) <= 2 * 10^5
- 0 <= nums[i] <= 10^9
- 0 <= val <= 10^9
- For each query, 0 <= l <= r < len(nums) when len(nums) > 0
Examples
Input: ([1, 0, 1], [[0, 2, 1]])
Expected Output: True
Explanation: The only query can decrease index 0 by 1, index 2 by 1, and index 1 by 0, producing [0, 0, 0].
Input: ([2, 0, 2], [[0, 1, 1], [1, 2, 1]])
Expected Output: False
Explanation: Index 0 is covered by total capacity 1 and index 2 is covered by total capacity 1, but both need 2.
Input: ([3, 1, 2, 0], [[0, 2, 1], [0, 0, 2], [1, 3, 1]])