Make the Prefix Sum Non-negative

Medium

Asked by:

35 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the original order).

Let prefix be the prefix sum array of nums. nums is considered valid if prefix[i] >= 0 for all i.

Return the minimum number of elements you need to rearrange in nums such that nums is valid.

Example 1:

Input: nums = [5,-2,-1,5,-5]
Output: 1
Explanation:
One possible rearrangement is [5,5,-2,-1,-5], with prefix sum values [5,10,8,7,2], which are all non-negative.
We can prove that 1 is the minimum number of elements to rearrange to make nums valid.

Example 2:

Input: nums = [-1,1,-3,2]
Output: 0
Explanation:
One possible rearrangement is [1, 2, -1, -3], with prefix sum values [1,3,2,-1], which is not valid.
However, the original array [-1,1,-3,2] has prefix sum values [-1,0,-3,-1], which is also not valid.
We can prove that 0 is the minimum number of elements to rearrange to make nums valid.

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values in the input array? Could they be very large, potentially causing overflow issues?
Is the input array guaranteed to be non-empty? If it can be empty, what should I return?
If multiple sets of indices would make the prefix sum non-negative, is any one of them acceptable, or is there a specific ordering or criteria for selecting one?
What should I return if it is impossible to make the prefix sum non-negative?
Can you define more precisely what you mean by 'make the prefix sum non-negative'? Does it need to be strictly positive or can it be zero?

Brute Force Solution

Approach

The goal is to make a running total of numbers always be zero or more. We'll try fixing the list by swapping pairs of numbers to see if we can achieve this. The brute force way means testing *every* possible swap until we find one that works.

Here's how the algorithm would work step-by-step:

First, we look at the original list of numbers and calculate the running total at each point.
If we find a running total that's negative, we need to try to fix it.
To fix it, we start by trying to swap the first number in the list with every other number in the list, one at a time.
After each swap, we recalculate the running totals.
If, after a swap, *all* running totals are zero or more, we've found a solution and we're done.
If the first set of swaps didn't work, we try swapping the second number in the original list with every number after it, one at a time, and recalculate the running totals after each swap.
We keep doing this, trying every possible swap between numbers in the list until we find a swap that makes all the running totals non-negative. If no swaps work, there is no answer to be found by swapping.

Code Implementation

def make_prefix_sum_non_negative_brute_force(numbers):
    list_length = len(numbers)
    for first_index in range(list_length):
        for second_index in range(first_index, list_length):
            # Attempt to swap the numbers at the two indices.
            temporary_value = numbers[first_index]
            numbers[first_index] = numbers[second_index]
            numbers[second_index] = temporary_value

            prefix_sum = 0
            is_non_negative = True

            for number in numbers:
                prefix_sum += number
                # We need to check if prefix sum goes negative
                if prefix_sum < 0:
                    is_non_negative = False
                    break

            # If all prefix sums are non-negative, return.
            if is_non_negative:
                return numbers

            # Swap back if the current swap did not work.
            temporary_value = numbers[first_index]
            numbers[first_index] = numbers[second_index]
            numbers[second_index] = temporary_value

    # No valid swap found.
    return None

Big(O) Analysis

Time Complexity

O(n³) – The described brute force approach involves iterating through the input array of size 'n' to identify negative prefix sums. When a negative prefix sum is found, the algorithm attempts to correct it by swapping an element at or after the negative prefix sum location with every element that follows it. In the worst case, for each of the 'n' elements, we potentially perform 'n' swaps. After each swap, the prefix sum needs to be recalculated, which takes O(n) time. Therefore, the overall time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(N) – The provided algorithm calculates running totals after each swap. To recalculate the running totals, it needs to store these totals in an auxiliary array. The size of this array will be equal to the number of elements in the original list, denoted as N. Therefore, the auxiliary space required is directly proportional to the input size N, resulting in a space complexity of O(N).

Optimal Solution

Approach

The main idea is to keep track of the running total. If the running total ever becomes negative, we need to fix it by strategically swapping some numbers to make it non-negative. We always swap the most negative number that caused the issue.

