Skip to main content
Talentd

Make a Positive Array - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedyPrefix Sum4 min readAsked at: UKG
Practice this problem

Problem Statement

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 -1018 and 1018.

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

 

Example 1:

Input: nums = [-10,15,-12]

Output: 1

Explanation:

The only subarray with more than 2 elements is the array itself. The sum of all elements is (-10) + 15 + (-12) = -7. By replacing nums[0] with 0, the new sum becomes 0 + 15 + (-12) = 3. Thus, the array is now positive.

Example 2:

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

Output: 1

Explanation:

The only subarrays with more than 2 elements and a non-positive sum are:

Subarray Indices Subarray Sum Subarray After Replacement (Set nums[1] = 1) New Sum
nums[0...2] [-1, -2, 3] 0 [-1, 1, 3] 3
nums[0...3] [-1, -2, 3, -1] -1 [-1, 1, 3, -1] 2
nums[1...3] [-2, 3, -1] 0 [1, 3, -1] 3

Thus, nums is positive after one operation.

Example 3:

Input: nums = [1,2,3]

Output: 0

Explanation:

The array is already positive, so no operations are needed.

 

Constraints:

  • 3 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Approach Overview

Problem Overview: You are given an integer array and need to ensure every prefix sum of the array remains strictly positive. The task typically allows modifying elements (such as flipping negative values) while minimizing the number of operations. The core challenge is maintaining a running prefix sum that never drops to zero or below.

Approach 1: Brute Force Prefix Fixing (O(n^2) time, O(1) space)

Compute the prefix sum while scanning the array. Whenever the running sum becomes non‑positive, look backward and choose a negative element to flip or adjust so the prefix becomes positive again. Each time the prefix fails, you may need to scan previously processed elements to decide which one to modify. This works conceptually but becomes expensive because every prefix violation may trigger another linear scan. Time complexity grows to O(n^2) with constant extra space.

Approach 2: Greedy with Prefix Sum and Max Heap (O(n log n) time, O(n) space)

Track a running prefix sum while iterating through the array. Every time you encounter a negative value, push it into a max heap (or priority queue). The key greedy insight: if the prefix sum becomes non‑positive, flipping the most negative element seen so far increases the prefix sum the most. Pop the largest‑magnitude negative value from the heap and flip it, which effectively adds twice its absolute value to the prefix sum. Continue until the prefix becomes positive again. Each element is inserted and possibly removed from the heap once, giving O(n log n) time and O(n) space.

This method relies on maintaining the running total via prefix sum while using a priority queue to enforce the greedy choice. The heap ensures the correction step always picks the modification that maximally restores the prefix balance.

Recommended for interviews: The greedy heap approach is what interviewers expect. Starting with the brute force explanation shows you understand the prefix constraint, but the optimized solution demonstrates knowledge of greedy algorithms and efficient data structures applied to array processing. The key observation is that fixing the most negative value gives the largest prefix increase, which makes the greedy choice provably optimal.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Prefix FixingO(n^2)O(1)Useful for reasoning about the problem and validating small inputs
Greedy + Max Heap with Prefix SumO(n log n)O(n)General optimal solution when array contains both positive and negative values

Frequently Asked Questions

Is Make a Positive Array easy or hard?
Make a Positive Array is generally classified as a medium difficulty problem. The challenge is recognizing the greedy insight that flipping the most negative value gives the maximum improvement to the prefix sum while keeping the operation count minimal.
Make a Positive Array Python/Java solution
Implement the greedy approach with a priority queue. Iterate through the array, maintain a running prefix sum, and push negative values into a heap. When the prefix becomes non‑positive, remove the most negative value from the heap and flip it, updating the prefix sum accordingly. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Make a Positive Array in O(n)?
A strict O(n) solution is difficult because selecting the most negative element efficiently requires a priority structure. The common approach maintains a max heap of negative values while computing prefix sums. Each heap operation costs O(log n), resulting in an overall O(n log n) algorithm.
What is the best approach for Make a Positive Array?
The most efficient solution uses a greedy strategy combined with prefix sums and a max heap. While scanning the array, track the running prefix sum and store negative numbers in a heap. If the prefix sum becomes non‑positive, flip the most negative value seen so far to maximize the increase in the sum. This approach runs in O(n log n) time and O(n) space.
Is Make a Positive Array asked at Google/Amazon/Meta?
Problems involving maintaining positive prefix sums and greedy corrections appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this pattern test understanding of prefix sums, greedy decision making, and priority queues.
What data structure is used in Make a Positive Array?
The optimal solution uses a max heap (priority queue) to track negative elements encountered during iteration. This structure allows quickly selecting the most negative value when the prefix sum becomes non‑positive, which maximizes the correction effect.
What is the time complexity of Make a Positive Array?
The optimal greedy solution runs in O(n log n) time because each negative element may be inserted and removed from a heap. Space complexity is O(n) for storing negative elements. A naive brute force approach can take O(n^2) time when repeatedly scanning previous elements to fix invalid prefixes.

Ready to solve this problem?

Practice Make a Positive Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays