#2640

Medium

LeetCode Problem Workspace

Find the Score of All Prefixes of an Array

Compute the score of each prefix in an array using conversion rules while tracking the maximum efficiently for prefix sums.

array prefix sum

Problem Statement

Given a 0-indexed integer array nums, define a conversion array where each element is either the element itself or the maximum of the prefix so far, doubled. The score of a prefix is the sum of its conversion array elements.

Return an array ans where ans[i] represents the score of the prefix nums[0..i]. Ensure the solution accounts for large arrays and keeps track of prefix maximums efficiently.

Examples

Example 1

Input: nums = [2,3,7,5,10]

Output: [4,10,24,36,56]

For the prefix [2], the conversion array is [4] hence the score is 4 For the prefix [2, 3], the conversion array is [4, 6] hence the score is 10 For the prefix [2, 3, 7], the conversion array is [4, 6, 14] hence the score is 24 For the prefix [2, 3, 7, 5], the conversion array is [4, 6, 14, 12] hence the score is 36 For the prefix [2, 3, 7, 5, 10], the conversion array is [4, 6, 14, 12, 20] hence the score is 56

Example 2

Input: nums = [1,1,2,4,8,16]

Output: [2,4,8,16,32,64]

For the prefix [1], the conversion array is [2] hence the score is 2 For the prefix [1, 1], the conversion array is [2, 2] hence the score is 4 For the prefix [1, 1, 2], the conversion array is [2, 2, 4] hence the score is 8 For the prefix [1, 1, 2, 4], the conversion array is [2, 2, 4, 8] hence the score is 16 For the prefix [1, 1, 2, 4, 8], the conversion array is [2, 2, 4, 8, 16] hence the score is 32 For the prefix [1, 1, 2, 4, 8, 16], the conversion array is [2, 2, 4, 8, 16, 32] hence the score is 64

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Track Prefix Maximum

Iterate through nums while maintaining the maximum element of the current prefix. Update the conversion value for each element as the maximum of the current element and the prefix maximum, then double it.

Compute Running Score

As you process each element, add its conversion value to a running total. Store this total in the result array for each prefix to ensure correct prefix scores.

Linear Time Optimization

Avoid nested loops by updating the prefix maximum and running sum in one pass. This guarantees O(n) time complexity, essential for arrays up to length 10^5.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is processed once. Space complexity is O(n) for storing the prefix scores array. The solution uses constant extra space beyond the output.

What Interviewers Usually Probe

Expecting you to track a running maximum rather than recomputing for each prefix.
Looking for O(n) linear time solution instead of nested prefix loops.
Observing if you handle large numbers and long arrays correctly.

Common Pitfalls or Variants

Common pitfalls

Recomputing the maximum for every prefix instead of maintaining a running maximum.
Incorrectly summing conversion values, missing doubling or prefix rules.
Failing to handle edge cases where nums has one element or all identical values.

Follow-up variants

Compute the minimum instead of maximum for each prefix and sum conversion values.
Return only the final total score of the entire array instead of all prefixes.
Apply a similar conversion logic for a 2D matrix row-wise using prefix maximums.

FAQ

What is the main pattern in Find the Score of All Prefixes of an Array?

The core pattern is array plus prefix sum, using a running prefix maximum to compute conversion values efficiently.

Can this solution handle the maximum constraints of nums length 10^5?

Yes, maintaining the prefix maximum and running sum allows O(n) time computation without exceeding memory limits.

Do I need extra space besides the output array?

No, the algorithm only needs variables for the running sum and prefix maximum; the rest is stored in the result array.

How is the conversion array calculated for each prefix?

Each element in the conversion array is the maximum of the prefix so far or the element itself, then doubled.

What is a common mistake when implementing this problem?

A frequent error is recalculating the prefix maximum repeatedly or missing the doubling rule in conversion, causing wrong prefix scores.

terminal

Solution

Solution 1: Prefix Sum

We use a variable $mx$ to record the maximum value of the first $i$ elements in the array $nums$, and use an array $ans[i]$ to record the score of the first $i$ elements in the array $nums$.

1

2

3

4

5

6

7

8

9

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        mx = 0
        for i, x in enumerate(nums):
            mx = max(mx, x)
            ans[i] = x + mx + (0 if i == 0 else ans[i - 1])
        return ans

Continue Practicing

#2615 sum of distances #2602 minimum operations to make all array elements equal #2680 maximum or