Zero Array Transformation IV - Practice Coding Problems

Zero Array Transformation IV - Problem

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

Each queries[i] represents the following action on nums:

Select a subset of indices in the range [l_i, r_i] from nums.
Decrement the value at each selected index by exactly val_i.

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3], queries = [[0,2,1],[1,2,1],[1,1,3]]

› Output: 2

💡 Note: After applying first 2 queries: query [0,2,1] reduces range [0,2] by 1, query [1,2,1] reduces range [1,2] by 1. Total reductions: [1,2,2] which can make [2,1,3] → [0,0,0]

Example 2 — Impossible Case

$ Input: nums = [5,2,4], queries = [[0,1,1],[1,2,1]]

› Output: -1

💡 Note: Even using all queries, maximum reductions are [1,2,1] which cannot reduce [5,2,4] to zero since 1 < 5

Example 3 — Zero Queries Needed

$ Input: nums = [0,0,0], queries = [[0,2,1]]

› Output: 0

💡 Note: Array is already all zeros, so k=0 queries needed

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
queries[i].length = 3
0 ≤ l_i ≤ r_i < nums.length
1 ≤ val_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,1,3] and queries [[0,2,1],[1,2,1],[1,1,3]]

Process

Find minimum k queries to make array all zeros

Output

Return k=2 (first 2 queries sufficient)

Key Takeaway

🎯 Key Insight: Binary search on k combined with difference arrays for efficient feasibility checking

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The optimal approach uses binary search on the answer combined with difference arrays for efficient range updates. For each candidate k, we use a difference array to apply the first k queries in O(n+k) time, then check if the resulting reductions can zero out all elements. Time: O(log q × (n + q)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(log q × n × q)	O(n)	Binary search on k to find minimum queries needed
Brute Force - Try Each k	O(q × n × q)	O(n)	Try each value of k from 0 to queries.length and check if array becomes zero
Optimized Greedy with Difference Array	O(log q × (n + q))	O(n)	Use difference array to efficiently apply range updates and check feasibility

Binary Search on Answer — Algorithm Steps

Binary search on k from 0 to queries.length
For each k, simulate applying first k queries
Use greedy approach to maximize reduction

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

k can be from 0 to queries.length

Check Middle

Test if mid value works

Narrow Range

Eliminate half of search space

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canMakeZero(int* nums, int numsSize, int** queries, int k) {
    int* temp = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        temp[i] = nums[i];
    }
    
    for (int i = 0; i < k; i++) {
        int l = queries[i][0], r = queries[i][1], val = queries[i][2];
        for (int j = l; j <= r; j++) {
            if (temp[j] > 0) {
                temp[j] = temp[j] > val ? temp[j] - val : 0;
            }
        }
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (temp[i] != 0) {
            free(temp);
            return 0;
        }
    }
    
    free(temp);
    return 1;
}

int solution(int* nums, int numsSize, int** queries, int queriesSize) {
    int left = 0, right = queriesSize;
    int result = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canMakeZero(nums, numsSize, queries, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    int nums[] = {2, 1, 3};
    int numsSize = 3;
    
    int query1[] = {0, 2, 1};
    int query2[] = {1, 2, 1};
    int* queries[] = {query1, query2};
    int queriesSize = 2;
    
    printf("%d\n", solution(nums, numsSize, queries, queriesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log q × n × q)

Binary search (log q) iterations, each checking k queries on n elements

⚡ Linearithmic

Space Complexity

O(n)

Temporary array for simulation

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler