2025-11-10 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

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

November LeetCoding Challenge 10

Description

Minimum Operations to Convert All Elements to Zero

You are given an array nums of size n, consisting of non-negative integers. Your task is to apply some (possibly zero) operations on the array so that all elements become 0.

In one operation, you can select a subarray [i, j] (where 0 <= i <= j < n) and set all occurrences of the minimum non-negative integer in that subarray to 0.

Return the minimum number of operations required to make all elements in the array 0.

 

Example 1:

Input: nums = [0,2]

Output: 1

Explanation:

  • Select the subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0].
  • Thus, the minimum number of operations required is 1.

Example 2:

Input: nums = [3,1,2,1]

Output: 3

Explanation:

  • Select subarray [1,3] (which is [1,2,1]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [3,0,2,0].
  • Select subarray [2,2] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [3,0,0,0].
  • Select subarray [0,0] (which is [3]), where the minimum non-negative integer is 3. Setting all occurrences of 3 to 0 results in [0,0,0,0].
  • Thus, the minimum number of operations required is 3.

Example 3:

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

Output: 4

Explanation:

  • Select subarray [0,5] (which is [1,2,1,2,1,2]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [0,2,0,2,0,2].
  • Select subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,2,0,2].
  • Select subarray [3,3] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,2].
  • Select subarray [5,5] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,0].
  • Thus, the minimum number of operations required is 4.

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 0 <= nums[i] <= 105

Solution

class Solution {
public:
  int minOperations(vector<int>& nums) {
    vector<int> st;
    int answer = 0;
    for(auto n : nums) {
      while(st.size() && st.back() > n) {
        st.pop_back();
      }
      if(st.size() && st.back() == n) continue;
      if(!n) continue;
      st.push_back(n);
      answer += 1;
    }
    return answer;
  }
};

// Accepted
// 968/968 cases passed (27 ms)
// Your runtime beats 80.11 % of cpp submissions
// Your memory usage beats 88.59 % of cpp submissions (221.9 MB)
Algorithm