3355. Zero Array Transformation I

UnknownView on LeetCode

Array Prefix Sum

Time: O(n + q)

Space: O(n)

Intuition

Check if zero array achievable: for each position, decrement by overlap of covering ranges. Difference array.

Algorithm

1Difference array on queries. Prefix sum gives how many times each index is covered.
2Check nums[i] <= coverage[i] for all i.

Common Pitfalls

•Coverage array from range queries using difference array. Each query [l,r] adds 1 to that range.

3355.cs

// Approach: Difference array; apply all query decrements; check all elements reducible to 0.
// Time: O(n + q) Space: O(n)

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

        foreach (var query in queries)
        {
            int l = query[0];
            int r = query[1];
            line[l]++;
            line[r + 1]--;
        }

        for (int i = 0; i < nums.Length; i++)
        {
            decrement += line[i];
            if (decrement < nums[i])
                return false;
        }

        return true;
    }
}

Was this solution helpful?