Make a Positive Array - Practice Coding Problems

Make a Positive Array - Problem

You are given an array nums. An array is considered positive if the sum of all numbers in each subarray with more than two elements is positive.

You can perform the following operation any number of times: Replace one element in nums with any integer between -10¹⁸ and 10¹⁸.

Find the minimum number of operations needed to make nums positive.

Input & Output

Example 1 — Basic Negative Array

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

› Output: 1

💡 Note: Subarray [-5, 2, -3] has sum -6 ≤ 0 and subarray [2, -3, 1] has sum 0 ≤ 0. Replace nums[0] = -5 with a large positive number to fix both problems with 1 operation.

Example 2 — Already Positive

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

› Output: 0

💡 Note: The only subarray with length ≥ 3 is [1, 2, 3] with sum 6 > 0. Array is already positive, so 0 operations needed.

Example 3 — Multiple Problems

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

› Output: 2

💡 Note: Multiple negative subarrays exist. Replace the two most impactful negative elements (like nums[1] = -3 and nums[3] = -4) to make all subarrays positive with 2 operations.

Constraints

1 ≤ nums.length ≤ 1000
-10¹⁸ ≤ nums[i] ≤ 10¹⁸
You can replace any element with any integer between -10¹⁸ and 10¹⁸

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with negative subarrays that need fixing

Identify Problems

Find all subarrays length ≥ 3 with sum ≤ 0

Strategic Replacement

Replace minimum elements to make all subarrays positive

Key Takeaway

🎯 Key Insight: Greedily replace elements that contribute to the most negative subarrays to minimize total operations needed.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 25

The key insight is to identify which elements contribute to the most negative subarrays and replace them greedily. The greedy approach calculates impact scores and targets high-impact negative elements first. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Replacement Strategy	O(n³)	O(n)	Greedily replace the most impactful negative elements to minimize operations
Prefix Sum Analysis	O(n³)	O(n)	Use prefix sums to identify problematic subarrays and fix them efficiently
Brute Force - Check All Combinations	O(2ⁿ × n³)	O(n)	Try all possible combinations of element replacements until array becomes positive

Greedy Replacement Strategy — Algorithm Steps

Calculate impact score for each element
Sort elements by negative impact
Replace highest-impact elements until all subarrays are positive

Visualization

Tap to expand

Step-by-Step Walkthrough

Score Elements

Calculate how many negative subarrays each element affects

Replace Highest Impact

Replace element that fixes most problems first

Repeat Until Fixed

Continue until all subarrays are positive

Code -

solution.c — C

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

int hasNegativeSubarray(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        long long currentSum = 0;
        for (int j = i; j < n; j++) {
            currentSum += arr[j];
            if (j - i >= 2 && currentSum <= 0) {
                return 1;
            }
        }
    }
    return 0;
}

int calculateImpact(int* arr, int n, int index) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        long long currentSum = 0;
        for (int j = i; j < n; j++) {
            currentSum += arr[j];
            if (j - i >= 2 && currentSum <= 0 && i <= index && index <= j) {
                count++;
            }
        }
    }
    return count;
}

int solution(int* nums, int n) {
    if (n <= 2) return 0;
    
    int* arr = malloc(n * sizeof(int));
    memcpy(arr, nums, n * sizeof(int));
    
    if (!hasNegativeSubarray(arr, n)) {
        free(arr);
        return 0;
    }
    
    int operations = 0;
    
    while (hasNegativeSubarray(arr, n) && operations < n) {
        int maxImpact = -1;
        int bestIndex = -1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] < 1000000000) {
                int impact = calculateImpact(arr, n, i);
                if (impact > maxImpact || (impact == maxImpact && (bestIndex == -1 || arr[i] < arr[bestIndex]))) {
                    maxImpact = impact;
                    bestIndex = i;
                }
            }
        }
        
        if (bestIndex == -1) break;
        
        arr[bestIndex] = 1000000000;
        operations++;
    }
    
    free(arr);
    return operations;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) to analyze subarrays, O(n log n) for sorting, limited iterations

⚠ Quadratic Growth

Space Complexity

O(n)

Impact score array and temporary modifications

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~35 min Avg. Time

892 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 Replacement Strategy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler