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.

Description Hints 4 Solution

3511. Make a Positive Array

Medium36.9% acceptance1 companyPremium elsewhere, free here

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.

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Asked at 1 company

UKG

Topics

Hints open one at a time

Hint 1

Only check subarrays up to a specific size.

Hint 2

Find the subarrays containing between 3 and 5 elements with a non-positive total sum.

Hint 3

Use a greedy approach to assign certain indices the maximum value.

Hint 4

Start with the subarray with the smallest last index i. Replace the element at index i with the maximum value. Find the selected subarray with the next smallest last index j that does not contain index i. Replace the element at index j with the maximum value, and repeat this process until all non-positive subarrays are fixed.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[-10,15,-12]

Input

[-1,-2,3,-1,2,6]

Input

[1,2,3]

Your code is saved on this device.Solution