Scale Engineer

Find the Score of All Prefixes of an Array

Med
#2400Time: O(n^2) - The outer loop runs `n` times, and the inner loop runs up to `n` times. The total number of operations is proportional to `1 + 2 + ... + n`, which is `n * (n+1) / 2`, resulting in O(n^2) time complexity.Space: O(n) - We need an array of size `n` to store the answer. The space used by other variables is constant, O(1).
Patterns
Prefix Sum
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly follows the problem definition. For each prefix of the input array nums, we calculate its corresponding conversion array and then sum up its elements to get the score. We repeat this process for all prefixes from nums[0..0] to nums[0..n-1].

Algorithm

  • Initialize a long array ans of size n.
  • Loop i from 0 to n-1:
    • Initialize current_score = 0L and max_in_prefix = 0.
    • Loop j from 0 to i to compute the score for the prefix nums[0..i].
    • Inside the inner loop, update max_in_prefix with the maximum value in nums[0..j].
    • Calculate the conversion value (long)nums[j] + max_in_prefix and add it to current_score.
    • After the inner loop, assign ans[i] = current_score.
  • Return ans.

Walkthrough

This approach directly simulates the process described in the problem. We iterate through each possible prefix of the nums array, from nums[0..0] up to nums[0..n-1]. For each prefix, we calculate its score and store it in the result array ans.

To calculate the score for a prefix nums[0..i]:

  1. We initialize a current_score to zero.
  2. We iterate from j = 0 to i. In this inner loop, we are essentially building the conversion array for the prefix nums[0..i] and summing its elements on the fly.
  3. For each j, we first find the maximum value in the subarray nums[0..j]. This can be done by maintaining a running maximum as we iterate through the prefix.
  4. We then calculate the conversion value nums[j] + max(nums[0..j]) and add it to our current_score.
  5. After the inner loop finishes, current_score contains the total score for the prefix nums[0..i], so we set ans[i] = current_score.

Because this method involves a nested loop structure where for each i, we loop i+1 times, the overall time complexity is quadratic.

class Solution {    public long[] findPrefixScore(int[] nums) {        int n = nums.length;        long[] ans = new long[n];         for (int i = 0; i < n; i++) {            long currentScore = 0;            int maxInPrefix = 0;            // Calculate score for prefix nums[0..i]            for (int j = 0; j <= i; j++) {                maxInPrefix = Math.max(maxInPrefix, nums[j]);                long converValue = (long)nums[j] + maxInPrefix;                currentScore += converValue;            }            ans[i] = currentScore;        }        return ans;    }}

Complexity

Time

O(n^2) - The outer loop runs `n` times, and the inner loop runs up to `n` times. The total number of operations is proportional to `1 + 2 + ... + n`, which is `n * (n+1) / 2`, resulting in O(n^2) time complexity.

Space

O(n) - We need an array of size `n` to store the answer. The space used by other variables is constant, O(1).

Trade-offs

Pros

  • Simple to understand and implement as it directly translates the problem statement into code.

Cons

  • Inefficient due to redundant calculations. For each prefix, it recalculates the conversion values for all its sub-prefixes.

  • Will result in a "Time Limit Exceeded" (TLE) error for large inputs as specified in the constraints.

Solutions

class Solution {public  long[] findPrefixScore(int[] nums) {    int n = nums.length;    long[] ans = new long[n];    int mx = 0;    for (int i = 0; i < n; ++i) {      mx = Math.max(mx, nums[i]);      ans[i] = nums[i] + mx + (i == 0 ? 0 : ans[i - 1]);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem