LC: 3355: Zero Array Transformation 1

21 May 2025

Intuitions mentioned at the end

Solution 1

func isZeroArray(nums []int, queries [][]int) bool {   

    // [1,2,2,1]
    //[ [1,3],[0,2] ] => diff array [0 0 0 0 0] => [0 1 0 -1 0] => [1 1 -1 -1 0]
    diffArray := make([]int,len(nums)+1)    
    for _,query:= range queries {
        diffArray[query[1]+1]--
        diffArray[query[0]]++
    }

    

    if nums[0] > diffArray[0]{
        return false
    }
    diffPrefixSum := diffArray[0] // sum of decrements 
    for i:=1;i<len(nums);i++{ // can't start from 0 since no prefix Sum for idx 0
        diffPrefixSum+=diffArray[i]
        if nums[i]>diffPrefixSum{
            return false
        }
    }

    return true
}

Solution 2 (trade memory for faster runtime)

func isZeroArray(nums []int, queries [][]int) bool {
    // [1,2,2,1]
    //[ [1,3],[0,2] ] => diff array [0 0 0 0 0] => [0 1 0 -1 0] => [1 1 -1 -1 0]
    diffArray := make([]int,len(nums)+1)    
    for _,query:= range queries {
        diffArray[query[1]+1]--
        diffArray[query[0]]++
    }    

    if nums[0] > diffArray[0]{
        return false
    }

    diffPrefixSum := diffArray[0] // sum of decrements 
    for i:=1;i<len(nums);i++{ // line #21 comment explains why start idx 1
        diffPrefixSum+=diffArray[i] 
        diffArray[i]=diffPrefixSum
    }

    
    for i:=1;i<len(nums);i++{ // can't start from 0 since no prefix Sum for idx 0        
        if nums[i]>diffArray[i]{
            return false
        }
    }

    return true
}

Intuition

intuition 1 – if sum of elements of array < query range sum, should be zero
doesn’t work since, some elements may never fall in range or enough times

intuition 2 – brute force, loop and decrememt, check final array, should not have gt 0
possibly time exceed since nums.length 10^5

intuition 3 – create another array of how much an index should be decremented by calculating query ranges
try O(1) time to poopulate the decrement in a range, rather than looping over a query element

intution 4 – a matrix operation with identity matrix of nums dimension… not clear what operation

intuition 5 – create prefix sum array of nums, sum differences of queries
decrement this sum at r in prefix array, check if any no gt 0
while researching prefix arrays, discovered concept of difference array using sum prefix technique
intuition 3 was close, trick was to “populate decrement array” using prefix sum
each element in this diff array is sum of all previous diffs