Zero Array After Queries

Zero Array After Queries

You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order.

Example

Input:

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

Output:

true

Explanation:
We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0].

Best Data Structure for the Job

We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum. It allows efficient range additions and helps track how many times each index is affected by the queries.

Different Approaches

Approach 1: Brute Force

This naive method iterates over every index for every query and performs the decrement operations directly.

class Solution {
    public boolean canTransformToZeroArray(int[] nums, int[][] queries) {
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            for (int i = l; i <= r; i++) {
                if (nums[i] > 0) {
                    nums[i]--;
                }
            }
        }

        for (int num : nums) {
            if (num != 0) return false;
        }

        return true;
    }
}

Why it’s not scalable:
Time complexity becomes O(q * n) in the worst case, which is not efficient for large inputs.

Approach 2: Count Query Coverage (Intermediate)

Rather than decrementing values, this method counts how many times each index is covered by the queries. At the end, we check if each nums[i] can be reduced to zero using the number of times it was covered.

class Solution {
    public boolean canTransformToZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] coverage = new int[n];

        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            for (int i = l; i <= r; i++) {
                coverage[i]++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] > coverage[i]) return false;
        }

        return true;
    }
}

Improvement:
We avoid modifying nums and only count coverage, but it's still O(q * range length), which may not be efficient for wide ranges.

Approach 3: Optimized Using Difference Array and Prefix Sum

This is the most efficient solution. We use a difference array to record how many times each index is affected. Instead of updating the entire range, we update the boundaries of the range and later compute the prefix sum.

class Solution {
    public boolean canTransformToZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];

        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            diff[l]++;
            if (r + 1 < n) {
                diff[r + 1]--;
            }
        }

        int[] prefix = new int[n];
        prefix[0] = diff[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + diff[i];
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] > prefix[i]) {
                return false;
            }
        }

        return true;
    }
}

Why it works:
Each query is processed in constant time, and we only do a single pass for prefix sum and comparison, giving a significant performance boost.

⚠️ Common Mistakes and Pitfalls

  • Modifying the array directly for every query, leading to timeouts.

  • Off-by-one errors in the difference array update (especially at r + 1).

  • Forgetting to compute the prefix sum before checking the results.

  • Not handling edge cases like queries beyond the array bounds properly.

📊 Time and Space Complexity Analysis

Approach      Time Complexity       Space Complexity
Brute Force        O(n * q)        O(1)
Count Coverage per Index        O(n * avg_range)        O(n)
Optimized (Diff + Prefix Sum)        O(n + q)        O(n)

  • n is the length of the input array nums

  • q is the number of queries

🌍 Real-World Applications

  • Inventory systems: Tracking the effect of overlapping orders or shipments.

  • Game development: Applying overlapping buffs or effects over different zones.

  • Resource planning: Determining whether supply meets demand across overlapping requests.

  • Scheduling and calendar systems: Evaluating coverage or conflicts in timeslot ranges.

 

I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Minimum equal sum

Minimum Equal Sum – Matching Arrays with Smart Replacements Problem Statement You are given two integer arrays nums1 and nums2 , which may contain zeros. You must replace each 0 with a strictly positive integer (≥ 1) such that the sum of both arrays becomes equal . Your goal is to minimize that common equal sum after all replacements. If there is no way to make the sums equal with any valid replacements, return -1 . Example Input: nums1 = [ 3 , 2 , 0 , 1 , 0 ] nums2 = [ 6 , 5 , 0 ] Output: 12 Explanation: Replace the two zeros in nums1 with 2 and 4 → [3,2,2,1,4] Replace the zero in nums2 with 1 → [6,5,1] Both arrays now sum to 12 . Best Data Structure for the Job This problem is mostly numerical, so there’s no need for complex data structures like trees or heaps. What you do need is: A way to count zeros and compute current sums. Simple math to determine possible ranges. Long data type to handle large sums. Different Approaches Approach 1: Brute Fo...
Read more