2025-05-20 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 20

Description

Zero Array Transformation I

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [li, ri].

For each queries[i]:

  • Select a subset of indices within the range [li, ri] in nums.
  • Decrement the values at the selected indices by 1.

A Zero Array is an array where all elements are equal to 0.

Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

 

Example 1:

Input: nums = [1,0,1], queries = [[0,2]]

Output: true

Explanation:

  • For i = 0: 
    <ul>
	<li>Select the subset of indices as <code>[0, 2]</code> and decrement the values at these indices by 1.</li>
	<li>The array will become <code>[0, 0, 0]</code>, which is a Zero Array.</li>
</ul>
</li>

Example 2:

Input: nums = [4,3,2,1], queries = [[1,3],[0,2]]

Output: false

Explanation:

  • For i = 0: 
    <ul>
	<li>Select the subset of indices as <code>[1, 2, 3]</code> and decrement the values at these indices by 1.</li>
	<li>The array will become <code>[4, 2, 1, 0]</code>.</li>
</ul>
</li>
<li><strong>For i = 1:</strong>
<ul>
	<li>Select the subset of indices as <code>[0, 1, 2]</code> and decrement the values at these indices by 1.</li>
	<li>The array will become <code>[3, 1, 0, 0]</code>, which is not a Zero Array.</li>
</ul>
</li>

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= li <= ri < nums.length

Solution

class Solution {
public:
  bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    int decrement = 0;
    int k = 0;
    vector<int> decrements(nums.size() + 1);
    for(auto &q : queries) {
      decrements[q[0]] += 1;
      decrements[q[1] + 1] -= 1;
    }
    for(int i = 0; i < nums.size(); ++i) {
      decrement += decrements[i];
      if(nums[i] > decrement) return false; 
    }
    return true;
  }
};

// Accepted
// 668/668 cases passed (6 ms)
// Your runtime beats 73.34 % of cpp submissions
// Your memory usage beats 56.99 % of cpp submissions (293 MB)
Algorithm