2587. Rearrange Array to Maximize Prefix Score


Problem Description

In this problem, you are provided with an integer array nums. Your goal is to rearrange the elements of this array in any order. By doing this, you want to maximize the "score" of the array. The "score" is defined as the number of positive integers in the array of prefix sums.

The prefix sums array, prefix, is created by summing elements from the start up to the current position after you have rearranged the array. prefix[i] represents the sum of elements from index 0 up to index i in the newly arranged array. Your task is to rearrange nums such that the count of positive numbers in the prefix array is the highest possible.

For example, if your input array nums is [1, -2, 3], you could rearrange it to [3, 1, -2]. Then, your prefix array would be [3, 4, 2], and the score of nums would be 3 since there are three positive numbers in the prefix array.

Intuition

The key intuition behind obtaining the maximum score is related to the arrangement of the numbers in descending order. By sorting the array in reverse order, we ensure that we add the largest numbers first. This has the benefit of potentially offsetting any negative numbers that come later in the sequence.

Consider an array with both positive and negative numbers. If we start by adding the largest positive numbers, the prefix sum is more likely to stay positive for a longer stretch, even if we encounter negative numbers. On the other hand, if we were to add negative numbers early on, they would decrease the overall sum, and thus there's a higher chance for the sum to drop to zero or become negative, which would reduce our score.

Thus, the approach used in the solution involves sorting nums in descending order and then calculating the prefix sums iteratively. With each sum, we check if the current sum s is less than or equal to zero. If it is, we return the index i, which represents the number of positive integers in the prefix array until that point. Otherwise, if we go through the entire list without the sum becoming non-positive, we return the length of nums, as all prefix sums are positive.

Learn more about Greedy, Prefix Sum and Sorting patterns.

Solution Approach

The solution to this problem uses a greedy algorithm, which is reflected by the choice to sort the input array nums in reverse (i.e., descending) order. The sort() function in Python is used for this purpose, which typically utilizes a Timsort algorithm, a hybrid sorting algorithm derived from merge sort and insertion sort, to rearrange the elements.

Once sorted, the solution iteratively accumulates the sum s of the nums elements, using a for loop. The accumulated sum s represents the current prefix sum after each iteration. The data structure used here is simple, relying on integer variables to track the sum and the index.

The pseudocode pattern for the solution is as follows:

  1. Sort the input array nums in reverse order.
  2. Initialize a variable s to 0 to keep track of the prefix sums.
  3. Iterate through the sorted array using a for loop with index i and value x: a. Increment s by x. b. If s becomes less than or equal to 0, return i as the score, because it represents the count of positive numbers in the prefix array up to this point.
  4. If the loop completes without s becoming non-positive, return the total length of the array, because this means all prefix sums were positive.

By following these steps, we ensure that the prefix array starts with the largest positive numbers, therefore maximizing the possibility that the sum at every index remains positive. If a negative or zero prefix sum is encountered, the algorithm stops counting, since further sums cannot contribute positively to the score. If negative values occur after positive ones in the sorted array, their impact is minimized by the prefix sums accumulated thus far.

In Python, the implementation looks like this:

1class Solution:
2    def maxScore(self, nums: List[int]) -> int:
3        nums.sort(reverse=True) # Step 1: Sort the array in reverse order.
4        s = 0                   # Step 2: Initialize the [prefix sum](/problems/subarray_sum) as 0.
5        for i, x in enumerate(nums): # Step 3: Iterate through the array.
6            s += x               # Step 3a: Add the current element to the sum.
7            if s <= 0:           # Step 3b: If the sum is non-positive, return the current score.
8                return i
9        return len(nums)         # Step 4: If all prefix sums are positive, return the length of the array.

This implementation is efficient, as it only requires a single pass through the array after sorting, which results in an overall time complexity of O(n log n) due to the sort operation, where n is the number of elements in the input array. The space complexity is O(1), as no additional data structures are needed beyond the input array and temporary variables.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's apply the solution approach to a small example. Consider the integer array nums as [2, -1, 3, -4, 1].

  1. The first step is to sort the array in reverse order. After sorting we get [3, 2, 1, -1, -4].
  2. We initialize a variable s to track the prefix sums, starting with s = 0.
  3. We start iterating through the sorted array and updating s with the current element:
    • In the first iteration i = 0, x = 3. The new value of s is 0 + 3 = 3 which is positive.
    • Next, i = 1, x = 2. Now s becomes 3 + 2 = 5, still positive.
    • For i = 2, x = 1. We update s to 5 + 1 = 6, again positive.
    • Then, i = 3, x = -1. The sum s will be updated to 6 - 1 = 5, which is positive.
    • Lastly, i = 4, x = -4. Updating s gives us 5 - 4 = 1, which remains positive.
  4. Since we don't encounter a sum that is zero or negative, we reach the end of the loop with all positive prefix sums. Therefore, we return the length of the array nums, which is 5.

