Make Array Elements Equal to Zero

Difficulty: Easy | Acceptance: 68.30% | Paid: No Topics: Array, Simulation, Prefix Sum

You are given an integer array nums.

You can perform the following operation any number of times:

Select any index i such that 0 <= i < nums.length and nums[i] > 0, then subtract 1 from nums[i] and subtract 1 from all elements to the right of i (i.e., nums[i+1], nums[i+2], …).

Return the minimum number of operations to make all elements equal to zero.

• Examples
• Constraints
• Greedy Simulation
• Mathematical Optimization

Examples

Example 1

Input:

nums = [1,0,2,0,3]

Output:

2

Explanation: The only possible valid selections are the following:

Choose curr = 3, and a movement direction to the left.

[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,0].

Choose curr = 3, and a movement direction to the right.

[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].

Example 2

Input:

nums = [2,3,4,0,4,1,0]

Output:

0

Explanation: There are no possible valid selections.

Constraints

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Greedy Simulation

Intuition We must zero out elements from left to right. Only operations at index i affect nums[i]. Therefore, to make nums[i] zero, we must perform exactly nums[i] operations at index i, minus any operations already performed on previous indices (which also affect i).

Steps

• Initialize ops to 0 to track the total operations performed so far.
• Iterate through the array from left to right.
• At each index i, calculate the difference diff = nums[i] - ops.
• If diff is negative, it means previous operations have already made nums[i] negative, which is impossible to recover from, so return -1 (or handle as invalid).
• Add diff to ops.
• Return the final ops count.

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        ops = 0
        for i in range(len(nums)):
            diff = nums[i] - ops
            if diff < 0:
                return -1
            ops += diff
        return ops

Complexity

• Time: O(n) — We iterate through the array once.
• Space: O(1) — We only use a few variables for tracking.
• Notes: This approach directly simulates the process and handles edge cases where the array might not be non-decreasing.

Mathematical Optimization

Intuition From the simulation, we observe that ops at index i must equal nums[i]. This implies that the array must be non-decreasing (nums[i] >= nums[i-1]) for a solution to exist. If valid, the total operations required is simply the value of the last element.

Steps

• Iterate through the array to check if it is non-decreasing.
• If nums[i] < nums[i-1] for any i, return -1 (impossible).
• If the loop completes, return nums[nums.length - 1].

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i] < nums[i-1]:
                return -1
        return nums[-1] if nums else 0

Complexity

• Time: O(n) — We traverse the array once to check the order.
• Space: O(1) — No extra space is used.
• Notes: This is the most optimal solution, reducing the problem to a simple monotonicity check.