How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Determine Whether Queries Can Zero Array

Q: Determine Whether Queries Can Zero Array

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.

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]])

Expected Output: False

Explanation: Index 0 can be decreased by at most 2 total, but it needs 4. Therefore it is impossible.

Input: ([], [])

Expected Output: True

Explanation: An empty array is already all zeros.

Input: ([5], [[0, 0, 2], [0, 0, 3]])

Expected Output: True

Explanation: The single element receives total decrement capacity 2 + 3 = 5, which is exactly enough.

Input: ([0, 2, 0, 1], [[1, 1, 1], [1, 2, 1]])

Expected Output: False

Explanation: Index 3 is never covered by any query, so it cannot be reduced from 1 to 0.

Input: ([1, 3, 2, 1], [[0, 1, 1], [1, 3, 2], [2, 2, 1]])

Expected Output: True

Explanation: The total capacities are [1, 3, 3, 2], which are each at least the corresponding values [1, 3, 2, 1].

Hints

For each index, you only need to know the total decrement capacity provided by all queries that cover it.
Use a difference array to add `val` to every range `[l, r]` in O(1) per query, then recover per-index totals with a prefix sum.

Quick Overview

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.