2587. Rearrange Array to Maximize Prefix Score LeetCode Solution

In this guide, you will get 2587. Rearrange Array to Maximize Prefix Score LeetCode Solution with the best time and space complexity. The solution to Rearrange Array to Maximize Prefix Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Rearrange Array to Maximize Prefix Score solution in C++
  4. Rearrange Array to Maximize Prefix Score solution in Java
  5. Rearrange Array to Maximize Prefix Score solution in Python
  6. Additional Resources
2587. Rearrange Array to Maximize Prefix Score LeetCode Solution image

Problem Statement of Rearrange Array to Maximize Prefix Score

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

See also  148. Sort List LeetCode Solution

Complexity Analysis

  • Time Complexity: O(\texttt{sort})
  • Space Complexity: O(\texttt{sort})

2587. Rearrange Array to Maximize Prefix Score LeetCode Solution in C++

class Solution {
 public:
  int maxScore(vector<int>& nums) {
    long prefix = 0;

    ranges::sort(nums, greater<>());

    for (int i = 0; i < nums.size(); ++i) {
      prefix += nums[i];
      if (prefix <= 0)
        return i;
    }

    return nums.size();
  }
};
/* code provided by PROGIEZ */

2587. Rearrange Array to Maximize Prefix Score LeetCode Solution in Java

class Solution {
  public int maxScore(int[] nums) {
    long prefix = 0;

    nums = Arrays.stream(nums)
               .boxed()
               .sorted(Collections.reverseOrder())
               .mapToInt(Integer::intValue)
               .toArray();

    for (int i = 0; i < nums.length; ++i) {
      prefix += nums[i];
      if (prefix <= 0)
        return i;
    }

    return nums.length;
  }
}
// code provided by PROGIEZ

2587. Rearrange Array to Maximize Prefix Score LeetCode Solution in Python

class Solution:
  def maxScore(self, nums: list[int]) -> int:
    return sum(num > 0
               for num in itertools.accumulate(sorted(nums, reverse=True)))
# code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.