3356. Zero Array Transformation II

Problem Description

You are given an integer array nums of length n and a 2D array queries where queries[i] = [lᵢ, rᵢ, valᵢ]. Each queries[i] represents the following action on nums:

Decrement the value at each index in the range [lᵢ, rᵢ] in nums by at most valᵢ.
The amount by which each value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Intuition

The main goal is to determine how many queries need to be processed in sequence before the array nums becomes a Zero Array. To achieve this, we need to process each query's operation by decrementing values within specified ranges of the array. However, the catch here is that the decrement amounts are independent for each index and can vary, up to the maximum specified by the query.

The solution leverages an auxiliary array used for efficiently managing range updates. This is done using a difference array that allows us to perform range updates in constant time. For each query processed, the amount to be decremented across specified indices is adjusted in this auxiliary array.

The function check(k) is implemented to determine if after processing k queries, the array can be converted into a Zero Array. This function uses the prefix sum technique over the auxiliary array to verify if after all operations, no element in nums is greater than the cumulative decrement at that position.

The approach employs a binary search over the number of queries to find the minimum number k for which the transformation is possible. This binary search reduces the complexity of evaluating each possible k linearly. If no such k exists, the function returns -1, ensuring that all possibilities are considered but none can satisfy the transformation to a Zero Array.

Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

The solution to this problem involves the following key steps and data structures:

Difference Array Technique: This approach is crucial for performing range updates efficiently. A difference array d is used to accumulate decrement values for a given range specified by each query. This allows us to apply range updates in constant time within a specific index [lᵢ, rᵢ].
Prefix Sum: The difference array d is processed with prefix sums to determine the effective decrement at each index of nums after applying a series of operations.
Binary Search: To find the minimum number k of queries required, we apply binary search on the number of queries. This allows us to iteratively check the minimum subset of queries which can convert the entire nums array to zero.

Detailed Steps:

Initializing the Difference Array: A difference array d of size len(nums) + 1 is created, where each entry is initialized to zero.
Range Updates: For each query, the value to be decremented is added to d[l] and subtracted from d[r + 1]. This marks the start and end of the decrement range for efficient calculation.
Check Function: The function check(k) determines if the first k queries can transform nums into a Zero Array. It accumulates values from the difference array using a prefix sum. For each index in nums, if the number at that index is greater than the cumulative decrement s, then it indicates that these k queries aren't sufficient to convert nums.
Binary Search Execution: The binary search utilizes bisect_left to identify the smallest k that fits the criteria, thereby achieving efficiency over evaluating each individually via a simple loop.

This combined methodology of difference arrays and binary search ensures that the solution is both efficient and scalable for larger inputs, processing range updates and performing binary search operations efficiently as demonstrated in the provided code.

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 consider a simple example to illustrate the solution approach.

Suppose we have an array nums = [3, 4, 5] and queries = [[0, 1, 3], [1, 2, 2], [0, 2, 1]].

Our goal is to determine the minimum number of queries needed to make nums a Zero Array.

Step-by-Step Breakdown:

Initialize the Difference Array:
We create a difference array d of size len(nums) + 1, initialized to zero, i.e., d = [0, 0, 0, 0].
Process Queries with Range Updates:
- Process the first query [0, 1, 3]:
  - Decrement indices from 0 to 1 by at most 3.
  - Update the difference array:
    - Add 3 to d[0] → d[0] = 3.
    - Subtract 3 from d[2] → d[2] = -3.
  - Updated difference array: d = [3, 0, -3, 0].
- Process the second query [1, 2, 2]:
  - Decrement indices from 1 to 2 by at most 2.
  - Update the difference array:
    - Add 2 to d[1] → d[1] = 2.
    - Subtract 2 from d[3] → d[3] = -2.
  - Updated difference array: d = [3, 2, -3, -2].
- Process the third query [0, 2, 1]:
  - Decrement indices from 0 to 2 by at most 1.
  - Update the difference array:
    - Add 1 to d[0] → d[0] = 4.
    - Subtract 1 from d[3] → d[3] = -3.
  - Final difference array: d = [4, 2, -3, -3].
