Watch 10 video solutions for Find the Score of All Prefixes of an Array, a medium level problem involving Array, Prefix Sum. This walkthrough by BinaryMagic has 470 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We define the conversion array conver of an array arr as follows:
conver[i] = arr[i] + max(arr[0..i]) where max(arr[0..i]) is the maximum value of arr[j] over 0 <= j <= i.We also define the score of an array arr as the sum of the values of the conversion array of arr.
Given a 0-indexed integer array nums of length n, return an array ans of length n where ans[i] is the score of the prefix nums[0..i].
Example 1:
Input: nums = [2,3,7,5,10] Output: [4,10,24,36,56] Explanation: 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] Explanation: 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 <= 1051 <= nums[i] <= 109Problem Overview: You receive an integer array nums. For every prefix nums[0..i], compute a converted value where each element becomes nums[i] + max(nums[0..i]). The score of a prefix is the cumulative sum of these converted values up to that index. The task is to return the score for every prefix.
Approach 1: Naive Approach Using Loop (Time: O(n²), Space: O(1))
For each index i, scan the prefix nums[0..i] to find the maximum value. Use that maximum to compute the converted value nums[i] + maxPrefix. Maintain a running total to build the score array. This approach repeatedly recomputes the prefix maximum, which costs O(i) work per step and leads to O(n²) total time.
The logic is straightforward and useful for understanding the definition of the conversion array. However, repeated maximum scans make it inefficient for large inputs. This version mainly helps validate correctness before optimizing.
Approach 2: Optimized Prefix Sum with Running Max (Time: O(n), Space: O(1) extra)
The key observation: the prefix maximum does not need to be recomputed each time. Maintain a variable runningMax that stores the largest value seen so far while iterating once through the array. At index i, update runningMax = max(runningMax, nums[i]). The converted value becomes nums[i] + runningMax.
Next, accumulate scores using a running prefix sum. Maintain currentScore and add the converted value at each step. Append that value to the result array. This single pass simultaneously maintains the prefix maximum and the cumulative score, reducing the total work to O(n).
This approach combines two classic techniques: tracking a running maximum from array traversal and maintaining cumulative totals with a prefix sum. Because every element is processed exactly once, it scales efficiently even for large inputs.
Recommended for interviews: The optimized running-max approach is what interviewers expect. It shows you recognize redundant work in repeated prefix scans and replace it with a maintained state variable. Mentioning the naive O(n²) idea first demonstrates understanding of the problem definition, but implementing the O(n) solution proves you can optimize using prefix sums and incremental computation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Loop with Prefix Max Scan | O(n²) | O(1) | Useful for understanding the definition of converted values or verifying correctness on small inputs |
| Running Max + Prefix Sum | O(n) | O(1) extra | Best general solution for large arrays and the expected approach in coding interviews |