2587. Rearrange Array to Maximize Prefix Score - Solution

The problem

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 <= 10⁵
-10⁶ <= nums[i] <= 10⁶

Approach overview

Problem 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 1: Sorting to Maximize Prefix Sums

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.

Python

def maxScore(nums):
    nums.sort(reverse=True)
    prefix_sum = 0
    count = 0
    for num in nums:
        prefix_sum += num
        if prefix_sum > 0:
            count += 1
        else:
            break
    return count

print(maxScore([2, -1, 0, 1, -3, 3, -3]))

Java

import java.util.Arrays;

public class MaxScore {
    public static int maxScore(int[] nums) {
        Arrays.sort(nums);
        int prefixSum = 0, count = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            prefixSum += nums[i];
            if (prefixSum > 0) count++;
            else break;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, -1, 0, 1, -3, 3, -3};
        System.out.println(maxScore(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxScore(std::vector<int>& nums) {
    std::sort(nums.rbegin(), nums.rend());
    long long prefixSum = 0;
    int count = 0;
    for (int num : nums) {
        prefixSum += num;
        if (prefixSum > 0) count++;
        else break;
    }
    return count;
}

int main() {
    std::vector<int> nums = {2, -1, 0, 1, -3, 3, -3};
    std::cout << maxScore(nums) << std::endl;
    return 0;
}

JavaScript

function maxScore(nums) {
    nums.sort((a, b) => b - a);
    let prefixSum = 0, count = 0;
    for (let num of nums) {
        prefixSum += num;
        if (prefixSum > 0) count++;
        else break;
    }
    return count;
}

console.log(maxScore([2, -1, 0, 1, -3, 3, -3]));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int maxScore(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int prefixSum = 0, count = 0;
    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i];
        if (prefixSum > 0) count++;
        else break;
    }
    return count;
}

int main() {
    int nums[] = {2,-1,0,1,-3,3,-3};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", maxScore(nums, size));
    return 0;
}

using System;

public class MaxScoreCalculator {
    public static int MaxScore(int[] nums) {
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        int prefixSum = 0, count = 0;
        foreach (int num in nums) {
            prefixSum += num;
            if (prefixSum > 0) count++;
            else break;
        }
        return count;
    }

    public static void Main() {
        int[] nums = {2, -1, 0, 1, -3, 3, -3};
        Console.WriteLine(MaxScore(nums));
    }
}

Python's sorting enables ease of descending order arrangement using the sort(reverse=True) argument. Then follow through with prefix sum calculation and counting of positives in a straightforward loop.

Complexity

Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) no extra space required.

Try this approach in the editor

Approach 2: Counting Technique for Efficiency

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.

Python

def maxScore(nums):
    nums.sort(reverse=True)
    prefix_sum = 0
    count = 0
    for num in nums:
        prefix_sum += num
        if prefix_sum > 0:
            count += 1
        else:
            break
    return count

print(maxScore([2, -1, 0, 1, -3, 3, -3]))

JavaScript

function maxScore(nums) {
    nums.sort((a, b) => b - a);
    let prefixSum = 0, count = 0;
    for (let num of nums) {
        prefixSum += num;
        if (prefixSum > 0) count++;
        else break;
    }
    return count;
}

console.log(maxScore([2, -1, 0, 1, -3, 3, -3]));

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.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Greedy + Sorting

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.

TypeScript

function maxScore(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let s = 0;
    for (let i = 0; i < n; ++i) {
        s += nums[n - i - 1];
        if (s <= 0) {
            return i;
        }
    }
    return n;
}

func maxScore(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	s := 0
	for i := range nums {
		s += nums[n-i-1]
		if s <= 0 {
			return i
		}
	}
	return n
}

Rust

impl Solution {
    pub fn max_score(mut nums: Vec<i32>) -> i32 {
        nums.sort_by(|a, b| b.cmp(a));
        let mut s: i64 = 0;
        for (i, &x) in nums.iter().enumerate() {
            s += x as i64;
            if s <= 0 {
                return i as i32;
            }
        }
        nums.len() as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sorting to Maximize Prefix Sums	Time Complexity: O(n log n) for sorting. Space Complexity: O(1) no extra space required.
Counting Technique for Efficiency	Time Complexity: O(n log n) due to sorting. Space Complexity: O(1).
Greedy + Sorting	–

Complexity analysis

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.

Frequently asked questions

Is Rearrange Array to Maximize Prefix Score easy or hard?

The problem is rated Medium because the greedy insight is not immediately obvious. Once you recognize that larger numbers must appear first to maximize the positive prefix length, the implementation becomes straightforward with sorting and a single prefix sum pass.

Rearrange Array to Maximize Prefix Score Python/Java solution

Both Python and Java implementations follow the same pattern: sort the array in descending order, iterate through elements, maintain a cumulative sum, and count how many prefixes remain positive. Python typically uses list sorting, while Java uses Arrays.sort with reverse traversal.

How to solve Rearrange Array to Maximize Prefix Score in O(n)?

An O(n) solution is possible when the value range allows frequency counting. Instead of comparison sorting, track counts of each value and process numbers from largest to smallest while maintaining the prefix sum. This simulates descending order without sorting, allowing linear processing.

What is the best approach for Rearrange Array to Maximize Prefix Score?

The best approach is a greedy strategy combined with sorting. Sort the array in descending order and iterate while maintaining a running prefix sum. Count each prefix where the cumulative sum stays positive. This works because placing the largest numbers first maximizes the buffer against negative numbers. The time complexity is O(n log n).

Is Rearrange Array to Maximize Prefix Score asked at Google/Amazon/Meta?

Greedy array ordering and prefix sum problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear verbatim, the underlying technique—reordering elements to optimize prefix behavior—is a common interview pattern.

What data structure is used in Rearrange Array to Maximize Prefix Score?

The primary structure is a simple array combined with sorting. The algorithm also relies on a running prefix sum variable to track cumulative values. In optimized variants, a hash map or frequency array may be used for counting-based ordering.

What is the time complexity of Rearrange Array to Maximize Prefix Score?

The standard solution runs in O(n log n) time due to sorting the array. After sorting, a single pass computes prefix sums and counts valid prefixes in O(n). Space complexity is O(1) if sorting in place, or O(n) depending on the language's sorting implementation.

Rearrange Array to Maximize Prefix Score solution and explanation

The problem

Approach overview

Approach 1: Sorting to Maximize Prefix Sums

Approach 2: Counting Technique for Efficiency

Approach 3: Greedy + Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rearrange Array to Maximize Prefix Score solution and explanation

The problem

Approach overview

Approach 1: Sorting to Maximize Prefix Sums

Approach 2: Counting Technique for Efficiency

Approach 3: Greedy + Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems