Frontend School

Pin Future Influence

DSA
medium

Pin Future Influence

Medium
Monotonic Stack
Arrays

Overview

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.

What you need to do / Task

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:

  1. pinScores[j] < pinScores[i] (pin j has a strictly lower influence score than pin i), AND
  2. All pins k 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 & output

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].

Clarifications

  • If a pin has no subsequent pins, its future influence is 0.
  • If no subsequent pins satisfy the condition (i.e., all subsequent pins are equal to or greater than the current pin's score), its future influence is 0.
  • The input array pinScores can be empty or contain a single element. In these cases, return an array of the same size with all zeros.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= pinScores.length <= 10^5
  • 0 <= pinScores[i] <= 10^9
  • The sum of all pinScores[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.
  • Expected time complexity: O(N) where N is the length of pinScores.
  • Expected space complexity: O(N) where N is the length of pinScores.

Out of scope

  • Handling negative influence scores.
  • Optimizing for extremely large numbers that exceed standard 64-bit integer limits (e.g., using BigInt in JavaScript, though the problem constraints indicate it's not strictly necessary for sums).

What interviewers evaluate

  • Correctness of the algorithm for all edge cases (empty input, monotonic sequences, etc.).
  • Optimal time and space complexity using a monotonic stack approach.
  • Clear, readable, and well-structured code.
  • Ability to articulate the chosen approach and its complexity trade-offs.

Loading editor...