Find the Score of All Prefixes of an Array

Find the Score of All Prefixes of an Array - Problem

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].

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,4]

› Output: [4,7,15,31]

💡 Note: For prefix [2]: conversion=[4], score=4. For prefix [2,1]: max=2, conversion=[4,3], score=7. For prefix [2,1,3]: max=3, conversion=[5,4,6], score=15. For prefix [2,1,3,4]: max=4, conversion=[6,5,7,8], score=26... wait, let me recalculate: conversion=[6,5,7,8], score=6+5+7+8=26. Actually, let me be more careful: For [2,1,3,4], the conversion array is [2+4,1+4,3+4,4+4]=[6,5,7,8], so score=26. Wait, that doesn't match. Let me recalculate properly: For prefix [2,1,3,4] with max=4, conversion[0]=2+4=6, conversion[1]=1+2=3 (max up to index 1 is 2), conversion[2]=3+3=6 (max up to index 2 is 3), conversion[3]=4+4=8. So conversion=[6,3,6,8] and score=23. Actually, let me restart: conversion[i] = nums[i] + max(nums[0..i]). For [2,1,3,4]: conversion[0]=2+2=4, conversion[1]=1+2=3, conversion[2]=3+3=6, conversion[3]=4+4=8. Score=4+3+6+8=21. So for all prefixes: [2]→[4]→4, [2,1]→[4,3]→7, [2,1,3]→[4,3,6]→13, [2,1,3,4]→[4,3,6,8]→21

Example 2 — Increasing Array

$ Input: nums = [1,3,6,4,5]

› Output: [2,8,20,28,38]

💡 Note: For prefix [1]: conversion=[2], score=2. For prefix [1,3]: conversion=[2,6], score=8. For prefix [1,3,6]: conversion=[2,6,12], score=20. Each element gets added to the running maximum at its position.

Example 3 — Decreasing Array

$ Input: nums = [5,4,3,2,1]

› Output: [10,18,24,28,30]

💡 Note: Maximum stays at 5 throughout, so conversion array is [10,9,8,7,6]. Prefix scores are cumulative sums: 10, 19, 27, 34, 40. Wait, let me recalculate: conversion=[5+5,4+5,3+5,2+5,1+5]=[10,9,8,7,6]. Scores: [10], [10,9]→19, [10,9,8]→27, [10,9,8,7]→34, [10,9,8,7,6]→40.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array nums = [2,1,3,4]

Build Conversion

For each prefix, conversion[i] = nums[i] + max(nums[0..i])

Calculate Scores

Sum conversion array values for each prefix

Key Takeaway

🎯 Key Insight: Track running maximum to build conversion values efficiently and accumulate scores incrementally

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to track the running maximum and build prefix scores incrementally. When a new maximum is found, we can efficiently update all previous conversion values. The optimal approach runs in O(n) time with O(1) extra space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	For each prefix, recalculate conversion array and sum from scratch
One Pass Solution	O(n)	O(1)	Calculate all prefix scores in single pass using cumulative approach
Optimized with Running Maximum	O(n²)	O(1)	Track running maximum and cumulative score in single pass

Brute Force — Algorithm Steps

For each prefix position i from 0 to n-1
Find maximum in prefix [0..i]
Build conversion array for this prefix
Sum the conversion array to get score

Visualization

Tap to expand

Step-by-Step Walkthrough

For Each Prefix

Process prefix [0..i] independently

Find Max & Convert

Find max in prefix, build conversion array

Sum Conversion

Sum conversion array to get score

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    long long* ans = (long long*)malloc(numsSize * sizeof(long long));
    
    for (int i = 0; i < numsSize; i++) {
        // Find max in prefix [0..i]
        int maxVal = nums[0];
        for (int j = 1; j <= i; j++) {
            if (nums[j] > maxVal) maxVal = nums[j];
        }
        
        // Calculate conversion array sum for prefix [0..i]
        long long score = 0;
        for (int j = 0; j <= i; j++) {
            // Find max in [0..j] again
            int prefixMax = nums[0];
            for (int k = 1; k <= j; k++) {
                if (nums[k] > prefixMax) prefixMax = nums[k];
            }
            score += nums[j] + prefixMax;
        }
        
        ans[i] = score;
    }
    
    return ans;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    long long* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%lld", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n positions, we find max in O(n) time and sum conversion array in O(n) time

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for calculation, not counting output array

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler