Skip to main content
Talentd

Rearrange Array to Maximize Prefix Score - Solution & Explanation

MediumArrayGreedySortingPrefix Sum14 min readAsked at: Amazon, IBM, Jpmorgan
Practice this problem

Problem Statement

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

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.

We first sort the array in descending order of values using qsort in C, so that positive numbers come first. This allows us to form the prefix sum with maximum positive integers initially. We iterate through the array, adding each number to the prefix sum, and count how many times the prefix sum remains positive to determine the score.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) as no additional space is used besides input storage.

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.

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.

Code

PythonJavaScript

Python

JavaScript

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting to Maximize Prefix Sums

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) as no additional space is used besides input storage.

Counting Technique for Efficiency

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

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(1) to O(n)General case. Works for any integer range and is the most common interview solution.
Counting / Frequency TechniqueO(n)O(n)Useful when values fall within a manageable range or frequency buckets can replace comparison sorting.

Video Solution

Leetcode Weekly Contest 336 | 6316. Rearrange Array to Maximize Prefix Score | Python • Bayu Aji • 546 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Rearrange Array to Maximize Prefix Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two City Scheduling