# Rearrange Array to Maximize Prefix Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rearrange-array-to-maximize-prefix-score)
Canonical: https://scaleengineer.com/dsa/problems/rearrange-array-to-maximize-prefix-score
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## 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 <= 105`
* `-106 <= nums[i] <= 106`

# Approaches
## Brute Force by Generating All Permutations
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.
**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.
**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.
### Explanation
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:
1.  Generate the first permutation of `nums`.
2.  For this permutation, compute its prefix sum array. For an array `p`, the prefix sum array `prefix` is defined as `prefix[i] = p[0] + p[1] + ... + p[i]`.
3.  Count the number of positive elements in the prefix sum array to get the score.
4.  Keep track of the maximum score seen so far.
5.  Generate the next unique permutation of `nums`.
6.  Repeat steps 2-5 until all unique permutations have been evaluated.
7.  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.
### 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_score` if the current permutation's score is higher.
- After exploring all permutations, `max_score` will hold the result.

## Greedy Approach with Sorting
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.
**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.
**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.
### Explanation
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:
1.  First, sort the `nums` array. A standard ascending sort is efficient.
2.  We then iterate from the end of the sorted array (largest elements) to the beginning (smallest elements).
3.  We maintain a running `prefixSum` (using a `long` to prevent overflow) and a `score` counter.
4.  In each step of the iteration, we add the current number to `prefixSum`.
5.  If the resulting `prefixSum` is positive, it contributes to the score, so we increment `score`.
6.  An important optimization: if at any point the `prefixSum` becomes 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 the `prefixSum` can never become positive again. This can save computation time if the prefix sum becomes non-positive early on.

Here is the implementation in Java:
```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;
    }
}
```
### Algorithm
- Sort the array `nums` in ascending order.
- Initialize a `long` variable `prefixSum` to 0 and an integer `score` to 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]` to `prefixSum`.
- If `prefixSum` is greater than 0, increment `score`.
- If `prefixSum` is less than or equal to 0, break the loop, as subsequent prefix sums cannot be positive.
- Return the final `score`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```