Welcome to Subscribe On Youtube

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

Description

You are given a 0-indexed integer array nums and a positive integer k.

You can apply the following operation on the array any number of times:

  • Choose any subarray of size k from the array and decrease all its elements by 1.

Return true if you can make all the array elements equal to 0, or false otherwise.

A subarray is a contiguous non-empty part of an array.

 

Example 1:

Input: nums = [2,2,3,1,1,0], k = 3
Output: true
Explanation: We can do the following operations:
- Choose the subarray [2,2,3]. The resulting array will be nums = [1,1,2,1,1,0].
- Choose the subarray [2,1,1]. The resulting array will be nums = [1,1,1,0,0,0].
- Choose the subarray [1,1,1]. The resulting array will be nums = [0,0,0,0,0,0].

Example 2:

Input: nums = [1,3,1,1], k = 2
Output: false
Explanation: It is not possible to make all the array elements equal to 0.

 

Constraints:

  • 1 <= k <= nums.length <= 105
  • 0 <= nums[i] <= 106

Solutions

  • class Solution {
        public boolean checkArray(int[] nums, int k) {
            int n = nums.length;
            int[] d = new int[n + 1];
            int s = 0;
            for (int i = 0; i < n; ++i) {
                s += d[i];
                nums[i] += s;
                if (nums[i] == 0) {
                    continue;
                }
                if (nums[i] < 0 || i + k > n) {
                    return false;
                }
                s -= nums[i];
                d[i + k] += nums[i];
            }
            return true;
        }
    }
    
  • class Solution {
    public:
        bool checkArray(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> d(n + 1);
            int s = 0;
            for (int i = 0; i < n; ++i) {
                s += d[i];
                nums[i] += s;
                if (nums[i] == 0) {
                    continue;
                }
                if (nums[i] < 0 || i + k > n) {
                    return false;
                }
                s -= nums[i];
                d[i + k] += nums[i];
            }
            return true;
        }
    };
    
  • class Solution:
        def checkArray(self, nums: List[int], k: int) -> bool:
            n = len(nums)
            d = [0] * (n + 1)
            s = 0
            for i, x in enumerate(nums):
                s += d[i]
                x += s
                if x == 0:
                    continue
                if x < 0 or i + k > n:
                    return False
                s -= x
                d[i + k] += x
            return True
    
    
  • func checkArray(nums []int, k int) bool {
    	n := len(nums)
    	d := make([]int, n+1)
    	s := 0
    	for i, x := range nums {
    		s += d[i]
    		x += s
    		if x == 0 {
    			continue
    		}
    		if x < 0 || i+k > n {
    			return false
    		}
    		s -= x
    		d[i+k] += x
    	}
    	return true
    }
    
  • function checkArray(nums: number[], k: number): boolean {
        const n = nums.length;
        const d: number[] = Array(n + 1).fill(0);
        let s = 0;
        for (let i = 0; i < n; ++i) {
            s += d[i];
            nums[i] += s;
            if (nums[i] === 0) {
                continue;
            }
            if (nums[i] < 0 || i + k > n) {
                return false;
            }
            s -= nums[i];
            d[i + k] += nums[i];
        }
        return true;
    }
    
    

All Problems

All Solutions