Make the Prefix Sum Non-negative - Practice Coding Problems

Make the Prefix Sum Non-negative - Problem

You are given a 0-indexed integer array nums. You can apply the following operation any number of times:

Pick any element from nums and put it at the end of nums.

The prefix sum array of nums is an array prefix of the same length as nums such that prefix[i] is the sum of all the integers nums[j] where j is in the inclusive range [0, i].

Return the minimum number of operations such that the prefix sum array does not contain negative integers. The test cases are generated such that it is always possible to make the prefix sum array non-negative.

Input & Output

Example 1 — Mixed Values

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

› Output: 0

💡 Note: Prefix sums are [2,1,3] - all non-negative, so no operations needed

Example 2 — Needs Rearrangement

$ Input: nums = [3,-5,4]

› Output: 1

💡 Note: Prefix sums are [3,-2,2]. When sum becomes -2, we move -5 to end: [3,4,-5] with prefix sums [3,7,2]

Example 3 — Multiple Negatives

$ Input: nums = [1,-1,-1,1]

› Output: 1

💡 Note: At position 2, prefix sum becomes -1. We move the smallest element (-1) to end, requiring 1 operation

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
The sum of all elements in nums is non-negative

Visualization

Tap to expand

Understanding the Visualization

Input

Array with potentially problematic negative values

Process

Move negative elements to end when prefix sum goes negative

Output

Minimum number of operations needed

Key Takeaway

🎯 Key Insight: When prefix sum becomes negative, greedily move the smallest element seen so far to the end

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that when the prefix sum becomes negative, we need to remove the smallest element seen so far to minimize impact. The optimal approach uses a min-heap to efficiently track and remove the smallest elements. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Min-Heap	O(n log n)	O(n)	Use a min-heap to efficiently move problematic negative elements to the end
Try All Permutations	O(n! × n)	O(n)	Generate all possible arrangements and find the minimum operations needed

Greedy with Min-Heap — Algorithm Steps

Iterate through array calculating prefix sums
When prefix sum goes negative, find minimum element seen so far
Move that minimum element to end and increment operation count
Continue until all elements processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Prefix Sum

Calculate running sum, maintain min-heap of seen elements

Handle Negative

When sum goes negative, remove smallest from heap

Count Operations

Each removal represents moving element to end

Code -

solution.c — C

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

typedef struct {
    int* data;
    int size;
    int capacity;
} MinHeap;

MinHeap* createMinHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->data = (int*)malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void minHeapify(MinHeap* heap, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < heap->size && heap->data[left] < heap->data[smallest])
        smallest = left;
    if (right < heap->size && heap->data[right] < heap->data[smallest])
        smallest = right;
    
    if (smallest != i) {
        int temp = heap->data[i];
        heap->data[i] = heap->data[smallest];
        heap->data[smallest] = temp;
        minHeapify(heap, smallest);
    }
}

void push(MinHeap* heap, int val) {
    heap->data[heap->size] = val;
    int i = heap->size++;
    
    while (i > 0 && heap->data[(i - 1) / 2] > heap->data[i]) {
        int temp = heap->data[i];
        heap->data[i] = heap->data[(i - 1) / 2];
        heap->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

int pop(MinHeap* heap) {
    if (heap->size == 0) return INT_MAX;
    
    int min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    minHeapify(heap, 0);
    return min;
}

int solution(int* nums, int n) {
    int operations = 0;
    long long prefixSum = 0;
    MinHeap* minHeap = createMinHeap(n);
    
    for (int i = 0; i < n; i++) {
        prefixSum += nums[i];
        push(minHeap, nums[i]);
        
        if (prefixSum < 0) {
            int smallest = pop(minHeap);
            prefixSum -= smallest;
            operations++;
        }
    }
    
    free(minHeap->data);
    free(minHeap);
    return operations;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each element is added/removed from heap at most once, heap operations are O(log n)

⚡ Linearithmic

Space Complexity

O(n)

Min-heap can store up to n elements in worst case

⚡ Linearithmic Space

32.0K 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

Greedy with Min-Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler