FastPrepZero Array Transformation I

Zero Array Transformation I

Google logoGoogle● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

You are given an integer array nums and a list of inclusive index ranges queries. Each query has the form [left, right].

Process the queries in order. For each query, you may choose any subset of indices between left and right, inclusive, and decrement the value at every chosen index by 1. You may choose a different subset for every query.

Return true if all values in nums can be made exactly 0 after all queries are processed. Otherwise, return false.

Function

isZeroArray(nums: int[], queries: int[][]) → boolean

Examples

Example 1

nums = [1,0,1]queries = [[0,2]]return = true

The only query covers the whole array. Decrement indices 0 and 2; index 1 is already zero.

Example 2

nums = [4,3,2,1]queries = [[1,3],[0,2]]return = false

Index 0 is covered only once, so its value can decrease from 4 to at best 3. Reaching an all-zero array is impossible.

Constraints

  • 1 <= nums.length <= 10^5.
  • 0 <= nums[i] <= 10^5.
  • 1 <= queries.length <= 10^5.
  • queries[i].length == 2.
  • 0 <= queries[i][0] <= queries[i][1] < nums.length.

More Google problems

See Google hiring insights
public boolean isZeroArray(int[] nums, int[][] queries) {
    // Write your code here.
}
nums[1,0,1]
queries[[0,2]]
expectedtrue
Checking account…