Rearrange Array to Maximize Prefix Score

Medium
1168.

Rearrange Array to Maximize Prefix Score

Rearrange Array to Maximize Prefix Score is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxScore = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    To keep the running sum positive for as long as possible, which numbers should come first?

  2. Hint 2

    Sort in descending order — the prefix sums are then as large as they can be at every length.

  3. 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

  1. Sort nums in descending order.
  2. Accumulate a 64-bit running sum.
  3. 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 score

Java

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