LeetCode Entry

3355. Zero Array Transformation I

20.05.2025 medium 2025 kotlin rust

Can intersecting intervals decrease an array sweep

3355. Zero Array Transformation I medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/994

Problem TLDR

Can intersecting intervals decrease an array #medium #line_sweep

Intuition

Line sweep trick: store starts and ends of the intervals, then do the line sweep by increasing and decreasing prefix sum.

Approach

• decreasing should be after the end

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

// 22ms
    fun isZeroArray(nums: IntArray, queries: Array<IntArray>): Boolean {
        val d = IntArray(nums.size + 1); var s = 0
        for ((s, e) in queries) { d[s]++; d[e + 1]-- }
        return nums.zip(d).all { (n, d) -> s += d; s >= n }
    }

// 3ms
    fun isZeroArray(nums: IntArray, queries: Array<IntArray>): Boolean {
        val d = IntArray(nums.size + 1); var s = 0
        for ((s, e) in queries) { d[s]++; d[e + 1]-- }
        for ((i, x) in nums.withIndex()) {
            s += d[i]
            if (s < x) return false
        }
        return true
    }

// 5ms
    pub fn is_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> bool {
        let (mut d, mut s) = (vec![0; nums.len() + 1], 0);
        for q in queries { d[q[0] as usize] += 1; d[q[1] as usize + 1] -= 1 }
        nums.iter().zip(d.iter()).all(|(x, d)| { s += d; s >= *x })
    }

// 0ms https://leetcode.com/problems/zero-array-transformation-i/submissions/1638961889
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> d(size(nums) + 1); int s = 0;
        for (auto& q: queries) ++d[q[0]], --d[q[1] + 1];
        for (int i = 0; int x: nums) { s += d[i++]; if (s < x) return 0; }
        return 1;
    }