2772. Apply Ops to Make All Array Elements Zero Solution

The problem

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 <= 10⁵
0 <= nums[i] <= 10⁶

Approach overview

Problem Overview: You get an integer array nums and a window size k. One operation subtracts 1 from every element in a subarray of length k. The task is to determine whether a sequence of such operations can reduce every value in the array to exactly zero.

Approach 1: Simplified Operations Tracking with Prefix Sum (O(n) time, O(n) space)

The key observation: when you reach index i, all operations that started earlier and still affect this index must already be accounted for. Track the cumulative number of active operations using a difference array. When the effective value at i (nums[i] - appliedOps) is positive, you must start exactly that many operations at i so the element becomes zero. Record their effect using a difference array so their influence automatically expires after k positions. If i + k exceeds the array length while you still need operations, making the array zero is impossible. This greedy sweep works because delaying an operation would leave the current index non‑zero. The technique relies on prefix accumulation similar to prefix sum or difference arrays and processes the array once.

Approach 2: Segment Tree for Operations Management (O(n log n) time, O(n) space)

A more general simulation uses a segment tree to support range decrement operations and point queries. Iterate from left to right, query the current value at index i, and if it is positive, apply that many range updates over [i, i + k - 1]. The segment tree efficiently propagates lazy updates so each operation runs in O(log n). This approach models the operations explicitly and is useful when constraints require flexible range updates or additional queries. However, it is slower and more complex than the greedy prefix-sum method for this problem.

Recommended for interviews: The greedy difference-array solution is the expected approach. It combines insights from array processing and prefix sum techniques to simulate range operations in constant time per index. A brute-force or segment-tree simulation shows understanding, but the O(n) greedy pass demonstrates strong algorithmic intuition and is typically what interviewers look for.

Approach 1: Simplified Operations Tracking

In this approach, we'll apply a greedy strategy to reduce the operations needed. By treating the decrement operations as intervals and tracking the prefix sum of these intervals, we can minimize the number of decrement operations efficiently.

Essentially, for each element in the array, we determine how many times a decrement operation needs to be applied so that every element becomes zero. By working with cumulative differences, we avoid redundant work and make the decision-making process more efficient.

Python

def can_make_zero(nums, k):
    n = len(nums)
    operations = [0] * (n + 1)
    curr_op = 0

    for i in range(n):
        curr_op -= operations[i]
        nums[i] -= curr_op

        if nums[i] > 0:
            if i + k > n:
                return False
            curr_op += nums[i]
            operations[i + k] += nums[i]
            nums[i] = 0

    return True

# Example Usage:
nums = [2, 2, 3, 1, 1, 0]
k = 3
print(can_make_zero(nums, k))  # Output: True

Java

public boolean canMakeZero(int[] nums, int k) {
    int n = nums.length;
    int[] operations = new int[n + 1];
    int currOp = 0;

    for (int i = 0; i < n; i++) {
        currOp -= operations[i];
        nums[i] -= currOp;

        if (nums[i] > 0) {
          if (i + k > n) return false;
          currOp += nums[i];
          operations[i + k] += nums[i];
          nums[i] = 0;
        }
    }
    return true;
}

// Example Usage:
int[] nums = {2, 2, 3, 1, 1, 0};
int k = 3;
System.out.println(canMakeZero(nums, k));  // Output: true

This Python code uses a simple greedy approach by treating the decrement operation as intervals using a prefix sum technique. We apply operations only when necessary and track when we reverse these operations when they are no longer necessary.

Complexity

Time Complexity: O(n), where n is the number of elements in the array, due to a single pass through the array with constant-time operations. Space Complexity: O(n), for the operations array used to track increment reversals.

Try this approach in the editor

Approach 2: Segment Tree for Operations Management

This approach employs a segment tree to efficiently manage operations over any subarray. By leveraging the segment tree, we can handle range updates and queries in logarithmic time, significantly optimizing performance over naive approaches.

The segment tree allows efficient application of operations to any range and effectively checks if the range operations can make the entire array zero.

C++

#include <vector>

class SegmentTree {
public:
    SegmentTree(int n) : n(n), data(4 * n, 0), lazy(4 * n, 0) {}

    void apply(int l, int r, int value) {
        apply(0, 0, n - 1, l, r, value);
    }

    bool canMakeZero(const std::vector<int>& nums, int k) {
        for (int i = 0; i < n; ++i) {
            int current = query(i, i);
            if (current < nums[i]) {
                int increase = nums[i] - current;
                if (i + k > n) return false;
                apply(i, i + k - 1, increase);
            }
        }
        return true;
    }

private:
    int n;
    std::vector<int> data;
    std::vector<int> lazy;

    void apply(int node, int start, int end, int l, int r, int value) {
        if (lazy[node] != 0) {
            data[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[node * 2 + 1] += lazy[node];
                lazy[node * 2 + 2] += lazy[node];
            }
            lazy[node] = 0;
        }
        if (start > end || start > r || end < l) return;
        if (start >= l && end <= r) {
            data[node] += value * (end - start + 1);
            if (start != end) {
                lazy[node * 2 + 1] += value;
                lazy[node * 2 + 2] += value;
            }
            return;
        }
        int mid = (start + end) / 2;
        apply(node * 2 + 1, start, mid, l, r, value);
        apply(node * 2 + 2, mid + 1, end, l, r, value);
        data[node] = data[node * 2 + 1] + data[node * 2 + 2];
    }

    int query(int l, int r) const {
        return query(0, 0, n - 1, l, r);
    }

