How hard is LeetCode 2587. Rearrange Array to Maximize Prefix Score?

LeetCode 2587. Rearrange Array to Maximize Prefix Score is rated Medium on LeetCode.

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

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2587. Rearrange Array to Maximize Prefix Score?

The Python solution on this page uses O(\log n) auxiliary space.

What topics does LeetCode 2587. Rearrange Array to Maximize Prefix Score cover?

LeetCode 2587. Rearrange Array to Maximize Prefix Score is tagged Greedy, Array, Prefix Sum and Sorting on LeetCode.

Rearrange Array to Maximize Prefix Score — LeetCode 2587 Python Solution

MediumGreedyArrayPrefix SumSorting

Problem: #2587
Pattern: Prefix Sum
Reading time: 2 min
Source: leetcode.com

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

Example

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

Python solution

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)

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(\log n) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2587. Rearrange Array to Maximize Prefix Score is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2587. Rearrange Array to Maximize Prefix Score?: LeetCode 2587. Rearrange Array to Maximize Prefix Score is rated Medium on LeetCode.
What is the time complexity of LeetCode 2587. Rearrange Array to Maximize Prefix Score?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2587. Rearrange Array to Maximize Prefix Score?: The Python solution on this page uses O(\log n) auxiliary space.
What topics does LeetCode 2587. Rearrange Array to Maximize Prefix Score cover?: LeetCode 2587. Rearrange Array to Maximize Prefix Score is tagged Greedy, Array, Prefix Sum and Sorting on LeetCode.