Find the Score of All Prefixes of an Array solution and explanation
9 more videos on this problem
Find the Score of All Prefixes of an Array || leetcode Biweekly 102 || Leetcode MediumBinaryMagic · 4:42 · 478 views
Find the Score of All Prefixes of an Array - Leetcode 2640 - PythonAlgorithms Casts · 4:32 · 272 views
6334. Find the Score of All Prefixes of an Array | Leetcode Biweekly Contest 102 | SolutionCode|JAVAOptimization · 4:05 · 271 views
Leetcode Biweekly Contest 102 | PROBLEM 2639 , 2640, 2641 | GREEDY | TREEcode Explainer · 18:30 · 210 views
Leetcode 2640. Find the Score of All Prefixes of an ArrayElite Code · 22:52 · 184 views
2640. Find the Score of All Prefixes of an Array (Leetcode Medium)Programming Live with Larry · 3:13 · 181 views
Leetcode BiWeekly contest 102 - Medium - Find the Score of All Prefixes of an ArrayPrakhar Agrawal · 4:03 · 129 views
LeetCode 2640 | Find the Score of All Prefixes of An Array | LeetcodeR Sai Siddhu · 15:24 · 108 views
Find the Score of All Prefixes of an Array | Leetcode Biweekly Contest 102 | SolutionCode|C++Apni Engineer · 8:42 · 96 views
Biweekly Contest 102 | 6334. Find the Score of All Prefixes of an Array | LeetCode | JAVANiharika Mishra · 0:21 · 81 views
The problem
We define the conversion array conver of an array arr as follows:
conver[i] = arr[i] + max(arr[0..i])wheremax(arr[0..i])is the maximum value ofarr[j]over0 <= 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] <= 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.
def find_prefix_scores(nums):
max_val = nums[0]
prefix_score = 0
result = []
for num in nums:
max_val = max(max_val, num)
prefix_score += num + max_val
result.append(prefix_score)
return result
# Example usage
nums = [2, 3, 7, 5, 10]
result = find_prefix_scores(nums)
print(result)import java.util.Arrays;
public class PrefixScores {
public static int[] findPrefixScores(int[] nums) {
int maxVal = nums[0];
int prefixScore = 0;
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
maxVal = Math.max(maxVal, nums[i]);
prefixScore += nums[i] + maxVal;
result[i] = prefixScore;
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3, 7, 5, 10};
int[] result = findPrefixScores(nums);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> findPrefixScores(std::vector<int>& nums) {
int maxVal = nums[0];
int prefixScore = 0;
std::vector<int> result(nums.size());
for (size_t i = 0; i < nums.size(); ++i) {
maxVal = std::max(maxVal, nums[i]);
prefixScore += nums[i] + maxVal;
result[i] = prefixScore;
}
return result;
}
int main() {
std::vector<int> nums = {2, 3, 7, 5, 10};
std::vector<int> result = findPrefixScores(nums);
for (int score : result) {
std::cout << score << " ";
}
return 0;
}function findPrefixScores(nums) {
let maxVal = nums[0];
let prefixScore = 0;
const result = [];
for (let num of nums) {
maxVal = Math.max(maxVal, num);
prefixScore += num + maxVal;
result.push(prefixScore);
}
return result;
}
const nums = [2, 3, 7, 5, 10];
console.log(findPrefixScores(nums));#include <stdio.h>
#include <string.h>
void findPrefixScores(int* nums, int numsSize, int* result) {
int maxVal = nums[0];
int prefixScore = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > maxVal) maxVal = nums[i];
prefixScore += nums[i] + maxVal;
result[i] = prefixScore;
}
}
int main() {
int nums[] = {2, 3, 7, 5, 10};
int result[5];
findPrefixScores(nums, 5, result);
for (int i = 0; i < 5; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
class PrefixScores {
static int[] FindPrefixScores(int[] nums) {
int maxVal = nums[0];
int prefixScore = 0;
int[] result = new int[nums.Length];
for (int i = 0; i < nums.Length; i++) {
maxVal = Math.Max(maxVal, nums[i]);
prefixScore += nums[i] + maxVal;
result[i] = prefixScore;
}
return result;
}
static void Main() {
int[] nums = {2, 3, 7, 5, 10};
int[] result = FindPrefixScores(nums);
Console.WriteLine(string.Join(" ", result));
}
}The Python solution uses a list to store result and updates both the maximum value and prefix score as it iterates over the input list nums.
Time Complexity: O(n)
Space Complexity: O(n), needed for the output list.
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.
def find_prefix_scores(nums):
max_val = nums[0]
conversion_sum = nums[0] + nums[0]
result = [conversion_sum]
for num in nums[1:]:
max_val = max(max_val, num)
conversion_sum += num + max_val
result.append(conversion_sum)
return result
# Example usage
nums = [2, 3, 7, 5, 10]
result = find_prefix_scores(nums)
print(result)import java.util.Arrays;
public class PrefixScores {
public static int[] findPrefixScores(int[] nums) {
int maxVal = nums[0];
int conversionSum = nums[0] + nums[0];
int[] result = new int[nums.length];
result[0] = conversionSum;
for (int i = 1; i < nums.length; i++) {
maxVal = Math.max(maxVal, nums[i]);
conversionSum += nums[i] + maxVal;
result[i] = conversionSum;
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3, 7, 5, 10};
int[] result = findPrefixScores(nums);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
std::vector<int> findPrefixScores(const std::vector<int>& nums) {
int maxVal = nums[0];
int conversionSum = nums[0] + nums[0];
std::vector<int> result(nums.size());
result[0] = conversionSum;
for (size_t i = 1; i < nums.size(); ++i) {
maxVal = std::max(maxVal, nums[i]);
conversionSum += nums[i] + maxVal;
result[i] = conversionSum;
}
return result;
}
int main() {
std::vector<int> nums = {2, 3, 7, 5, 10};
auto result = findPrefixScores(nums);
for (int score : result) {
std::cout << score << " ";
}
return 0;
}function findPrefixScores(nums) {
let maxVal = nums[0];
let conversionSum = nums[0] + nums[0];
const result = [conversionSum];
for (let i = 1; i < nums.length; i++) {
maxVal = Math.max(maxVal, nums[i]);
conversionSum += nums[i] + maxVal;
result.push(conversionSum);
}
return result;
}
const nums = [2, 3, 7, 5, 10];
console.log(findPrefixScores(nums));#include <stdio.h>
void findPrefixScores(int* nums, int numsSize, int* result) {
int maxVal = nums[0];
int conversionSum = nums[0] + nums[0];
result[0] = conversionSum;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > maxVal) maxVal = nums[i];
conversionSum += nums[i] + maxVal;
result[i] = conversionSum;
}
}
int main() {
int nums[] = {2, 3, 7, 5, 10};
int result[5];
findPrefixScores(nums, 5, result);
for (int i = 0; i < 5; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
class PrefixScores {
static int[] FindPrefixScores(int[] nums) {
int maxVal = nums[0];
int conversionSum = nums[0] + nums[0];
int[] result = new int[nums.Length];
result[0] = conversionSum;
for (int i = 1; i < nums.Length; i++) {
maxVal = Math.Max(maxVal, nums[i]);
conversionSum += nums[i] + maxVal;
result[i] = conversionSum;
}
return result;
}
static void Main() {
int[] nums = {2, 3, 7, 5, 10};
int[] result = FindPrefixScores(nums);
Console.WriteLine(string.Join(" ", result));
}
}The Python implementation captures all crucial elements of an efficient solution by holding updated sums, achieving results without extensive reshuffling or recalculations.
Time Complexity: O(n)
Space Complexity: O(n), for the resultant list.
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).
function findPrefixScore(nums: number[]): number[] {
const n = nums.length;
const ans: number[] = new Array(n);
let mx: number = 0;
for (let i = 0; i < n; ++i) {
mx = Math.max(mx, nums[i]);
ans[i] = nums[i] + mx + (i === 0 ? 0 : ans[i - 1]);
}
return ans;
}func findPrefixScore(nums []int) []int64 {
n := len(nums)
ans := make([]int64, n)
mx := 0
for i, x := range nums {
mx = max(mx, x)
ans[i] = int64(x + mx)
if i > 0 {
ans[i] += ans[i-1]
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach Using Loop | Time Complexity: O(n) |
| Optimized Prefix Sum with Running Max | Time Complexity: O(n) |
| Prefix Sum | – |
Complexity analysis
| 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 |
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.