Leetcode 2640: Find the Score of All Prefixes of an Array

Input: The input consists of an integer array `nums` of length `n` where 1 <= n <= 10^5 and 1 <= nums[i] <= 10^9.

Example: nums = [4, 6, 2, 9]

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

Output: Return an integer array `ans` of length `n`, where each `ans[i]` represents the score of the prefix `nums[0..i]`.

Example: Output: [8, 18, 26, 44]

Constraints:

• The output array will have exactly `n` elements, each corresponding to the score of the prefix.

Goal: The goal is to compute the score of each prefix of the array. For each index `i`, compute the conversion array element as the sum of `nums[i]` and the maximum value encountered in the array up to that index.

Steps:

• Step 1: Initialize a variable to keep track of the maximum value encountered so far in the array.

• Step 2: Iterate over the array, and for each element at index `i`, calculate its conversion array value by adding `nums[i]` to the maximum value up to that point.

• Step 3: Maintain a running sum of the conversion array values to store the score of the prefix `nums[0..i]`.

• Step 4: Return the array of scores for all prefixes.

Goal: Ensure that the solution can efficiently handle large arrays up to 10^5 elements.

Steps:

• The solution must be efficient for large inputs, with time complexity approximately O(n).

Assumptions:

• The array `nums` is non-empty and contains positive integers within the specified range.

• Input: nums = [4, 6, 2, 9]

• Explanation: For the prefix [4], the conversion array is [8] with score 8. For the prefix [4, 6], the conversion array is [8, 12] with score 18. For the prefix [4, 6, 2], the conversion array is [8, 12, 14] with score 26. For the prefix [4, 6, 2, 9], the conversion array is [8, 12, 14, 20] with score 44.

• Input: nums = [1, 2, 3]

• Explanation: For the prefix [1], the conversion array is [2] with score 2. For the prefix [1, 2], the conversion array is [2, 4] with score 6. For the prefix [1, 2, 3], the conversion array is [2, 4, 6] with score 12.

Approach: The problem can be solved by iterating through the array while maintaining the maximum element encountered up to the current index. We can calculate the conversion array value on the fly and maintain a running sum for each prefix score.

Observations:

• The problem asks us to compute a running score for each prefix of the array, so a straightforward approach would be to maintain the maximum of the prefix as we iterate through the array.

• By keeping track of the maximum element encountered so far, we can efficiently compute the conversion array for each prefix and accumulate the score in a single pass.

Steps:

• Step 1: Initialize a variable `max_value` to store the maximum value encountered so far in the array.

• Step 2: Initialize a variable `prefix_score` to store the cumulative score of the prefixes.

• Step 3: Iterate over the array, for each element at index `i`, compute its conversion value and add it to the running score.

• Step 4: Store the cumulative score at each index `i` in the result array `ans`.

Empty Inputs:

• If the input array is empty, the result should also be an empty array.

Large Inputs:

• The solution should handle large arrays with up to 100,000 elements efficiently.

Special Values:

• When all elements are the same, the result will follow a predictable pattern where the score increases steadily based on the fixed maximum value.

Constraints:

• The algorithm must be optimized to run in O(n) time to handle large inputs efficiently.

vector<long long> findPrefixScore(vector<int>& nums) {
    int mx = nums[0];
    long long sum = 0;
    int n = nums.size();
    vector<long long> ans(n, 0);
    for(int i = 0; i < n; i++) {
        mx = max(mx, nums[i]);
        int scr = nums[i] + mx;
        ans[i] = i == 0? scr: ans[i - 1] + scr;
    }
    return ans;
}

1 : Function Header

vector<long long> findPrefixScore(vector<int>& nums) {

This line defines the function `findPrefixScore`, which takes a vector of integers `nums` and returns a vector of long long integers containing the prefix scores.

2 : Variable Initialization

    int mx = nums[0];

Initializes `mx` to the first element of the array `nums`, representing the maximum value encountered so far.

3 : Variable Initialization

    long long sum = 0;

A variable `sum` is initialized to 0, but it's not used further in the current code.

4 : Variable Initialization

    int n = nums.size();

Stores the size of the `nums` array in the variable `n`.

5 : Array Initialization

    vector<long long> ans(n, 0);

Initializes a vector `ans` of size `n` to store the cumulative prefix scores, initially filled with zeros.

6 : Loop Setup

    for(int i = 0; i < n; i++) {

Starts a loop to iterate through each element of the `nums` array.

7 : Logic

        mx = max(mx, nums[i]);

Updates the `mx` variable to be the maximum of the current `mx` and the current element of `nums[i]`.

8 : Computation

        int scr = nums[i] + mx;

Calculates the score `scr` for the current element as the sum of the element `nums[i]` and the maximum element `mx` seen so far.

9 : Condition

        ans[i] = i == 0? scr: ans[i - 1] + scr;

If it's the first element (`i == 0`), assigns `scr` to `ans[i]`. Otherwise, adds `scr` to the cumulative sum stored in `ans[i-1]`.

10 : Return

    return ans;

Returns the vector `ans` containing the cumulative prefix scores.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we process each element of the array once and perform constant time operations for each element.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the space required for the result array `ans`, which stores the scores for all prefixes.

Leetcode 2640: Find the Score of All Prefixes of an Array

Explore →