Frontend School

Event Impact Span

DSA
medium

Event Impact Span

Medium
Monotonic Stack
Arrays
Stack

Overview

At Freshworks, understanding the impact of various system events on overall performance is crucial. Imagine a monitoring system that records an 'impact score' for every significant event. To analyze trends and identify sustained periods of lower or higher impact, we need a way to quantify the 'span' of influence for each event.

This problem asks you to process a series of event impact scores and determine for each event how many consecutive previous events (including itself) had an impact score less than or equal to its own. This metric, the 'impact span', helps us understand how long an event's impact is 'dominant' over recent preceding events.

What you need to do / Task

Implement the function calculateImpactSpans that takes an array of historical event impactScores and returns an array of the same length. Each element in the output array, spans[i], should represent the impact span for the event at impactScores[i].

Definition of Impact Span: For an event at index i, its impact span is the maximum number of consecutive events immediately preceding it (including itself) whose impact scores are less than or equal to impactScores[i]. The span calculation stops when an event with a strictly higher impact score is encountered, or the beginning of the array is reached.

Input & output

  • Input: impactScores: number[]
    • An array of non-negative integers representing the impact scores of events, in chronological order.
  • Output: number[]
    • An array where output[i] is the calculated impact span for impactScores[i].

Clarifications

  • Empty input: If the impactScores array is empty, return an empty array.
  • First event: The first event in the array will always have an impact span of 1 as there are no preceding events.
  • All increasing scores: If impactScores is [10, 20, 30], the spans would be [1, 2, 3].
  • All decreasing scores: If impactScores is [30, 20, 10], the spans would be [1, 1, 1].

Examples

1

Example 1

Input:

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

Output:

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

Note:

Let's trace:

  • impactScores[0] = 100: No previous events. Span is 1.
  • impactScores[1] = 80: Only 80 itself is <= 80. 100 > 80. Span is 1.
  • impactScores[2] = 60: Only 60 itself is <= 60. 80 > 60. Span is 1.
  • impactScores[3] = 70: 70 <= 70, 60 <= 70. 80 > 70. Span is 2 ([60, 70]).
  • impactScores[4] = 60: Only 60 itself is <= 60. 70 > 60. Span is 1.
  • impactScores[5] = 75: 75 <= 75, 60 <= 75, 70 <= 75. 80 > 75. Span is 4 ([60, 70, 60, 75]). Note that impactScores[2] (60) is included because it's part of the consecutive sequence [60, 70, 60, 75] where all elements are <= 75 and impactScores[1] (80) breaks the sequence.
  • impactScores[6] = 85: 85 <= 85, 75 <= 85, 60 <= 85, 70 <= 85, 60 <= 85, 80 <= 85. 100 > 85. Span is 6 ([80, 60, 70, 60, 75, 85]).
2

Example 2

Input:

impactScores = [10, 20, 30, 40]

Output:

[1, 2, 3, 4]

Note:

Each event's score is greater than or equal to all preceding events, so the span grows with the index.

3

Example 3

Input:

impactScores = [40, 30, 20, 10]

Output:

[1, 1, 1, 1]

Note:

Each event's score is strictly less than the immediately preceding event, so the span is always 1.

Constraints

Constraints & assumptions

  • 1 <= impactScores.length <= 10^5
  • 0 <= impactScores[i] <= 10^9
  • The solution should aim for optimal time complexity, ideally O(N).
  • The solution should aim for optimal space complexity, ideally O(N).

Out of scope

  • Handling non-integer or negative impact scores (guaranteed by constraints).
  • Input validation beyond array length and element value constraints.

What interviewers evaluate

  • Correct application of the Monotonic Stack pattern to solve the problem efficiently.
  • Ability to handle various input scenarios, including edge cases.
  • Code clarity, organization, and adherence to best practices.
  • Analysis of time and space complexity.

Loading editor...