You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the given order).
Let prefix be the array containing the prefix sums of nums after rearranging it. In other words, prefix[i] is the sum of the elements from 0 to i in nums after rearranging it. The score of nums is the number of positive integers in the array prefix.
Return the maximum score you can achieve.
Example 1:
Input: nums = [2,-1,0,1,-3,3,-3] Output: 6 Explanation: 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 Explanation: Any rearrangement of the array will result in a score of 0.
Constraints:
1 <= nums.length <= 105-106 <= nums[i] <= 106Problem Overview: You are given an integer array and can rearrange its elements in any order. After rearranging, compute prefix sums and count how many of them remain positive. The goal is to maximize this count by choosing the best ordering of elements.
The key observation: large positive values should appear early so the running prefix sum stays positive as long as possible. Once the cumulative sum becomes non‑positive, all following prefixes will also fail unless earlier ordering was improved.
Approach 1: Sorting to Maximize Prefix Sums (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This approach uses sorting and a greedy observation. Sort the array in descending order so the largest numbers contribute to the prefix sum first. Then iterate through the sorted array while maintaining a running sum using a prefix sum. Each time the cumulative sum remains greater than zero, increment the score. As soon as the sum becomes non‑positive, adding further elements will only decrease it further (because remaining numbers are smaller), so the process can stop early. This works because placing larger values first maximizes the buffer available to absorb negative numbers later.
Implementation is straightforward: sort descending, iterate once, maintain current_sum, and count prefixes where current_sum > 0. This greedy ordering guarantees the maximum number of valid prefixes because any alternative arrangement would introduce smaller or negative values earlier, reducing the running sum sooner.
Approach 2: Counting Technique for Efficiency (Time: O(n), Space: O(n))
If the value range is manageable or frequency tracking is available, you can avoid full comparison sorting. Count how many times each value appears using a frequency structure. Process values from largest to smallest while updating the cumulative prefix sum and score. Positive values are consumed first to build a strong positive prefix sum. Then gradually add negative values with the smallest magnitude so the running sum decreases as slowly as possible.
This strategy effectively simulates the sorted order but uses counting or bucket processing instead of comparison sort. When the domain of numbers is constrained, this reduces time complexity to O(n). The logic remains identical: keep extending the prefix while the cumulative sum stays positive.
Recommended for interviews: The greedy sorting approach is the expected solution. It demonstrates understanding of ordering strategies and prefix sum behavior while staying simple and reliable. A brute force permutation idea shows initial reasoning, but sorting with a greedy prefix check proves algorithmic maturity and is easy to implement within interview time.
This approach sorts the array in descending order. By placing larger (more positive) numbers earlier, we maximize the prefix sums early on, which minimizes the chance that subsequent additions result in non-positive values in the prefix array. This increases the overall maximum score by maximizing the number of positive prefix sums.
We first sort the array in descending order of values using qsort in C, so that positive numbers come first. This allows us to form the prefix sum with maximum positive integers initially. We iterate through the array, adding each number to the prefix sum, and count how many times the prefix sum remains positive to determine the score.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) as no additional space is used besides input storage.
This approach involves sorting and counting towards an efficient solution. It focuses on counting negative numbers rather than recalculating the prefix sum. By observing when adding subsequent numbers does not result in a positive prefix, one can maximize the efficiency by processing backwards for negatives and forwards for positives.
In this solution, while similar to the sorting approach, is reaching an optimized path by ensuring early negative numbers won’t affect the total processing if prefixed early with sufficient positive influence as evaluated beforehand.
Python
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).
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.
Otherwise, after the traversal, we return the length of the array.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Sorting to Maximize Prefix Sums | Time Complexity: O(n log n) due to the sorting step. |
| Counting Technique for Efficiency | Time Complexity: O(n log n) due to sorting. |
| Greedy + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) to O(n) | General case. Works for any integer range and is the most common interview solution. |
| Counting / Frequency Technique | O(n) | O(n) | Useful when values fall within a manageable range or frequency buckets can replace comparison sorting. |
Leetcode Weekly Contest 336 | 6316. Rearrange Array to Maximize Prefix Score | Python • Bayu Aji • 546 views views
Watch 9 more video solutions →Practice Rearrange Array to Maximize Prefix Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor