3355. Zero Array Transformation I

Problem Description

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [l_i, r_i].

For each queries[i]:

Select a subset of indices within the range [l_i, r_i] in nums.
Decrement the values at the selected indices by 1.

A Zero Array is an array where all elements are equal to 0.

Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

Intuition

The goal is to determine whether we can make all elements of the given array nums zero using the operations described by the queries. We approach this problem using a difference array, which is a useful tool for efficiently performing range updates.

Difference Array Creation:
- We first create an auxiliary array d of length n+1, initialized with zeros. This array helps in managing the range updates.
- For each query [l, r], increment the d[l] by 1 and decrement d[r+1] by 1. This operation marks the start and end of the decrement effect caused by the query operation.
Using Prefix Sum:
- We traverse the difference array d, maintaining a cumulative sum s which gives us the effective number of decrements to apply at each index.
- As we move through each index of nums, we compare the number, nums[i], with the cumulative sum s.
- If at any index nums[i] > s, it indicates that it is impossible to reduce nums[i] to zero because the number of decrements so far (given by s) is insufficient.
- If we are able to perform the necessary decrements for all indices such that all elements become zero, we return true. Otherwise, at the first failure, we return false.

This approach is efficient because the difference array technique allows us to perform query range updates in constant time, and the subsequent single pass through nums and d to check final conditions is linear in time complexity (O(n)).

Learn more about Prefix Sum patterns.

Solution Approach

Solution 1: Difference Array

We implement the solution using the difference array technique:

Initialize the Difference Array:
- Create an auxiliary array d of length n + 1, initialized to zeros: d = [0] * (len(nums) + 1).
Process Each Query:
- For every query [l, r] in queries, update the difference array as follows:
  - Increment the start of the range: d[l] += 1.
  - Decrement the position just after the end of the range: d[r + 1] -= 1.
Calculate the Prefix Sum:
- Iterate through the nums array, maintaining a prefix sum s that accumulates the values from the difference array d.
- For each index i in nums, update s with the current value from d: s += d[i].
Check for Possibility of Zero Array:
- For each element nums[i], check if nums[i] is greater than the accumulated decrements s. If nums[i] > s, immediately return False as it means we can't make nums[i] zero with the decrements available so far.
- If all elements can be decremented to zero using the queries, return True after the iteration.

By leveraging the difference array, the solution efficiently handles the multiple range decrement operations while maintaining constant time updates for each query.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example.

Given:

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

Step-by-step walkthrough:

Initialize the Difference Array:
- Create d = [0, 0, 0, 0, 0] (one extra space for easier boundary management).
Process Each Query:
- For query [0, 1], update d:
  - Increment d[0] += 1 → d = [1, 0, 0, 0, 0]
  - Decrement d[2] -= 1 → d = [1, 0, -1, 0, 0]
- For query [1, 3], update d:
  - Increment d[1] += 1 → d = [1, 1, -1, 0, 0]
  - Decrement d[4] -= 1 → d = [1, 1, -1, 0, -1]
- For query [0, 2], update d:
  - Increment d[0] += 1 → d = [2, 1, -1, 0, -1]
  - Decrement d[3] -= 1 → d = [2, 1, -1, -1, -1]
Calculate the Prefix Sum and Check for Zero Array Possibility:
- Initialize s = 0; iterate through nums:
  - For i = 0, update s += d[0] → s = 2
    - Check if nums[0] <= s (i.e., 3 <= 2) → Fails, return False immediately.

In this case, we determine early that it is not possible to make all elements of nums zero, therefore the function would return False.

This example demonstrates the effectiveness and efficiency of the difference array approach in handling range update operations swiftly and checking the possibility of transforming nums into a zero array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
5        # Initialize a difference array with an extra space for implementation convenience
6        difference_array = [0] * (len(nums) + 1)
7      
8        # Apply range updates using the difference array
9        for left, right in queries:
10            # Increment the left boundary
11            difference_array[left] += 1
12            # Decrement the position after the right boundary
13            difference_array[right + 1] -= 1
14      
15        # Initialize a running sum to apply the range increments
16        running_sum = 0
17
18        # Iterate through each element of the original array along with its corresponding difference
19        for num, delta in zip(nums, difference_array):
20            # Update running sum from the difference array
21            running_sum += delta
22            # Check if the current number in the original array is greater than the running sum
23            if num > running_sum:
24                return False
25      
26        # If all positions are valid, return True indicating the transformation is possible
27        return True
28

1class Solution {
2    public boolean isZeroArray(int[] nums, int[][] queries) {
3        int n = nums.length;
4        int[] differenceArray = new int[n + 1]; // Initialize a difference array with one extra space
5      
6        // Apply the range update technique using the difference array
7        for (int[] query : queries) {
8            int left = query[0];
9            int right = query[1];
10            ++differenceArray[left]; // Increment at the start index for the query
11            --differenceArray[right + 1]; // Decrement right+1 index for the query
12        }
13      
14        int currentSum = 0; // To keep track of accumulated sum/references from difference array
15        for (int i = 0; i < n; ++i) {
16            currentSum += differenceArray[i]; // Update the running sum for current index
17          
18            // If any number in the original array is greater than the current referenced sum, return false
19            if (nums[i] > currentSum) {
20                return false;
21            }
22        }
23      
24        // All indices meet the condition; return true
25        return true;
26    }
27}
28

1#include <vector>
2#include <cstring> // For memset
3
4class Solution {
5public:
6    // Function that determines if an array can be turned into a zero array 
7    // using the given range increment queries.
8    bool isZeroArray(std::vector<int>& nums, std::vector<std::vector<int>>& queries) {
9        int n = nums.size();
10        int differenceArray[n + 1]; // Initialize a difference array of size n + 1
11        std::memset(differenceArray, 0, sizeof(differenceArray)); // Set all elements to 0
12
13        // Apply the range increment operations using the difference array technique
14        for (const auto& query : queries) {
15            int left = query[0], right = query[1];
16            ++differenceArray[left];
17            --differenceArray[right + 1]; // Decrement at right + 1 to end the increment effect
18        }
19
20        // Check if the array after applying all queries can be turned into a zero array
21        int currentSum = 0;
22        for (int i = 0; i < n; ++i) {
23            currentSum += differenceArray[i];
24            if (nums[i] > currentSum) {
25                return false; // Return false if currentSum is less than nums[i]
26            }
27        }
28        return true; // Return true if all conditions are satisfied
29    }
30};
31

1// Function to determine if every element of the array can be made zero by applying a series of operations given in queries
2function isZeroArray(nums: number[], queries: number[][]): boolean {
3    const n = nums.length; // Get the length of the nums array
4  
5    // Initialize a difference array with an extra space, filled with zeros
6    const differenceArray: number[] = Array(n + 1).fill(0);
7  
8    // Apply the queries to the difference array
9    for (const [left, right] of queries) {
10        ++differenceArray[left];
11        --differenceArray[right + 1];
12    }
13
14    let currentSum = 0; // Variable to keep track of the cumulative sum of the difference array
15  
16    // Iterate over 'nums' and check if each element can be zero
17    for (let i = 0; i < n; ++i) {
18        currentSum += differenceArray[i]; // Update the current sum
19        if (nums[i] > currentSum) { // Check if current element in nums is greater than current sum
20            return false; // If yes, return false as it's not possible to make it zero
21        }
22    }
23    return true; // If all elements can be zeroed, return true
24}
25

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the length of the array nums and m is the number of queries. This complexity arises because the algorithm iterates over nums and the queries once. The space complexity is O(n), as it uses an additional array d that is of size n + 1 to keep track of incremental changes due to the queries.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: