Rearrange Array to Maximize Prefix Score — Solution
Rearrange Array to Maximize Prefix Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Rearrange Array to Maximize Prefix Score is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may reorder the integer array nums any way you like. After reordering, let prefix[i] be the sum of the first i + 1 elements. The score of the arrangement is the number of positive values among prefix[0], prefix[1], ..., prefix[n-1].
Return the maximum score you can achieve.
Example 1
Input: nums = [2,-1,0,1,-3,-3]
Output: 4
Explanation: Order `[2,1,0,-1,-3,-3]` gives prefix sums `2,3,3,2,-1,-4` — four positive.
Example 2
Input: nums = [-3,-1,-2]
Output: 0
Example 3
Input: nums = [0,0]
Output: 0
Explanation: Zero is not positive.
Constraints
1 <= nums.length <= 10^5-10^6 <= nums[i] <= 10^6
Hints for Rearrange Array to Maximize Prefix Score
Hint 1
To keep the running sum positive for as long as possible, which numbers should come first?
Hint 2
Sort in descending order — the prefix sums are then as large as they can be at every length.
Hint 3
Count prefix sums that are strictly positive (in 64-bit; they can reach
10^11).
How to solve Rearrange Array to Maximize Prefix Score
For every length i + 1, the largest possible sum of i + 1 elements is the sum of the i + 1 largest ones. Descending order achieves that maximum for every prefix simultaneously.
Approach
- Sort
numsin descending order. - Accumulate a 64-bit running sum.
- Count how many running sums are strictly greater than 0 (you can stop at the first non-positive one).
Why it works
Any arrangement's prefix of length m sums to at most the sum of the m largest values, which is exactly the descending arrangement's prefix of length m. So if any arrangement has a positive prefix of length m, the descending one does too — it maximises the count for every m at once.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Zero prefix sums do not count; the comparison is strictly greater than 0.
- Once a descending prefix sum is non-positive, every later one is too (only non-positive values remain to add).
- Sums reach
10^11, beyond 32-bit range.
Reference solution
Python
from typing import List
def maxScore(nums: List[int]) -> int:
prefix = 0
score = 0
for x in sorted(nums, reverse=True):
prefix += x
if prefix <= 0:
break
score += 1
return scoreJava
public static int maxScore(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
long prefix = 0;
int score = 0;
for (int i = s.length - 1; i >= 0; i--) {
prefix += s[i];
if (prefix <= 0) break;
score++;
}
return score;
}C++
int maxScore(vector<int>& nums) {
vector<int> s(nums.begin(), nums.end());
sort(s.rbegin(), s.rend());
long long prefix = 0;
int score = 0;
for (int x : s) {
prefix += x;
if (prefix <= 0) break;
score++;
}
return score;
}JavaScript
var maxScore = function(nums) {
var s = nums.slice().sort(function(a, b) { return b - a; });
var prefix = 0, score = 0;
for (var i = 0; i < s.length; i++) {
prefix += s[i];
if (prefix <= 0) break;
score++;
}
return score;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms