Minimum Operations to Convert All Elements to Zero

Minimum Operations to Convert All Elements to Zero - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: Operation 1: Remove minimum 1 from subarray [2,1,3,4] → [2,0,3,4]. Operation 2: Remove minimum 2 → [0,0,3,4]. Operation 3: Remove minimum 3 → [0,0,0,4]. Operation 4: Remove minimum 4 → [0,0,0,0]. Total: 4 operations, but optimal strategy gives 5.

Example 2 — All Same Elements

$ Input: nums = [3,3,3]

› Output: 3

💡 Note: Each element requires exactly 1 operation since they're all the same value. Total: 3 operations.

Example 3 — Already Zero

$ Input: nums = [0,0,0]

› Output: 0

💡 Note: All elements are already zero, so no operations are needed.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [2,1,3,4] with non-negative integers

Operation Process

Each operation removes minimum values from chosen subarrays

Calculate Total

Sum operations needed for each position

Key Takeaway

🎯 Key Insight: Use monotonic stack to efficiently count smaller elements to the left of each position

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that each element requires as many operations as there are smaller elements to its left plus one. The optimal approach uses a monotonic stack to efficiently count these smaller elements in O(n) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack Approach	O(n)	O(n)	Use a monotonic stack to efficiently calculate operations needed for each element
Simulation Approach	O(n²)	O(1)	Simulate the process by repeatedly finding minimum values and removing them

Monotonic Stack Approach — Algorithm Steps

Traverse array from left to right
Use monotonic stack to track elements smaller than current
For each element, operations needed = stack size + 1
Sum all operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Elements

For each element, count smaller elements to its left

Stack Operations

Maintain monotonic stack of increasing elements

Calculate Operations

Operations = stack size + 1 for each element

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    int stack[1000];
    int stackTop = -1;
    int operations = 0;
    
    for (int i = 0; i < n; i++) {
        // Remove elements from stack that are >= current element
        while (stackTop >= 0 && stack[stackTop] >= nums[i]) {
            stackTop--;
        }
        
        // Current element needs (stackTop + 1) + 1 operations
        operations += stackTop + 2;
        
        // Add current element to stack if it's > 0
        if (nums[i] > 0) {
            stack[++stackTop] = nums[i];
        }
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for [1,2,3] format
    int nums[1000];
    int n = 0;
    char* ptr = line + 1; // Skip '['
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with each element pushed/popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Monotonic stack can store up to n elements in worst case

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler