Frontend School

Daily Playback Streak

DSA
medium

Daily Playback Streak

Medium
Arrays
Stack
Monotonic Stack

Overview

At Spotify, understanding the performance trends of tracks over time is crucial for curation, recommendation systems, and artist support. We often analyze daily play counts to identify periods of increasing popularity. This problem asks you to process a sequence of a track's daily play counts to find "playback streaks" – a measure of how many consecutive preceding days a track's plays were consistently lower than the current day.

What you need to do / Task

Implement a function calculatePlaybackStreaks that takes an array of integers representing a track's daily play counts. For each day i, your function should determine the number of consecutive preceding days (i.e., days i-1, i-2, ..., i-k) where the play count was strictly less than the current day's play count (playCounts[i]). The streak ends when a preceding day's play count is found to be greater than or equal to playCounts[i], or when the beginning of the array is reached.

Your function should return an array of integers, where each element at index i corresponds to the calculated streak for playCounts[i].

Input & output

Function Signature:

function calculatePlaybackStreaks(playCounts: number[]): number[]

Input:

  • playCounts: An array of integers, where playCounts[i] represents the total number of plays for a track on day i.

Output:

  • An array of integers, streaks, of the same length as playCounts. streaks[i] should be the count of consecutive preceding days where the play count was strictly less than playCounts[i].

Clarifications

  • First Day: For the very first day (index 0), there are no preceding days, so its streak will always be 0.
  • Empty Input: If playCounts is empty, the function should return an empty array.
  • Strictly Less: The condition for a preceding day to be part of the streak is that its play count must be strictly less than the current day's play count. If a preceding day has an equal or greater play count, the streak is broken.

Examples

1

Example 1

Input:

playCounts = [100, 80, 60, 70, 60, 75, 85]

Output:

[0, 0, 0, 1, 0, 3, 4]

Note:

Let's trace the streak for each day:

  • Day 0 (100): No preceding days. Streak: 0.
  • Day 1 (80): playCounts[0]=100 is not strictly less than 80. Streak: 0.
  • Day 2 (60): playCounts[1]=80 is not strictly less than 60. Streak: 0.
  • Day 3 (70): playCounts[2]=60 is strictly less than 70. playCounts[1]=80 is not strictly less than 70, so the streak breaks. Streak: 1.
  • Day 4 (60): playCounts[3]=70 is not strictly less than 60. Streak: 0.
  • Day 5 (75): playCounts[4]=60 is strictly less than 75. playCounts[3]=70 is strictly less than 75. playCounts[2]=60 is strictly less than 75. playCounts[1]=80 is not strictly less than 75, so the streak breaks. Streak: 3.
  • Day 6 (85): playCounts[5]=75 is strictly less than 85. playCounts[4]=60 is strictly less than 85. playCounts[3]=70 is strictly less than 85. playCounts[2]=60 is strictly less than 85. playCounts[1]=80 is not strictly less than 85, so the streak breaks. Streak: 4.
2

Example 2

Input:

playCounts = [50, 60, 70, 80, 75]

Output:

[0, 1, 2, 3, 0]

Note:

Let's trace the streak for each day:

  • Day 0 (50): Streak: 0.
  • Day 1 (60): playCounts[0]=50 < 60. Streak: 1.
  • Day 2 (70): playCounts[1]=60 < 70, playCounts[0]=50 < 70. Streak: 2.
  • Day 3 (80): playCounts[2]=70 < 80, playCounts[1]=60 < 80, playCounts[0]=50 < 80. Streak: 3.
  • Day 4 (75): playCounts[3]=80 is not strictly less than 75. Streak: 0.
3

Example 3

Input:

playCounts = []

Output:

[]

Note:

An empty input array results in an empty output array.

Constraints

Constraints & assumptions

  • 0 <= playCounts.length <= 10^5
  • 1 <= playCounts[i] <= 10^9 for all valid i.
  • The input array playCounts contains only non-negative integers.

What interviewers evaluate

  • Correctness: Does the solution accurately calculate the playback streaks for all valid inputs, including edge cases?
  • Time Complexity: Is the solution efficient enough to handle large input sizes? An optimal solution should aim for O(N) time complexity.
  • Space Complexity: Is the solution memory-efficient? An optimal solution should aim for O(N) space complexity.
  • Code Quality & Readability: Is the code well-structured, easy to understand, and maintainable? Are appropriate data structures used?
  • Problem-Solving Approach: Can the candidate articulate their thought process, identify potential data structures, and explain the rationale behind their chosen approach (e.g., why a monotonic stack is suitable)?

Loading editor...