3356. Zero Array Transformation II

UnknownView on LeetCode

Array Binary Search Prefix Sum

Intuition

Find minimum coverage to zero out array. Binary search on number of queries used.

Algorithm

1Binary search on k (number of queries). Check feasibility: can first k queries zero the array?

Common Pitfalls

•Binary search: use first k queries, check if coverage suffices everywhere. Difference array for O(n+k) check.

3356.cs

// Approach: Binary search on number of queries used; validate with difference array prefix sum.
// Time: O((n + q) log q) Space: O(n)

public class Solution
{
    public int MinZeroArray(int[] nums, int[][] queries)
    {
        int[] line = new int[nums.Length + 1];
        int decrement = 0;
        int k = 0;

        for (int i = 0; i < nums.Length; ++i)
        {
            while (decrement + line[i] < nums[i])
            {
                if (k == queries.Length)
                    return -1;
                int l = queries[k][0];
                int r = queries[k][1];
                int val = queries[k][2];
                ++k;
                if (r < i)
                    continue;
                line[Math.Max(l, i)] += val;
                line[r + 1] -= val;
            }
            decrement += line[i];
        }

        return k;
    }
}

Was this solution helpful?