    int query(int node, int start, int end, int l, int r) const {
        if (start > end || start > r || end < l) return 0;
        if (lazy[node] != 0) {
            data[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[node * 2 + 1] += lazy[node];
                lazy[node * 2 + 2] += lazy[node];
            }
            lazy[node] = 0;
        }
        if (start >= l && end <= r) return data[node];
        int mid = (start + end) / 2;
        int leftQuery = query(node * 2 + 1, start, mid, l, r);
        int rightQuery = query(node * 2 + 2, mid + 1, end, l, r);
        return leftQuery + rightQuery;
    }
};

// Example Usage:
int main() {
    std::vector<int> nums = {2, 2, 3, 1, 1, 0};
    int k = 3;
    SegmentTree st(nums.size());
    if (st.canMakeZero(nums, k)) {
        std::cout << "true" << std::endl;
    } else {
        std::cout << "false" << std::endl;
    }
    return 0;
}

This C++ solution utilizes a segment tree to manage operations across multiple indices. It checks feasibility by calculating required operations per segment and efficiently applies them using range updates.

Complexity

Time Complexity: O(n log n), Space Complexity: O(n) due to segment tree storage.

Try this approach in the editor

Approach 3: Difference Array + Prefix Sum

First, let's consider the first element of nums, nums[0]:

If nums[0] = 0, we don't need to do anything.
If nums[0] > 0, we need to operate on nums[0..k-1] for nums[0] times, subtracting nums[0] from all elements in nums[0..k-1], so nums[0] becomes 0.

To perform the add and subtract operations on a contiguous segment of elements simultaneously, we can use a difference array to manage these operations. We represent the difference array with d[i], and calculating the prefix sum of the difference array gives us the change of the value at each position.

Therefore, we iterate over nums. For each element nums[i], the current position's change quantity is s = sum_{j=0}^{i} d[j]. We add s to nums[i] to get the actual value of nums[i].

If nums[i] = 0, there's no need for any operation, and we can skip directly.
If nums[i]=0 or i + k > n, it indicates that after the previous operations, nums[i] has become negative, or nums[i..i+k-1] is out of bounds. Therefore, it's impossible to make all elements in nums equal to 0. We return false. Otherwise, we need to subtract nums[i] from all elements in the interval [i..i+k-1]. Therefore, we subtract nums[i] from s and add nums[i] to d[i+k].
We continue to iterate over the next element.

If the iteration ends, it means that all elements in nums can be made equal to 0, so we return true.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

TypeScript

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;
}

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simplified Operations Tracking	Time Complexity: O(n), where n is the number of elements in the array, due to a single pass through the array with constant-time operations. Space Complexity: O(n), for the operations array used to track increment reversals.
Segment Tree for Operations Management	Time Complexity: O(n log n), Space Complexity: O(n) due to segment tree storage.
Difference Array + Prefix Sum	–

Complexity analysis

Approach	Time	Space	When to Use
Simplified Operations Tracking (Difference / Prefix Sum)	O(n)	O(n)	Best general solution. Efficient when range updates always have fixed length k.
Segment Tree for Range Updates	O(n log n)	O(n)	Useful if the problem extends to dynamic queries or variable-length range operations.

Frequently asked questions

Is Apply Operations to Make All Array Elements Equal to Zero easy or hard?

The problem is rated Medium on LeetCode. The difficulty comes from recognizing that repeated subarray operations can be simulated using a prefix-sum difference array rather than performing each operation explicitly.

Apply Operations to Make All Array Elements Equal to Zero Python/Java solution

Most Python and Java solutions implement a greedy sweep with a difference array. Maintain a running count of active operations and update a helper array to mark when those operations expire after k steps. This keeps each index update O(1) and the full algorithm O(n).

How to solve Apply Operations to Make All Array Elements Equal to Zero in O(n)?

Use a difference array to track how many decrement operations are currently active at each index. While iterating, subtract the accumulated operations from nums[i]. If the remaining value is positive, start that many operations at i and mark their ending at i + k. If i + k exceeds the array boundary when operations are needed, the transformation is impossible.

What is the best approach for Apply Operations to Make All Array Elements Equal to Zero?

The most efficient solution uses a greedy difference-array (prefix sum) technique. Traverse the array from left to right while tracking how many operations currently affect each index. If the effective value at index i is positive, start that many operations at i and record their expiration at i + k. This runs in O(n) time with O(n) space.

Is Apply Operations to Make All Array Elements Equal to Zero asked at Google/Amazon/Meta?

Range update and prefix-sum style greedy problems appear frequently in interviews at companies like Google, Amazon, and Meta. This specific problem tests the ability to convert repeated range operations into a linear-time sweep using a difference array.

What data structure is used in Apply Operations to Make All Array Elements Equal to Zero?

The optimal approach relies on arrays with a difference-array or prefix-sum technique to simulate range updates efficiently. Alternative implementations may use a segment tree with lazy propagation to support range decrement operations.

What is the time complexity of Apply Operations to Make All Array Elements Equal to Zero?

The optimal greedy solution runs in O(n) time because the array is scanned once while maintaining a running prefix of active operations. Space complexity is O(n) for the difference array used to track when operations stop affecting future indices.

Apply Operations to Make All Array Elements Equal to Zero solution and explanation

The problem

Approach overview

Approach 1: Simplified Operations Tracking

Approach 2: Segment Tree for Operations Management

Approach 3: Difference Array + Prefix Sum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Apply Operations to Make All Array Elements Equal to Zero solution and explanation

The problem

Approach overview

Approach 1: Simplified Operations Tracking

Approach 2: Segment Tree for Operations Management

Approach 3: Difference Array + Prefix Sum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems