Practice/Google/Leetcode 2772. Apply Operations to Make All Array Elements Equal to Zero

Leetcode 2772. Apply Operations to Make All Array Elements Equal to Zero

CodingOptional

Problem

You are given an array of non-negative integers nums and a positive integer k. In one operation, you can select any contiguous subarray of exactly length k and subtract 1 from each element in that subarray.

Your task is to determine whether it is possible to reduce all elements in the array to zero by performing these operations any number of times (including zero).

Return true if it's possible to make all array elements equal to zero, otherwise return false.

Requirements

Each operation must target exactly k consecutive elements
You can perform operations in any order and as many times as needed
Elements cannot become negative (implicitly, since we're checking feasibility)
The solution should efficiently determine feasibility without simulating all operations

Constraints

1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 106
1 ≤ k ≤ nums.length
Target time complexity: O(n) where n is the length of nums
Target space complexity: O(1) or O(n)

Examples

Example 1:

` Input: nums = [2, 2, 3, 1, 1, 0], k = 3 Output: true Explanation:

Apply operation on window [0:3]: [2,2,3,1,1,0] → [1,1,2,1,1,0]
Apply operation on window [0:3]: [1,1,2,1,1,0] → [0,0,1,1,1,0]
Apply operation on window [1:4]: [0,0,1,1,1,0] → [0,0,0,0,1,0]
Apply operation on window [2:5]: [0,0,0,0,1,0] → [0,0,0,0,0,0] All elements are zero, so return true. `

Example 2:

Input: nums = [1, 3, 1, 1], k = 2 Output: false Explanation: To zero out index 0, we need 1 operation on window [0:2]. After that operation: [0,2,1,1] To zero out index 1, we need 2 more operations on window [1:3]. After those: [0,0,-1,1] But this would make index 2 negative, which is impossible. The arrangement makes it infeasible to zero everything out.

Example 3:

Input: nums = [4, 3, 2, 1], k = 1 Output: true Explanation: When k=1, we can decrement each element independently until all reach zero.