Pin Future Influence
At Pinterest, understanding the reach and longevity of content is crucial for user engagement and content curation. Pins are constantly being created and consumed, and their "influence" can vary widely. We want to analyze how much a pin's influence extends to subsequent, less impactful pins, until a more influential pin emerges. This helps us understand the immediate "shadow" a pin casts over its successors.
You are tasked with implementing a function calculateFutureInfluence that takes an array of integers pinScores, where each element represents the influence score of a pin. For each pin i, you need to calculate its "total future influence".
A pin j (where j > i) contributes to pin i's future influence if:
pinScores[j] < pinScores[i] (pin j has a strictly lower influence score than pin i), ANDk such that i < k < j also satisfy pinScores[k] < pinScores[i] (all pins between i and j also have strictly lower influence scores than pin i).In simpler terms, for each pin i, sum the scores of all subsequent pins j that are strictly less influential than pinScores[i], until you encounter a pin p (where p > i) such that pinScores[p] >= pinScores[i]. Once such a pin p is found, no further pins contribute to pinScores[i]'s future influence. If no such p exists, sum all subsequent pins j where pinScores[j] < pinScores[i].
Your function should return an array where the element at index i is the total future influence for pinScores[i].
Input:
pinScores: number[] - An array of non-negative integers representing the influence scores of pins. Each score is 0 <= score <= 10^9.Output:
number[] - An array of integers of the same length as pinScores, where output[i] is the total future influence for pinScores[i].pinScores can be empty or contain a single element. In these cases, return an array of the same size with all zeros.Examples
Example 1
Input:
pinScores = [3, 1, 2, 4]
Output:
[3, 0, 0, 0]
Note:
For pinScores[0]=3: it dominates pins with scores 1 and 2. The next pin is 4 (>=3), so we stop. Total = 1 + 2 = 3. For pinScores[1]=1: the next pin is 2 (>=1), so it dominates nothing. Total = 0. For pinScores[2]=2: the next pin is 4 (>=2), so it dominates nothing. Total = 0. For pinScores[3]=4: no subsequent pins. Total = 0.
Example 2
Input:
pinScores = [5, 4, 3, 2, 1]
Output:
[10, 6, 3, 1, 0]
Note:
For pinScores[0]=5: it dominates 4, 3, 2, 1. Total = 4+3+2+1 = 10. For pinScores[1]=4: it dominates 3, 2, 1. Total = 3+2+1 = 6. For pinScores[2]=3: it dominates 2, 1. Total = 2+1 = 3. For pinScores[3]=2: it dominates 1. Total = 1. For pinScores[4]=1: no subsequent pins. Total = 0.
Example 3
Input:
pinScores = [1, 2, 3, 4, 5]
Output:
[0, 0, 0, 0, 0]
Note:
For every pin, the very next pin has an equal or higher score, so no pins are dominated. Total future influence for all pins is 0.
Constraints
1 <= pinScores.length <= 10^50 <= pinScores[i] <= 10^9pinScores[i] in the input will not exceed 10^14 to prevent overflow issues for intermediate sums if using 64-bit integers. For JavaScript/TypeScript, Number type can handle up to 2^53 - 1, which is approximately 9 * 10^15, so sums should fit.pinScores.pinScores.Loading editor...