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,13,21]

💡 Note: For prefix [2]: max=2, conversion=[2+2]=[4], score=4. For prefix [2,1]: conversion=[2+2,1+2]=[4,3], score=7. For prefix [2,1,3]: conversion=[2+2,1+2,3+3]=[4,3,6], score=13. For prefix [2,1,3,4]: conversion=[2+2,1+2,3+3,4+4]=[4,3,6,8], score=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,19,27,34,40]

💡 Note: Maximum stays at 5 throughout, so conversion array for each prefix: [5]→[10], [5,4]→[10,9], [5,4,3]→[10,9,8], etc. Prefix scores are cumulative sums of conversion arrays.

Constraints

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

Visualization

Tap to expand

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

✓ Two Pointers

⏱️ Time: N/A Space: N/A

Brute Force

⏱️ Time: O(n³) Space: O(1)

For each position i, we iterate through the prefix [0..i] to find the maximum, build the conversion array, and sum it up to get the score. This approach recalculates everything for each prefix.

One Pass Solution

⏱️ Time: O(n) Space: O(1)

The most efficient approach uses the fact that when we extend from prefix i-1 to prefix i, we can reuse previous computations. The new score equals the previous score plus the new conversion value plus all previous conversion values that get the new maximum added.

Optimized with Running Maximum

⏱️ Time: O(n²) Space: O(1)

Instead of recalculating everything, we maintain a running maximum as we iterate through the array. For each position, we can directly compute the conversion value using the current running max and add it to our cumulative score.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

static int nums[100000];
static long long result[100000];

int main() {
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    // Parse the input array [num1,num2,...]
    int n = 0;
    char* ptr = line;
    
    // Skip to first '['
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') ptr++;
    
    // Parse numbers
    while (*ptr && *ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        
        // Parse number (handle negative)
        int sign = 1;
        if (*ptr == '-') {
            sign = -1;
            ptr++;
        }
        
        int num = 0;
        while (*ptr >= '0' && *ptr <= '9') {
            num = num * 10 + (*ptr - '0');
            ptr++;
        }
        
        nums[n++] = sign * num;
    }
    
    // Calculate scores for each prefix
    long long running_score = 0;
    int current_max = nums[0];
    
    for (int i = 0; i < n; i++) {
        // Update max for current prefix
        if (nums[i] > current_max) {
            current_max = nums[i];
        }
        
        // Add to running score: nums[i] + max_so_far
        running_score += (long long)nums[i] + current_max;
        result[i] = running_score;
    }
    
    // Output result
    printf("[");
    for (int i = 0; i < n; i++) {
        if (i > 0) printf(",");
        printf("%lld", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ 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