DDSA Solutions

3356. Zero Array Transformation II

UnknownView on LeetCode
ArrayBinary SearchPrefix Sum

Problem Overview

Find minimum coverage to zero out array.

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems