Prefix Scores With the Running Maximum
Updated
Problem statement
You are given an integer array arr of length n. For every k from 1 to n, find the score of the first k elements:
- Copy the first
kelements into a new arraya. - Walk through
afrom left to right. At each indexi, take the current maximum of the whole arrayaand add it toa[i]. The maximum includes the values already changed and the values not reached yet. - The score is the sum of
aafter the walk, modulo109 + 7.
The walk uses the exact values. Only the final sum is taken modulo 109 + 7.
Return an array scores of length n, where scores[k - 1] is the score of the first k elements.
Function
getPrefixScores(arr: int[]) → int[]Examples
Example 1
arr = [3,1,2]return = [6,13,22]Prefix [3]: the maximum is 3, so it becomes [6]. Score 6.
Prefix [3, 1]: add the maximum 3 to the first element to get [6, 1]. Now the maximum is 6, so the second element becomes 7: [6, 7]. Score 6 + 7 = 13.
Prefix [3, 1, 2]: [3, 1, 2] becomes [6, 1, 2], then [6, 7, 2], then the maximum is 7, so [6, 7, 9]. Score 6 + 7 + 9 = 22.
Example 2
arr = [2,5]return = [4,19]Prefix [2]: it becomes [4]. Score 4.
Prefix [2, 5]: the maximum of the whole array is 5, even though 5 has not been visited yet, so the first element becomes 7: [7, 5]. Now the maximum is 7, so the second element becomes 12: [7, 12]. Score 7 + 12 = 19.
Example 3
arr = [1000000000,1000000000]return = [999999993,999999972]Prefix [1000000000]: it becomes [2000000000]. 2000000000 mod 1000000007 = 999999993.
Prefix [1000000000, 1000000000]: it becomes [2000000000, 1000000000], then the maximum is 2000000000, so [2000000000, 3000000000]. The exact sum is 5000000000, and 5000000000 mod 1000000007 = 999999972. The walk uses the exact values; only the final sum is taken modulo 109 + 7.
Constraints
1 <= arr.length <= 20001 <= arr[i] <= 109
More C3.ai interview questions
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
- Tree Node With Maximum BeautyOA · Seen Nov 2022
- Count Vowel Strings With Follow RulesOA · Seen Apr 2022
- Photo Album Insert OrderOA · Seen Apr 2022
- Sort by Frequency, Then ValueOA · Seen Apr 2022
- Count Distinct Binary Search TreesOA · Seen Mar 2022
- Count Palindromic Subsequences of Length KOA · Seen Mar 2022
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- Online No-Intercept Linear RegressionTwo Sigma · OATwo Sigma interview questions
- Array Challenge (QR Intern)Akuna Capital · OAAkuna Capital interview questions
- Capping Portfolio WeightsCapstone Investment Advisors · OA
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Stacked Item and Category DiscountsPalantir · OAPalantir interview questions
- Macaron Order PriceOpenAI · OAOpenAI interview questions
- Daily Settlement for Long and Short PositionsBelvedere Trading · OA
- Count Attack Vectors by Divisor RangeVisa · OAVisa interview questions
- Prime Factor VisitationMaven Securities · OAMaven Securities interview questions