Problem of The Day: Simplify Path

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        arr = nums[:]
        for l, r in queries:
            for i in range(l, r + 1):
                if arr[i] > 0:
                    arr[i] -= 1

        return all(x == 0 for x in arr)

Discussion Solution

Must Read to understand difference array. Article

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        N = len(nums)
        diff = [0] * (N + 1)
        prefix = nums[:]
        for l, r in queries:
            diff[l] += 1
            diff[r + 1] -= 1

        curr_sum = 0
        for i in range(N):
            curr_sum += diff[i]
            if nums[i] <= curr_sum:
                nums[i] = 0
            else:
                return False

        return True

Editorial

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        deltaArray = [0] * (len(nums) + 1)
        for left, right in queries:
            deltaArray[left] += 1
            deltaArray[right + 1] -= 1
        operationCounts = []
        currentOperations = 0
        for delta in deltaArray:
            currentOperations += delta
            operationCounts.append(currentOperations)
        for operations, target in zip(operationCounts, nums):
            if operations < target:
                return False
        return True