Rearrange Array to Maximize Prefix Score
MedPrompt
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] <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores every possible arrangement of the nums array to find the one that yields the maximum prefix score. It's a naive method that guarantees finding the optimal solution by exhaustive search, but it's computationally very expensive.
Algorithm
- Define a recursive function that generates all permutations of the input array
nums. - The base case for the recursion is when a full permutation has been formed.
- For each complete permutation:
- Calculate its prefix sum array.
- Count the number of positive integers in the prefix sum array to get the score.
- Update a global variable
max_scoreif the current permutation's score is higher.
- After exploring all permutations,
max_scorewill hold the result.
Walkthrough
This method exhaustively checks every possible arrangement of the numbers in nums. The main idea is to generate all permutations of the array and, for each one, calculate the score. The maximum score found among all permutations is the answer.
The algorithm is as follows:
- Generate the first permutation of
nums. - For this permutation, compute its prefix sum array. For an array
p, the prefix sum arrayprefixis defined asprefix[i] = p[0] + p[1] + ... + p[i]. - Count the number of positive elements in the prefix sum array to get the score.
- Keep track of the maximum score seen so far.
- Generate the next unique permutation of
nums. - Repeat steps 2-5 until all unique permutations have been evaluated.
- Return the overall maximum score.
Generating permutations is a classic combinatorial problem, often solved with recursion and backtracking. While this approach is guaranteed to be correct, its factorial time complexity makes it infeasible for the given constraints.
Complexity
Time
O(N! * N). There are N! possible permutations. For each permutation, it takes O(N) time to calculate the prefix sums and the score. This is highly inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
Space
O(N), where N is the number of elements in `nums`. This space is used to store the current permutation and for the recursion stack.
Trade-offs
Pros
Guarantees finding the optimal solution by checking every possibility.
Cons
Extremely high time complexity, making it impractical for input sizes larger than about 12.
A much more efficient approach is based on a greedy strategy. To maximize the number of positive prefix sums, we should try to keep the prefix sum as large as possible at each step. This can be achieved by adding the largest available numbers first. Therefore, sorting the array in descending order provides the optimal arrangement.
Algorithm
- Sort the array
numsin ascending order. - Initialize a
longvariableprefixSumto 0 and an integerscoreto 0. - Iterate through the sorted array from right to left (i.e., from the largest element to the smallest).
- In each iteration, add the current element
nums[i]toprefixSum. - If
prefixSumis greater than 0, incrementscore. - If
prefixSumis less than or equal to 0, break the loop, as subsequent prefix sums cannot be positive. - Return the final
score.
Walkthrough
The intuition behind this greedy strategy is that to maximize the number of positive prefix sums, we must arrange the numbers in a way that keeps the running total as high as possible for as long as possible. Adding a larger number before a smaller number always results in a larger or equal intermediate prefix sum (S + large vs S + small), while the final sum after adding both remains the same. By extending this logic, sorting the entire array in descending order is the optimal arrangement.
The algorithm proceeds as follows:
- First, sort the
numsarray. A standard ascending sort is efficient. - We then iterate from the end of the sorted array (largest elements) to the beginning (smallest elements).
- We maintain a running
prefixSum(using alongto prevent overflow) and ascorecounter. - In each step of the iteration, we add the current number to
prefixSum. - If the resulting
prefixSumis positive, it contributes to the score, so we incrementscore. - An important optimization: if at any point the
prefixSumbecomes zero or negative, we can immediately stop. Since we are processing numbers in decreasing order, any subsequent numbers we add will be smaller or equal, meaning theprefixSumcan never become positive again. This can save computation time if the prefix sum becomes non-positive early on.
Here is the implementation in Java:
import java.util.Arrays; class Solution { public int maxScore(int[] nums) { // Sort the array in ascending order. // Time complexity: O(N log N) Arrays.sort(nums); long prefixSum = 0; int score = 0; // Iterate from the end to the beginning (effectively in descending order). // Time complexity: O(N) for (int i = nums.length - 1; i >= 0; i--) { prefixSum += nums[i]; // If the prefix sum is positive, it's a valid prefix. if (prefixSum > 0) { score++; } else { // Optimization: If the sum is not positive, adding smaller or // negative numbers won't make it positive again. // So we can break early. break; } } return score; }}Complexity
Time
O(N log N), where N is the number of elements in `nums`. The dominant operation is sorting the array. The subsequent iteration takes O(N) time.
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm used. For `Arrays.sort` in Java on primitive types, it's typically O(log N) for the recursion stack of Quicksort. Some sorting algorithms like Heapsort can achieve O(1) auxiliary space.
Trade-offs
Pros
Highly efficient and provides the optimal solution.
Simple to implement using standard library sorting functions.
Cons
The time complexity is limited by the sorting algorithm, so it's not a linear time solution.
Solutions
Solution
class Solution {public int maxScore(int[] nums) { Arrays.sort(nums); int n = nums.length; long s = 0; for (int i = 0; i < n; ++i) { s += nums[n - i - 1]; if (s <= 0) { return i; } } return n; }}class Solution {public: int maxScore(vector<int> &nums) { sort(nums.rbegin(), nums.rend()); long long s = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { s += nums[i]; if (s <= 0) { return i; } } return n; }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.