LeetCode 2640 - Find the Score of All Prefixes of an Array

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem requires calculating a score for all prefixes of an array. Given an integer array nums, we first define a conversion array for any prefix of nums. The conversion array is constructed by adding each element in the prefix to the maximum element seen so far in that prefix. The score of a prefix is the sum of its conversion array. We need to return an array ans where ans[i] is the score of the prefix nums[0..i].

The input array nums is 0-indexed, and its length can be up to 100,000 with elements up to 1 billion. This implies that any solution must be linear in time to handle the largest input efficiently. Large numbers also suggest that we need to use a numeric type that can handle sums exceeding 32-bit integers.

Important observations include: the prefix structure allows us to incrementally calculate the score, and keeping track of the current maximum value avoids repeated scanning of the array. Edge cases to consider are arrays of length 1, arrays where all elements are equal, strictly increasing arrays, and strictly decreasing arrays.

Approaches

The brute-force approach iterates over each prefix and explicitly constructs the conversion array by scanning the prefix for the maximum. Then, it sums the conversion array. While correct, this approach has a time complexity of $O(n^2)$ and will fail for large inputs.

The optimal approach leverages incremental computation. Instead of recomputing the prefix maximum each time, we maintain a variable current_max as we iterate. For each element nums[i], the conversion value is nums[i] + current_max, and the prefix score is the previous prefix score plus this conversion value. This reduces the time complexity to O(n) while keeping space complexity linear for the output.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Computes prefix maximum and conversion sum for each prefix
Optimal	O(n)	O(n)	Maintains running prefix sum and max to compute scores incrementally

Algorithm Walkthrough

Initialize an empty list ans to store the prefix scores.
Initialize current_max as 0 to track the maximum element seen so far.
Initialize prefix_score as 0 to track the cumulative score for the current prefix.
Iterate through each element num in nums:
Update current_max as the maximum of current_max and num.
Calculate the conversion value conversion = num + current_max.
Update prefix_score by adding conversion.
Append prefix_score to ans.
After the loop, return ans.

Why it works: At each step, current_max correctly stores the maximum of the prefix. Adding num to current_max gives the current conversion value, and summing these incrementally ensures that the prefix scores are correctly accumulated.

Python Solution

from typing import List

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        ans: List[int] = []
        current_max: int = 0
        prefix_score: int = 0

        for num in nums:
            current_max = max(current_max, num)
            conversion = num + current_max
            prefix_score += conversion
            ans.append(prefix_score)

        return ans

The Python implementation follows the algorithm closely. current_max keeps the largest number seen, conversion computes the conversion array value, and prefix_score accumulates the sum for the prefix. Each prefix score is appended to ans, which is returned at the end.

Go Solution

func findPrefixScore(nums []int) []int64 {
    n := len(nums)
    ans := make([]int64, n)
    var currentMax int64 = 0
    var prefixScore int64 = 0

    for i, num := range nums {
        num64 := int64(num)
        if num64 > currentMax {
            currentMax = num64
        }
        conversion := num64 + currentMax
        prefixScore += conversion
        ans[i] = prefixScore
    }

    return ans
}

In Go, we must handle 64-bit integers explicitly to avoid overflow since nums[i] can be as large as $10^9$ and the sum can exceed 32-bit limits. The rest of the logic mirrors the Python solution. Slice ans stores prefix scores directly, and running totals are maintained using currentMax and prefixScore.

Worked Examples

Example 1: nums = [2,3,7,5,10]

i	num	current_max	conversion	prefix_score	ans
0	2	2	4	4	[4]
1	3	3	6	10	[4,10]
2	7	7	14	24	[4,10,24]
3	5	7	12	36	[4,10,24,36]
4	10	10	20	56	[4,10,24,36,56]

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

i	num	current_max	conversion	prefix_score	ans
0	1	1	2	2	[2]
1	1	1	2	4	[2,4]
2	2	2	4	8	[2,4,8]
3	4	4	8	16	[2,4,8,16]
4	8	8	16	32	[2,4,8,16,32]
5	16	16	32	64	[2,4,8,16,32,64]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through `nums` to calculate prefix scores
Space	O(n)	Output array `ans` stores n prefix scores

The solution iterates over nums once, updating a running maximum and prefix sum, which ensures linear time complexity. Only the output array contributes to extra space usage.

Test Cases

# Provided examples
assert Solution().findPrefixScore([2,3,7,5,10]) == [4,10,24,36,56]  # example 1
assert Solution().findPrefixScore([1,1,2,4,8,16]) == [2,4,8,16,32,64]  # example 2

# Edge cases
assert Solution().findPrefixScore([1]) == [2]  # single element
assert Solution().findPrefixScore([10,10,10]) == [20,40,60]  # all equal elements
assert Solution().findPrefixScore([3,2,1]) == [6,10,12]  # decreasing order
assert Solution().findPrefixScore([1,2,3,4,5]) == [2,6,12,20,30]  # increasing order
assert Solution().findPrefixScore([1000000000]*5) == [2000000000,4000000000,6000000000,8000000000,10000000000]  # large numbers

Test	Why
[2,3,7,5,10]	Standard example to verify prefix calculation
[1,1,2,4,8,16]	Increasing powers of 2 for exponential score growth
[1]	Single element prefix, smallest array
[10,10,10]	All elements equal to check repeated maximum handling
[3,2,1]	Decreasing values to ensure max persists correctly
[1,2,3,4,5]	Increasing values to check incremental max updates
[1000000000]*5	Large numbers to test integer handling and overflow

Edge Cases

One important edge case is single-element arrays, where the prefix and conversion array contain just one element. The algorithm handles this naturally by initializing current_max and prefix_score.

Another edge case is arrays with all identical elements, which could trip naive maximum calculations if not updated correctly. Here, current_max remains the same, and conversion values double each element, which our solution handles properly.

The third edge case involves large numbers, as the sum of conversion arrays can exceed 32-bit integer limits. In Python, integers are arbitrary-precision, but in Go, we explicitly use int64 to prevent overflow. Our solution accounts for this by converting inputs to 64-bit integers