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

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

Expected Output: True

Explanation: The total available decrease per index is [3, 2, 2, 1], which is enough for [3, 1, 2, 0].

Input: ([], [])

Expected Output: True

Explanation: An empty array is already all zeros.

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

Expected Output: True

Explanation: The first query contributes nothing, the second gives capacity 1 to index 0, and the third gives capacity 2 to index 1, exactly enough.

Input: ([1], [])

Expected Output: False

Explanation: There are no queries, so the value 1 can never be reduced to 0.

Hints

Think about one index at a time: since each index in a query can be decreased independently, what really matters for position `i` is the total decrease capacity from all queries that cover `i`.
You do not need to simulate every query on every element. Use a difference array or sweep-line technique to accumulate how much total capacity each index receives.

Quick Overview

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.