Implement the check(k) Function:

We calculate cumulative decrements for various values of k using the prefix sum of d to see if nums can become a Zero Array.
Binary Search to Determine Minimum k:

Using binary search, check for the smallest k:
- Start with low = 0, high = len(queries).
- Iteratively calculate the prefix sums and compare with nums:
  - If the sum of decrements at each position is sufficient to cover nums, adjust the high bound.
  - Otherwise, adjust the low bound.
For our example, after processing two queries, observe if the prefix sum evaluation ensures all decrements sufficiently cover nums, leading us to decide on the smallest viable k.
Output Result:

The smallest k found through this process represents the minimum number of queries needed. If unable, return -1.

This step-by-step approach efficiently uses the difference array and binary search to solve the problem, illustrating how each query affects nums and helps reach the solution.

Solution Implementation

1from typing import List
2from bisect import bisect_left
3
4class Solution:
5    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
6        # This function checks if it's possible to make the array zero
7        # by applying the first 'k' queries
8        def check(k: int) -> bool:
9            # Initialize a difference array with an extra element for boundary management
10            difference_array = [0] * (len(nums) + 1)
11          
12            # Apply each query's effect to the difference array
13            for left, right, value in queries[:k]:
14                difference_array[left] += value
15                difference_array[right + 1] -= value
16          
17            # Accumulate the changes from the difference array
18            accumulated_sum = 0
19            for original_value, change in zip(nums, difference_array):
20                accumulated_sum += change
21                # Check if the accumulated value can zero out the original array value
22                if original_value > accumulated_sum:
23                    return False
24            return True
25
26        # Determine the number of queries
27        num_queries = len(queries)
28      
29        # Use binary search to find the minimum number of queries needed
30        l = bisect_left(range(num_queries + 1), True, key=check)
31      
32        # Return -1 if not possible, otherwise return the minimum queries needed
33        return -1 if l > num_queries else l
34

1class Solution {
2    private int n; // Store the length of the nums array
3    private int[] nums; // Array of numbers
4    private int[][] queries; // Array of queries, each query is an array of 3 elements
5
6    /**
7     * Method to find the minimum number of queries needed to make all elements in nums non-positive.
8     *
9     * @param nums    The initial array of numbers.
10     * @param queries Array of queries, where each query is represented by [l, r, value].
11     * @return The minimum number of queries required to achieve the desired result, or -1 if not possible.
12     */
13    public int minZeroArray(int[] nums, int[][] queries) {
14        this.nums = nums;
15        this.queries = queries;
16        n = nums.length;
17        int m = queries.length;
18        int left = 0, right = m + 1; // Initialize binary search boundaries
19
20        // Binary search to find the minimal number of queries needed
21        while (left < right) {
22            int mid = (left + right) >> 1; // Calculate the midpoint
23            if (check(mid)) {
24                right = mid; // Try a smaller number of queries if the current middle value works
25            } else {
26                left = mid + 1; // Otherwise, increase the number of queries
27            }
28        }
29        return left > m ? -1 : left; // If 'left' exceeds 'm', it means no solution exists
30    }
31
32    /**
33     * Helper method to check if the first 'k' queries can make all elements in nums[] non-positive.
34     *
35     * @param k The number of queries to consider.
36     * @return true if possible, false otherwise.
37     */
38    private boolean check(int k) {
39        int[] deltaArray = new int[n + 1]; // Array for handling range updates efficiently
40
41        // Apply the first 'k' queries to the deltaArray
42        for (int i = 0; i < k; ++i) {
43            int l = queries[i][0], r = queries[i][1], value = queries[i][2];
44            deltaArray[l] += value;
45            deltaArray[r + 1] -= value;
46        }
47
48        // Calculate the prefix sum and check if nums[i] can be made non-positive
49        for (int i = 0, sum = 0; i < n; ++i) {
50            sum += deltaArray[i]; // Update sum using the delta array
51            if (nums[i] > sum) {
52                return false; // nums[i] cannot be made non-positive
53            }
54        }
55        return true;
56    }
57}
58