Here's how the algorithm would work step-by-step:

Calculate the prefix sum as you go through the sequence of numbers.
If the prefix sum is negative at any point, identify the number that caused the largest decrease in the sum prior to that point.
Swap the most negative number you found with its positive counterpart.
Adjust the prefix sum after the swap to reflect the change.
Continue this process until the prefix sum is always non-negative.

Code Implementation

def make_prefix_sum_non_negative(numbers):
    prefix_sum = 0
    swap_count = 0
    negative_numbers = []

    for i in range(len(numbers)):
        prefix_sum += numbers[i]

        # Store negative numbers to swap if prefix sum goes negative
        if numbers[i] < 0:
            negative_numbers.append(i)
            negative_numbers.sort(key=lambda index: numbers[index])

        # Need to swap if the prefix sum dips below zero
        while prefix_sum < 0:
            if not negative_numbers:
                return -1
            index_to_swap = negative_numbers.pop(0)

            # Always swap the most negative number seen thus far
            prefix_sum -= 2 * numbers[index_to_swap]
            numbers[index_to_swap] *= -1
            swap_count += 1

    return swap_count

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the n elements of the input array once to calculate the prefix sum. In each iteration, if the prefix sum becomes negative, it finds the most negative number encountered so far. Finding the most negative number can be efficiently done using a heap (priority queue) of size at most n, which takes O(log n) time for insertion and retrieval. Since this heap operation is performed at most n times (once for each element in the original array), the overall time complexity is O(n log n) because the prefix sum calculations are O(n) and the heap operations in total are O(n log n). The O(n) prefix sum calculations are therefore dominated by the O(n log n) operations.

Space Complexity

O(N) – The algorithm's space complexity is primarily determined by the need to store the identified most negative numbers for potential swaps. While the plain English description doesn't explicitly state a data structure, implicitly, we must "keep track" of these most negative numbers discovered so far. This implies potentially storing these numbers in a list of size proportional to N, where N is the length of the input sequence, as in the worst case, we might consider every number for a swap. Therefore, the auxiliary space required grows linearly with the input size, leading to O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0, as no operations are needed to make the prefix sum non-negative.
Array with all positive numbers	Return 0, as the prefix sum is already non-negative.
Array with all negative numbers	Sort the array in ascending order (smallest/most negative first) and perform the swap operations until the prefix sums are all non-negative.
Array with a large number of elements	Ensure the algorithm has O(n log n) time complexity due to sorting, avoiding quadratic or worse performance.
Array contains very large negative numbers	Use 64-bit integers to avoid integer overflow when calculating prefix sums.
Array where no amount of swapping can make prefix sums non-negative	Return -1 to indicate that no solution exists.
Array with many zeros	Zeros should be ignored during the sorting step as their placement doesn't affect the negativity of the prefix sum.
Presence of duplicates and their impact on the sorting and swapping operations.	Sorting algorithm needs to be stable if duplicate negative numbers significantly affect the number of operations.

Empty input array

How to Handle:

Return 0, as no operations are needed to make the prefix sum non-negative.

Array with all positive numbers

How to Handle:

Return 0, as the prefix sum is already non-negative.

Array with all negative numbers

How to Handle:

Sort the array in ascending order (smallest/most negative first) and perform the swap operations until the prefix sums are all non-negative.

Array with a large number of elements

How to Handle:

Ensure the algorithm has O(n log n) time complexity due to sorting, avoiding quadratic or worse performance.

Array contains very large negative numbers

How to Handle:

Use 64-bit integers to avoid integer overflow when calculating prefix sums.

Array where no amount of swapping can make prefix sums non-negative

How to Handle:

Return -1 to indicate that no solution exists.

Array with many zeros

How to Handle:

Zeros should be ignored during the sorting step as their placement doesn't affect the negativity of the prefix sum.

Presence of duplicates and their impact on the sorting and swapping operations.

How to Handle:

Sorting algorithm needs to be stable if duplicate negative numbers significantly affect the number of operations.