We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Score of All Prefixes of an Array

Number: 2676

Difficulty: Medium

Paid? No

Companies: TikTok

Problem Description

Given an array nums, we need to compute an answer array where each element ans[i] is the score of the prefix nums[0..i]. The score of an array is defined as the sum of its conversion array, where conversion[i] = nums[i] + max(nums[0..i]). Essentially, for every prefix of nums, compute cumulative conversion values and return those sums.

Key Insights

  • For each element, maintain the current maximum of all elements seen so far.
  • The conversion value for the current index is the sum of the current element and the current maximum.
  • A running prefix sum helps to accumulate the scores for each prefix.
  • A single pass over the array yields an O(n) solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (for the output array)

Solution

We iterate through the input array and for each index update two key variables: the current maximum (max_so_far) and the prefix sum (score). At each step, we update max_so_far to be the maximum of itself and the current element. The conversion value at the current position is computed as the current element plus max_so_far, and then we add that to our score. Finally, the updated score is stored in the output array for that prefix.

Code Solutions

# Python implementation
def find_prefix_scores(nums):
    # initialize variables for maximum so far and current prefix score
    max_so_far = 0
    prefix_score = 0
    # list to store score for each prefix
    result = []
    
    # iterate through each element in the array
    for num in nums:
        # update the maximum so far
        max_so_far = max(max_so_far, num)
        # compute the conversion value for current index
        conversion = num + max_so_far
        # update the prefix score by adding the current conversion value
        prefix_score += conversion
        # store the current prefix score result
        result.append(prefix_score)
    
    return result

# Example usage:
print(find_prefix_scores([2,3,7,5,10]))
← Back to All Questions