1#include <vector>
2#include <cstring> // For using memset
3
4class Solution {
5public:
6    int minZeroArray(std::vector<int>& nums, std::vector<std::vector<int>>& queries) {
7        int n = nums.size();        // Number of elements in 'nums'
8        int d[n + 1];               // Difference array for range updates
9        int m = queries.size();     // Number of queries
10        int left = 0, right = m + 1;
11      
12        // Lambda function to check if the first 'k' queries can make 'nums' zero
13        auto check = [&](int k) -> bool {
14            // Initialize the difference array 'd' with zeros
15            std::memset(d, 0, sizeof(d));
16          
17            // Iterate over the first 'k' queries
18            for (int i = 0; i < k; ++i) {
19                int start = queries[i][0];
20                int end = queries[i][1];
21                int value = queries[i][2];
22              
23                // Apply range increment using difference array
24                d[start] += value;
25                d[end + 1] -= value;
26            }
27
28            // Apply the updates to the array
29            for (int i = 0, sum = 0; i < n; ++i) {
30                sum += d[i];
31                // Check if any position in 'nums' is not zero after applying updates
32                if (nums[i] > sum) {
33                    return false;
34                }
35            }
36          
37            return true;
38        };
39      
40        // Binary search to find the minimum number of queries required
41        while (left < right) {
42            int mid = (left + right) / 2;
43            if (check(mid)) {
44                right = mid; // If valid, try a smaller number of queries
45            } else {
46                left = mid + 1; // If not valid, increase the number of queries
47            }
48        }
49      
50        // Return result, if left > m, it means all queries are needed
51        return left > m ? -1 : left;
52    }
53};
54

1// Function to find the minimum number of queries to make the entire array 'nums' non-negative.
2function minZeroArray(nums: number[], queries: number[][]): number {
3    const n = nums.length; // Length of the nums array
4    const m = queries.length; // Number of queries
5
6    // Array to keep track of differences for applying range updates.
7    const d: number[] = Array(n + 1).fill(0);
8  
9    let l = 0; // Initialize left boundary for binary search
10    let r = m + 1; // Initialize right boundary for binary search
11  
12    // Function to check if first 'k' queries can cover 'nums' by making all its values non-negative.
13    const check = (k: number): boolean => {
14        d.fill(0); // Reset difference array for each check
15
16        // Apply each of the first 'k' queries as a range increment
17        for (let i = 0; i < k; ++i) {
18            const [l, r, val] = queries[i];
19            d[l] += val; // Start increment at index 'l'
20            if (r + 1 < n) {
21                d[r + 1] -= val; // End increment at index 'r + 1', if within bounds
22            }
23        }
24
25        let s = 0; // Sum variable to apply the difference array
26        // Apply the difference array values to 'nums' and check if 'nums' becomes non-negative.
27        for (let i = 0; i < n; ++i) {
28            s += d[i]; // Increment current sum with difference value
29            if (nums[i] > s) {
30                return false; // If any element in 'nums' is still positive, return false
31            }
32        }
33        return true; // Return true if all elements are non-negative
34    };
35
36    // Perform a binary search to find the minimal sufficient number of queries
37    while (l < r) {
38        const mid = (l + r) >> 1; // Find the mid index
39        if (check(mid)) {
40            r = mid; // If mid queries suffice, search in the lower half
41        } else {
42            l = mid + 1; // Else, disregard mid and search in the upper half
43        }
44    }
45
46    return l > m ? -1 : l; // Return -1 if not possible else the minimum queries necessary
47}
48

Time and Space Complexity

The minZeroArray function operates with the following complexities:

Time Complexity:
- The function uses a binary search over the range of query indices, resulting in a time complexity of O(log m), where m is the length of queries.
- Within each step of the binary search, the check function is called:
  - Updating the difference array d takes O(m) in the worst case, as we consider all queries in the range up to k.
  - Iterating through nums for validation involves a time complexity of O(n), where n is the length of nums.
- Thus, the total time complexity is O((m + n) * log m).
Space Complexity:
- The function uses additional space for the difference array d, which is of size len(nums) + 1.
- Therefore, the space complexity is O(n).

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:

Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don’t know