2640. Find the Score of All Prefixes of an Array LeetCode Solution
In this guide, you will get 2640. Find the Score of All Prefixes of an Array LeetCode Solution with the best time and space complexity. The solution to Find the Score of All Prefixes of an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Score of All Prefixes of an Array
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
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2640. Find the Score of All Prefixes of an Array LeetCode Solution in C++
class Solution {
public:
vector<long long> findPrefixScore(vector<int>& nums) {
vector<long long> ans;
long prefix = 0;
int mx = 0;
for (const int num : nums) {
mx = max(mx, num);
prefix += num + mx;
ans.push_back(prefix);
}
return ans;
}
}; /* code provided by PROGIEZ */
2640. Find the Score of All Prefixes of an Array LeetCode Solution in Java
class Solution {
public long[] findPrefixScore(int[] nums) {
long[] ans = new long[nums.length];
long prefix = 0;
int mx = 0;
for (int i = 0; i < nums.length; i++) {
mx = Math.max(mx, nums[i]);
prefix += nums[i] + mx;
ans[i] = prefix;
}
return ans;
}
} // code provided by PROGIEZ
2640. Find the Score of All Prefixes of an Array LeetCode Solution in Python
class Solution:
def findPrefixScore(self, nums: list[int]) -> list[int]:
conver = []
mx = 0
for num in nums:
mx = max(mx, num)
conver.append(num + mx)
return itertools.accumulate(conver) # code by PROGIEZ
