Frontend School

Delivery Performance Streak

DSA
medium

Delivery Performance Streak

Medium
Stack
Monotonic Stack
Arrays

Overview

Delhivery places significant emphasis on tracking and improving the performance of its delivery executives (DEs). A crucial metric involves understanding consistent performance or improvement trends. This problem challenges you to quantify 'performance streaks' — how many consecutive previous days a DE's delivery count was less than or equal to their current day's performance. This insight helps managers identify consistent performers or days of significant personal bests, fostering a data-driven approach to performance management.

What you need to do / Task

Implement a function calculatePerformanceStreaks that takes an array of daily delivery counts for a delivery executive. For each day, your function must determine the number of consecutive previous days (including the current day itself) where the delivery count was less than or equal to the current day's count. The result should be an array containing these streak lengths for each corresponding day.

Input & output

  • Input: deliveryCounts: number[]
    • An array of non-negative integers, where deliveryCounts[i] represents the number of parcels delivered on day i.
  • Output: number[]
    • An array of integers answer, where answer[i] is the length of the performance streak ending on day i.

Clarifications

  • Empty input: If deliveryCounts is an empty array, the function should return an empty array [].
  • Single element input: If deliveryCounts contains a single element, the streak for that day is 1.
  • Consecutive previous days: This implies that the count on day j must be <= deliveryCounts[i] for all j such that j <= i and deliveryCounts[k] <= deliveryCounts[i] for all k in [j, i]. If a day k within this range has deliveryCounts[k] > deliveryCounts[i], the streak breaks at k+1 and only includes days from k+1 to i (inclusive).

Examples

1

Example 1

Input:

deliveryCounts = [10, 4, 5, 9, 11]

Output:

[1, 1, 2, 3, 5]

Note:

Day 0 (10): No preceding day is <= 10. Streak: 1. Day 1 (4): No preceding day (10) is <= 4. Streak: 1. Day 2 (5): Day 1 (4) is <= 5. Day 0 (10) is > 5, so streak breaks. Streak: 2 (from 4, 5). Day 3 (9): Day 2 (5) is <= 9, Day 1 (4) is <= 9. Day 0 (10) is > 9, so streak breaks. Streak: 3 (from 4, 5, 9). Day 4 (11): Day 3 (9) <= 11, Day 2 (5) <= 11, Day 1 (4) <= 11, Day 0 (10) <= 11. No preceding day breaks the streak. Streak: 5 (from 10, 4, 5, 9, 11).

2

Example 2

Input:

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

Output:

[1, 1, 1, 2, 1, 4, 6]

Note:

Day 0 (100): Streak 1. Day 1 (80): Streak 1. Day 2 (60): Streak 1. Day 3 (70): Day 2 (60) <= 70. Streak 2 (60, 70). Day 4 (60): Streak 1. Day 5 (75): Day 4 (60) <= 75, Day 3 (70) <= 75, Day 2 (60) <= 75. Day 1 (80) > 75, so streak breaks. Streak 4 (from 60, 70, 60, 75). Day 6 (85): Day 5 (75) <= 85, Day 4 (60) <= 85, Day 3 (70) <= 85, Day 2 (60) <= 85, Day 1 (80) <= 85. Day 0 (100) > 85, so streak breaks. Streak 6 (from 80, 60, 70, 60, 75, 85).

3

Example 3

Input:

deliveryCounts = [5, 5, 5, 5]

Output:

[1, 2, 3, 4]

Note:

Each day's count is equal to or greater than the preceding days, extending the streak continuously.

Constraints

Constraints & assumptions

  • 1 <= deliveryCounts.length <= 10^5
  • 0 <= deliveryCounts[i] <= 10^9
  • The input array deliveryCounts will only contain non-negative integers.
  • Expected time complexity: O(N), where N is the length of deliveryCounts.
  • Expected space complexity: O(N), for auxiliary data structures.

Out of scope

  • Input validation for non-array types or elements that are not numbers.
  • Handling extremely large numbers that might exceed standard integer limits (assume number type is sufficient).

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly calculate streak lengths for all valid inputs, including edge cases.
  • Efficiency: The solution should achieve the optimal time and space complexity requirements.
  • Stack Usage: Effective and appropriate application of the stack data structure to solve the problem.
  • Code Quality: Clear, well-structured, and readable code with meaningful variable names and comments where necessary.

Loading editor...