Watch 10 video solutions for Rearrange Array to Maximize Prefix Score, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Bayu Aji has 546 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |