2640. Find the Score of All Prefixes of an Array

MediumArrayPrefix Sum
Leetcode Link

Problem Description

The problem provides us with an array arr. We are asked to calculate a "conversion" array based on this original array. The conversion array conver is defined such that each of its elements conver[i] is the sum of arr[i] and the maximum value in the subarray arr[0..i], which includes all elements from the start of the array up to the current index i.

In addition to this, we need to find the "score" of each prefix of the original array arr. A prefix arr[0..i] includes all elements in the array from index 0 to index i. The score of a prefix is the sum of all the values in its conversion array. So for each prefix, we calculate its score and store it in an output array ans, where ans[i] equals the score of the prefix arr[0..i].

To summarize, the problem is asking us to:

  1. For each index i in the input array nums, calculate the conversion array conver as conver[i] = nums[i] + max(nums[0..i]).
  2. Calculate the score for each prefix nums[0..i] as the sum of conver[0..i].
  3. Return an array ans where each ans[i] is the score of the prefix nums[0..i].

Intuition

To approach this problem, we need to iterate through the input array nums to build both the conversion array conver and keep track of the sum for calculating the score simultaneously.

  1. Iterating Through the Array: As we iterate through nums, we keep track of the maximum value found so far; this value represents max(nums[0..i]) at each step.

  2. Computing the Conversion Values: For each index i, we simply add nums[i] to this maximum value to get our current conver[i].

  3. Accumulating the Scores: To calculate the score of the prefix, we also need to accumulate the scores obtained from previous prefixes. This can be done by maintaining a running sum of the conversion values as we proceed. The score up to the current prefix is the sum of the current conver[i] and the score of the previous prefix (which we have been accumulating). For the first element in the array, since there is no previous prefix, the score is simply nums[0] + max(nums[0]), which is just nums[0] * 2.

  4. Handling the First Element: We handle the first element as a special case, our code checks if i is 0 and, if so, it doesn't add the score of the previous prefix (since there is none) but simply the nums[i] * 2.

This process ensures that we only need to traverse the array once. We do not need to recalculate the maximum or the sum for each prefix from scratch.

The code implements these steps through the following logic:

  • We initialize the maximum value mx as 0, and we start with an answer array ans of zeros.
  • We iterate through the input array nums, update mx to the maximum value so far, and calculate ans[i].
  • Finally, return the populated ans array as the result.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Solution Approach

The implementation uses a simple for loop to iterate over the elements of the input array nums, while maintaining two key pieces of information: the maximum value encountered so far (mx) and the accumulated score for each prefix (ans[i]). Here's a detailed walkthrough of the implementation:

  1. Initialization: Before the loop starts, an array ans of zeros with the same length as nums is created to store the scores for each prefix. The variable mx is initialized to 0 to keep track of the maximum value seen at each step during the iteration.

  2. Enumeration: The code uses enumerate to iterate over nums, giving us both the index i and the value x at each step. The enumerate function is a common pattern when both the element and its index are needed.

  3. Updating the Maximum Value: As we traverse the array, the maximum value so far is updated by comparing the current value x with the last recorded maximum mx and assigning the greater of the two to mx.

    1mx = max(mx, x)

  4. Calculation of Conversion Values and Accumulating Scores: For each index i, the current conversion value is computed as x + mx. The score of the current prefix is the sum of this conversion value and the score of the previous prefix, which we have stored in ans[i - 1]. Since ans is initialized to have zeros, when i is 0, ans[i - 1] does not exist and we handle this by adding 0 instead.

    1ans[i] = x + mx + (0 if i == 0 else ans[i - 1])

  5. Data Structures: The solution uses two main data structures: a list ans to hold the scores of the prefixes and a simple variable mx to keep track of the running maximum. No additional complex data structures are required to implement this solution effectively.

  6. Algorithm Complexity: The time complexity of this implementation is O(n) where n is the length of the nums because it makes a single pass through the input array. The space complexity is also O(n) due to the space used by the ans array. This efficient use of time and space makes the solution optimal for this problem.

In conclusion, the solution leverages a single linear scan, a common algorithmic pattern used to minimize the time complexity by avoiding nested loops or recursive calls that could potentially increase the complexity. It efficiently computes the required maximal values and accumulated sums in one iteration by using constant space (apart from the output array) and in linear time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the following input array nums:

1nums = [1, 3, 5, 2]

  1. Initialization: Before we begin, we create an array ans of zeros with the same length as nums to store the scores for each prefix. Also, we initialize the variable mx to 0.

    1ans = [0, 0, 0, 0]  // to hold the results
2mx = 0  // maximum value encountered so far

  2. Processing the First Element: We start with the element at index 0 which is 1.

    1mx = max(mx, nums[0])  // mx becomes 1, since max(0, 1) is 1
2ans[0] = nums[0] + mx  // ans[0] becomes 1 + 1 = 2

    After processing the first element, our array ans and mx variable are updated as:

    1ans = [2, 0, 0, 0]
2mx = 1

  3. Processing the Second Element: Moving on to the element at index 1 which is 3.

    1mx = max(mx, nums[1])  // mx is updated to 3
2ans[1] = nums[1] + mx + ans[0]  // ans[1] is 3 + 3 + 2 = 8

    Now ans and mx are:

    1ans = [2, 8, 0, 0]
2mx = 3

  4. Processing the Third Element: For the element at index 2 which is 5.

    1mx = max(mx, nums[2])  // mx stays at 5
2ans[2] = nums[2] + mx + ans[1]  // ans[2] is 5 + 5 + 8 = 18

    The updated ans and mx:

    1ans = [2, 8, 18, 0]
2mx = 5

  5. Processing the Last Element: Finally, for the element at index 3 which is 2.

    1mx = max(mx, nums[3])  // mx stays at 5, since max(5, 2) is 5
2ans[3] = nums[3] + mx + ans[2]  // ans[3] is 2 + 5 + 18 = 25

    We have our final ans array:

    1ans = [2, 8, 18, 25]

As a result, for each prefix of the array nums, we have calculated the corresponding scores and stored them in the ans array. The scores indicate the sum of the values in the conversion array for each prefix. Thus, the final output for the input nums = [1, 3, 5, 2] is [2, 8, 18, 25]. This walkthrough demonstrates how our approach effectively processes each element of the input array to compute the scores in a step-by-step manner, updating the maximum value encountered and accumulating the scores for each prefix.

Solution Implementation

1class Solution:
2    def findPrefixScore(self, nums: List[int]) -> List[int]:
3        # Get the number of elements in the input list 'nums'.
4        num_elements = len(nums)
5      
6        # Initialize a result list 'prefix_scores' with zeros of the same length as 'nums'.
7        prefix_scores = [0] * num_elements
8      
9        # Initialize a variable 'max_prefix' that will hold the maximum prefix score so far.
10        max_prefix = 0
11      
12        # Iterate over each number in 'nums' using its index and value.
13        for index, number in enumerate(nums):
14            # Update 'max_prefix' with the maximum between 'max_prefix' and the current number.
15            max_prefix = max(max_prefix, number)
16          
17            # Compute the current prefix score.
18            # If it's the first element, then 'max_prefix' is the current number.
19            # Otherwise, it's the sum of the maximum prefix so far, the current number,
20            # and the previous prefix score.
21            if index == 0:
22                prefix_scores[index] = number + max_prefix
23            else:
24                prefix_scores[index] = number + max_prefix + prefix_scores[index - 1]
25              
26        # Return the resulting list of prefix scores.
27        return prefix_scores
28
1class Solution {
2    // Method to find the prefix score for each number in the array
3    public long[] findPrefixScore(int[] nums) {
4        // n holds the length of the input array
5        int n = nums.length;
6
7        // Initialize the answer array with the same length as the input array
8        long[] answer = new long[n];
9
10        // Initialize a variable to keep track of the maximum value seen so far
11        int max = 0;
12
13        // Iterate over the input array to compute the prefix scores
14        for (int i = 0; i < n; ++i) {
15            // Update max if the current number is greater than the current max
16            max = Math.max(max, nums[i]);
17
18            // Calculate the prefix score for the current index i
19            // It is the sum of the current number, the maximum number seen so far,
20            // and the previous prefix score (if not the first element)
21            answer[i] = nums[i] + max + (i == 0 ? 0 : answer[i - 1]);
22        }
23
24        // Return the computed prefix scores
25        return answer;
26    }
27}
28
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the prefix score of a given array of integers
7    vector<long long> findPrefixScore(vector<int>& nums) {
8        int size = nums.size(); // Get the size of the input vector.
9        vector<long long> prefixScore(size); // Initialize the result vector to store prefix scores.
10
11        int maxElement = 0; // Variable to keep track of the maximum element in the prefix.
12
13        // Iterate over the array to calculate prefix scores
14        for (int i = 0; i < size; ++i) {
15            maxElement = max(maxElement, nums[i]); // Update the maximum element in the prefix.
16          
17            // The prefix score of the current position is the sum of the current element,
18            // the maximum element seen so far, and the previous prefix score (if not the first element).
19            prefixScore[i] = nums[i] + maxElement + (i == 0 ? 0 : prefixScore[i - 1]);
20        }
21
22        return prefixScore; // Return the final computed prefix scores.
23    }
24};
25
1function findPrefixScore(nums: number[]): number[] {
2    const numsLength = nums.length; // Length of the input array.
3    const prefixScores: number[] = new Array(numsLength); // Array to hold the prefix scores.
4
5    let maxNum: number = 0; // Variable to keep track of the maximum number encountered so far.
6
7    // Iterate through the array of numbers.
8    for (let index = 0; index < numsLength; ++index) {
9        // Update the maximum number if the current number is greater.
10        maxNum = Math.max(maxNum, nums[index]);
11
12        // Calculate the prefix score:
13        // It's the sum of the current number, the maximum number so far,
14        // and the prefix score of the previous element (if it exists).
15        prefixScores[index] = nums[index] + maxNum;
16        if (index > 0) {
17            prefixScores[index] += prefixScores[index - 1];
18        }
19    }
20
21    // Return the array of calculated prefix scores.
22    return prefixScores;
23}
24
Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Time Complexity

The provided code calculates the prefix score for a list of integers. The time complexity can be broken down as follows:

  • There is a single loop that iterates over the list nums, which contains n elements.
  • Inside the loop, the code performs constant time operations, including assignment, the max function on two integers, and arithmetic operations.

As a result, the loop will have n iterations, and each iteration consists of constant time operations. This gives the time complexity as O(n).

Space Complexity

Analyzing the space complexity:

  • The list ans is initialized with the same length as nums, which adds O(n) space.
  • The variables n, mx, and i use constant space (O(1)).
  • No additional data structures or recursive calls that use space proportional to the size of the input.

Thus, the space complexity is O(n) primarily due to the space required for the ans list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