So, the final score for the array [2, -1, 3, -4, 1] when sorted in descending order would be 5 because all prefix sums of the sorted array [3, 2, 1, -1, -4] are positive.

Applying this algorithm to the example provided shows the step-by-step process and confirms the efficiency of the solution, illustrating that all positive prefix sums were obtained by arranging the numbers in descending order.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxScore(self, card_points: List[int]) -> int:
5        # Sort the list of card points in decreasing order
6        card_points.sort(reverse=True)
7
8        # Initialize the sum of selected card points to zero
9        total_score = 0
10
11        # Iterate over the sorted list of card points
12        for index, points in enumerate(card_points):
13            # Add the points of the current card to the total score
14            total_score += points
15
16            # If at any point the total score becomes non-positive,
17            # return the current number of cards used (index of iteration)
18            if total_score <= 0:
19                return index
20      
21        # If all cards contribute positively to the score (the total score never becomes non-positive),
22        # return the total number of cards as the result
23        return len(card_points)
24
25# Example of usage:
26# solution = Solution()
27# print(solution.maxScore([1, -2, -3, 4, 5])) # Output: 3
28
1import java.util.Arrays; // Import Arrays class for sorting
2
3class Solution {
4    // Method to calculate the maximum score that can be obtained
5    // from the given array nums
6    public int maxScore(int[] nums) {
7        // Sort the array in ascending order
8        Arrays.sort(nums);
9
10        // n stores the total length of the array
11        int n = nums.length;
12
13        // Variable to keep track of the cumulative score
14        long cumulativeScore = 0;
15
16        // Iterate over the array from the last element to the first
17        for (int i = 0; i < n; ++i) {
18            // Add the value of current largest element to cumulativeScore
19            cumulativeScore += nums[n - i - 1];
20
21            // If cumulative score is less than or equal to zero,
22            // the maximum score that can be obtained is the current index i.
23            if (cumulativeScore <= 0) {
24                return i;
25            }
26        }
27        // If the loop completes, then all elements contributed positively,
28        // hence return the total length of the array
29        return n;
30    }
31}
32
1#include <vector>
2#include <algorithm> // include necessary headers
3
4class Solution {
5public:
6    int maxScore(vector<int>& numbers) {
7        // Sorting the array in non-increasing order
8        sort(numbers.rbegin(), numbers.rend());
9      
10        long long sum = 0; // Using long long for potential big sum
11        int count = 0; // This will hold the maximum number of elements contributing to a positive sum
12        int n = numbers.size(); // Get the total count of elements in the numbers vector
13
14        // Iterate over the sorted numbers
15        for (int i = 0; i < n; ++i) {
16            sum += numbers[i]; // Add up the numbers starting from the largest
17          
18            // If the sum goes to zero or negative, return the current count
19            if (sum <= 0) {
20                return count;
21            }
22
23            count++; // Increment count as the current number contributed to a positive sum
24        }
25
26        // If the loop finishes, all elements contribute to a positive sum
27        return count; // Return the total number of elements
28    }
29};
30
1function maxScore(nums: number[]): number {
2    // Sorts the array of numbers in ascending order.
3    nums.sort((a, b) => a - b);
4  
5    // Stores the length of the array for convenience.
6    const lengthOfNums = nums.length;
7  
8    // 'totalScore' will keep track of the aggregated score.
9    let totalScore = 0;
10  
11    // Loop through each number in the array from the end towards the beginning.
12    for (let i = 0; i < lengthOfNums; ++i) {
13        // Accumulate the total score by adding the value of the current largest number.
14        totalScore += nums[lengthOfNums - i - 1];
15      
16        // If the score becomes non-positive, return the current index as the result.
17        if (totalScore <= 0) {
18            return i;
19        }
20    }
21  
22    // If the loop completes without returning, it means all scores were positive,
23    // so return the total count of numbers.
24    return lengthOfNums;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of the code mainly comes from two parts:

  1. Sorting the nums list, and
  2. Iterating through the nums list once.

The sorting can be done in O(n log n) time where n is the length of the list nums. Python uses Timsort for sorting which has this time complexity for the worst case.

After sorting, the code iterates through the list once, which is an O(n) operation.

Combining these parts, the overall time complexity is O(n log n + n), which simplifies to O(n log n) as the log-linear term dominates for large n.

Space Complexity

The space complexity of this code is O(1), or constant space, not counting the input and output. This is because the sorting is done in-place (no extra space is used apart from temporary variables), and the iteration does not use additional space proportional to the input size (only a fixed number of variables s and i are used).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