Skip to main content
Talentd

Find the Score of All Prefixes of an Array - Solution & Explanation

MediumArrayPrefix Sum15 min readAsked at: Tiktok
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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 1: Naive Approach Using Loop

This approach involves iterating through each element of the array, calculating the maximum value encountered so far, and then updating the conversion array by adding the current element's value to this maximum. The scores are then calculated by summing up the conversion array up to the current index.

In this solution, we maintain a variable `maxVal` to keep track of the maximum value encountered so far as we loop through the `nums` array. We calculate the prefix score by maintaining a running sum of the conversion values, which is stored in `prefixScore`.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the nums array.
Space Complexity: O(1), since we are using a fixed amount of extra space.

Try this approach in the editor →

Approach 2: Optimized Prefix Sum with Running Max

In this optimized approach, we maintain a running maximum and a conversion sum as we traverse the array. With each element, we update these values and calculate the prefix score directly, reducing unnecessary recalculations.

This C solution efficiently calculates prefix scores while maintaining a running maximum value and conversion sum, enhancing performance by avoiding explicit loop nesting to calculate max values again.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1), aside from the input and output arrays.

Try this approach in the editor →

Approach 3: 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.

Next, we traverse the array nums. For each element nums[i], we update mx, i.e., mx = max(mx, nums[i]), and then update ans[i]. If i = 0, then ans[i] = nums[i] + mx, otherwise ans[i] = nums[i] + mx + ans[i - 1].

The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach Using Loop

Time Complexity: O(n), where n is the length of the nums array.
Space Complexity: O(1), since we are using a fixed amount of extra space.

Optimized Prefix Sum with Running Max

Time Complexity: O(n)
Space Complexity: O(1), aside from the input and output arrays.

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Loop with Prefix Max ScanO(n²)O(1)Useful for understanding the definition of converted values or verifying correctness on small inputs
Running Max + Prefix SumO(n)O(1) extraBest general solution for large arrays and the expected approach in coding interviews

Video Solution

Find the Score of All Prefixes of an Array || leetcode Biweekly 102 || Leetcode Medium • BinaryMagic • 478 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Score of All Prefixes of an Array easy or hard?
The problem is rated Medium because the definition involves two layered concepts: prefix maximum and cumulative scoring. The implementation is straightforward once you realize that the prefix maximum can be maintained incrementally instead of recomputed.
Find the Score of All Prefixes of an Array Python/Java solution
Python and Java implementations follow the same logic: iterate once, maintain runningMax, compute nums[i] + runningMax, and accumulate it into a prefix score. The algorithm runs in O(n) time and uses O(1) extra space besides the output array.
How to solve Find the Score of All Prefixes of an Array in O(n)?
Iterate through the array once while keeping two variables: runningMax and currentScore. Update runningMax = max(runningMax, nums[i]), compute converted = nums[i] + runningMax, then add it to currentScore. Store currentScore in the result array for each index.
What is the best approach for Find the Score of All Prefixes of an Array?
The best approach maintains a running maximum while iterating through the array and computes scores using a prefix sum. At each index, update the maximum seen so far and add nums[i] + runningMax to a cumulative total. This avoids rescanning prefixes and achieves O(n) time with O(1) extra space.
Is Find the Score of All Prefixes of an Array asked at Google/Amazon/Meta?
Prefix-based array problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test recognizing cumulative computations, maintaining running state such as prefix maximums, and optimizing from O(n²) to O(n).
What data structure is used in Find the Score of All Prefixes of an Array?
The solution mainly uses simple array traversal along with two scalar variables: a running maximum and a prefix sum accumulator. No advanced data structures are required, but understanding array iteration and prefix sum techniques is essential.
What is the time complexity of Find the Score of All Prefixes of an Array?
The optimal solution runs in O(n) time because each element is processed exactly once while maintaining a running maximum and cumulative score. A naive implementation that recomputes the maximum for every prefix takes O(n²) time due to repeated scans.

Ready to solve this problem?

Practice Find the Score of All Prefixes of an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Most Beautiful Item for Each Query