LeetCode 2587 - Rearrange Array to Maximize Prefix Score

LeetCode Problem 2587

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Prefix Sum

Solution

Problem Understanding

The problem gives us a 0-indexed array of integers, nums, which can include negative numbers, zero, and positive numbers. We are allowed to reorder the elements in any way we choose. After reordering, we compute the prefix sum array, prefix, where prefix[i] is the sum of all elements from index 0 to i. The score of this array is the count of positive numbers in the prefix array. Our goal is to maximize the score by choosing an optimal order for nums.

Key points are:

• Positive prefix sums contribute to the score; negative or zero values do not.
• Reordering is allowed, so the placement of numbers affects the sum accumulation.
• Constraints indicate nums can be as large as 10^5 elements and values up to 10^6 in magnitude. Therefore, an algorithm must be linearithmic at most, O(n log n), to run efficiently.
• Edge cases include arrays of all negatives, all positives, zeros, or a mix. For arrays with all negative numbers, the maximum score is zero. For all positive numbers, the maximum score is the length of the array.

Understanding these constraints is essential because naive approaches like trying all permutations would be computationally infeasible.

Approaches

Brute Force

The brute-force approach would involve generating all possible permutations of the input array, computing the prefix sums for each, and counting the positive prefix sums. Then, we would take the maximum score among all permutations. This guarantees correctness, as it explores all options, but it is exponentially slow, O(n!), which is impossible for n up to 10^5.

Optimal Approach

The key observation is that to maximize the number of positive prefix sums, we should accumulate positive sums as early as possible. This means we should place the largest positive numbers first. Negative numbers or zeros should come later because they might reduce the running prefix sum and decrease the number of positive prefixes.

Formally, the steps are:

1. Sort the array in descending order. Positive numbers will appear first.
2. Iterate through the sorted array, maintaining a running sum.
3. Count each prefix that remains positive. Once the running sum becomes non-positive, we stop counting since any further negative numbers would not contribute positively to the prefix.

This approach works because the sum of the first k largest numbers is maximized at every prefix, ensuring the largest number of positive prefix sums.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Try all permutations, impractical
Optimal	O(n log n)	O(1)	Sort descending, accumulate sum, count positive prefixes

Algorithm Walkthrough

1. Sort nums in descending order. This ensures that the largest values are considered first, maximizing the chance of maintaining a positive prefix sum as we traverse.
2. Initialize a running sum prefix_sum to 0 and a score counter to 0**.
3. Iterate over the sorted array:

• Add the current element to prefix_sum.
• If prefix_sum > 0, increment score by 1.
• If prefix_sum <= 0, we can still continue adding numbers but they may not increase the score.

4. Return score after completing the iteration.

Why it works: By sorting in descending order, every prefix sum is as large as possible given the remaining numbers. This maximizes the number of positive prefix sums because adding smaller or negative numbers later cannot undo the positives accumulated from larger numbers upfront.

Python Solution

from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort(reverse=True)  # Step 1: Sort descending
        prefix_sum = 0
        score = 0
        for num in nums:  # Step 2-3: Iterate and accumulate
            prefix_sum += num
            if prefix_sum > 0:
                score += 1
        return score  # Step 4: Return the total positive prefixes

Explanation: First, we sort the array in descending order. The running sum accumulates elements one by one. Each time the running sum is positive, we increment the score. This directly implements the optimal approach discussed above.

Go Solution

import "sort"

func maxScore(nums []int) int {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] > nums[j] // Sort descending
    })
    
    prefixSum := 0
    score := 0
    for _, num := range nums {
        prefixSum += num
        if prefixSum > 0 {
            score++
        }
    }
    return score
}

Go-specific notes: We use sort.Slice with a custom comparator to sort descending. Slices are dynamically sized, so no extra space is required. The integer operations are safe within the problem's constraints.

Worked Examples

Example 1: nums = [2,-1,0,1,-3,3,-3]

1. Sort descending: [3, 2, 1, 0, -1, -3, -3]
2. Initialize prefix_sum = 0, score = 0.
3. Iterate:

• 3 → prefix_sum = 3 → score = 1
• 2 → prefix_sum = 5 → score = 2
• 1 → prefix_sum = 6 → score = 3
• 0 → prefix_sum = 6 → score = 4
• -1 → prefix_sum = 5 → score = 5
• -3 → prefix_sum = 2 → score = 6
• -3 → prefix_sum = -1 → score remains 6

4. Return 6

Example 2: nums = [-2, -3, 0]

1. Sort descending: [0, -2, -3]
2. Initialize prefix_sum = 0, score = 0.
3. Iterate:

• 0 → prefix_sum = 0 → score = 0
• -2 → prefix_sum = -2 → score = 0
• -3 → prefix_sum = -5 → score = 0

4. Return 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the array dominates; iteration is O(n)
Space	O(1)	Only counters and running sum; sorting in-place

Sorting dominates time complexity. Extra space is negligible because we can sort in-place and maintain only two counters.

Test Cases

# Provided examples
assert Solution().maxScore([2,-1,0,1,-3,3,-3]) == 6  # Mixed numbers
assert Solution().maxScore([-2,-3,0]) == 0           # All non-positive

# Edge cases
assert Solution().maxScore([1,2,3,4,5]) == 5         # All positive
assert Solution().maxScore([-1,-2,-3]) == 0         # All negative
assert Solution().maxScore([0,0,0]) == 0            # All zeros
assert Solution().maxScore([1000000, -1000000]) == 1 # Large numbers
assert Solution().maxScore([1]) == 1                # Single positive
assert Solution().maxScore([-1]) == 0               # Single negative

Test	Why
[2,-1,0,1,-3,3,-3]	Mixed positive, negative, zero numbers
[-2,-3,0]	All non-positive numbers
[1,2,3,4,5]	All positive numbers
[-1,-2,-3]	All negative numbers
[0,0,0]	All zeros
[1000000, -1000000]	Large magnitude numbers
[1]	Single element positive
[-1]	Single element negative

Edge Cases

1. All negative numbers: Any order yields a running sum that is never positive. Our implementation correctly returns 0 as the maximum score.
2. Zeros mixed with negatives: Adding zeros does not increase the prefix sum, so they do not contribute to the score. The algorithm naturally counts only positive sums.
3. Single element arrays: Both positive and negative single-element arrays are handled, returning 1 or 0 as appropriate.
4. Large arrays with large numbers: Sorting in-place and iterating ensures that integer accumulation does not overflow within the problem constraints, making the solution robust to the largest allowed inputs.

This solution is both efficient and safe for all specified constraints.