#2587

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Rearrange Array to Maximize Prefix Score

Maximize the number of positive prefix sums by rearranging an integer array using a greedy, order-focused strategy.

Problem Statement

You are given a 0-indexed integer array nums. You can reorder its elements in any way, including keeping the current order. After rearrangement, define prefix[i] as the sum of the first i+1 elements. The score is the count of positive values in prefix.

Return the maximum possible score achievable by any rearrangement. Optimize the ordering so that early prefix sums remain positive as long as possible, following a greedy choice plus invariant validation approach.

Examples

Example 1

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

Output: 6

We can rearrange the array into nums = [2,3,1,-1,-3,0,-3]. prefix = [2,5,6,5,2,2,-1], so the score is 6. It can be shown that 6 is the maximum score we can obtain.

Example 2

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

Output: 0

Any rearrangement of the array will result in a score of 0.

Constraints

1 <= nums.length <= 105
-106 <= nums[i] <= 106

Solution Approach

Sort in Descending Order

Arrange nums in descending order so that the largest elements come first. This ensures the initial prefix sums are maximized and provides a foundation for the greedy selection.

Iterate with Running Total

Maintain a cumulative sum while iterating through the sorted array. Include each element only if adding it keeps the running total positive, counting each valid prefix to maximize the score.

Return Maximum Count

After processing all elements, the count of positive prefix sums gives the maximum score. This approach strictly follows the greedy choice plus invariant validation, avoiding negative early sums.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting, and space complexity is O(1) or O(n) depending on whether a separate prefix array is maintained. Iteration and cumulative sum tracking are linear operations.

What Interviewers Usually Probe

Expect candidates to identify the greedy choice of ordering the array in descending values.
Look for correct handling of prefix sums to avoid early negative totals that reduce score.
Watch if candidates can justify why adding smaller elements later does not reduce maximum score.

Common Pitfalls or Variants

Common pitfalls

Adding elements without checking if the running prefix sum remains positive.
Failing to sort in descending order, which can lower the maximum achievable score.
Miscounting prefix sum positions when updating the score.

Follow-up variants

Compute the minimum number of negative prefix sums achievable with any rearrangement.
Find the rearrangement that maximizes the sum of all positive prefix sums instead of count.
Handle arrays with additional constraints like only rearranging subsets of the elements.

FAQ

What is the main strategy for Rearrange Array to Maximize Prefix Score?

Sort the array in descending order and iteratively add elements while keeping prefix sums positive to maximize the score.

Can negative numbers contribute to the maximum prefix score?

Only if adding them does not turn the cumulative prefix sum negative; otherwise they are skipped.

What is the time complexity of the optimal approach?

Sorting dominates the complexity, giving O(n log n), with linear iteration for prefix sum counting.

Why does the greedy approach guarantee the maximum score?

Because placing larger elements first preserves positive prefix sums, satisfying the invariant and maximizing count.

Does GhostInterview provide step guidance for this problem pattern?

Yes, it guides the solver through greedy selection, cumulative sum updates, and order validation for maximal score.

terminal

Solution

Solution 1: Greedy + Sorting

To maximize the number of positive integers in the prefix sum array, we need to make the elements in the prefix sum array as large as possible, that is, to add as many positive integers as possible. Therefore, we can sort the array $nums$ in descending order, then traverse the array, maintaining the prefix sum $s$. If $s \leq 0$, it means that there can be no more positive integers in the current position and the positions after it, so we can directly return the current position.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        s = 0
        for i, x in enumerate(nums):
            s += x
            if s <= 0:
                return i
        return len(nums)

Continue Practicing

#2448 minimum cost to make array equal #2406 divide intervals into minimum number of groups #2389 longest subsequence with limited sum