Frontend School

Stock Price Span Calculator

DSA
medium

Stock Price Span Calculator

Medium
Stack
Arrays
Monotonic Stack
Financial Data

Overview

In financial markets, analyzing stock price trends is crucial for making informed decisions. One common technical indicator is the "price span," which helps identify how long a stock has maintained or increased its value relative to recent history. This problem challenges you to implement an efficient algorithm to calculate this span for a given series of daily stock prices.

What you need to do / Task

Implement the function calculateSpan that takes an array of daily stock prices. For each day, you need to calculate its "span". The span of a stock's price today is defined as the maximum number of consecutive days immediately preceding the current day (and including the current day) for which the stock price was less than or equal to today's price.

Your function should return an array where each element i corresponds to the calculated span for prices[i].

Input & output

  • Input: prices: number[]
    • An array of positive integers representing the daily stock prices.
  • Output: number[]
    • An array where result[i] is the calculated span for prices[i]. Each span value will be a positive integer.

Clarifications

  • First Day's Span: The span for the first day in the prices array is always 1, as there are no preceding days.
  • Consecutive Days: The definition of span requires consecutive days. If a day's price breaks the less than or equal to condition, the streak is broken, and you only count days up to that point (including the current day).

Examples

1

Example 1

Input:

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

Output:

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

Note:

Let's trace:

  • Day 0 (100): No preceding days. Span = 1.
  • Day 1 (80): 100 > 80. Span = 1.
  • Day 2 (60): 80 > 60. Span = 1.
  • Day 3 (70): 60 <= 70. Go back. 80 > 70. Streak broken. Days: [60, 70]. Span = 2.
  • Day 4 (60): 70 > 60. Span = 1.
  • Day 5 (75): 60 <= 75, 70 <= 75, 60 <= 75. Go back. 80 > 75. Streak broken. Days: [60, 70, 60, 75]. Span = 4.
  • Day 6 (85): 75 <= 85, 60 <= 85, 70 <= 85, 60 <= 85, 80 <= 85. Go back. 100 > 85. Streak broken. Days: [80, 60, 70, 60, 75, 85]. Span = 6.
2

Example 2

Input:

prices = [10, 4, 5, 90, 120, 80]

Output:

[1,1,2,4,5,1]

Note:

Spans are calculated as follows:

  • 10: 1
  • 4: 1
  • 5: (4, 5) -> 2
  • 90: (10, 4, 5, 90) -> 4
  • 120: (10, 4, 5, 90, 120) -> 5
  • 80: 1
3

Example 3

Input:

prices = [1, 2, 3, 4, 5]

Output:

[1,2,3,4,5]

Note:

For a strictly increasing sequence, each day's price is greater than or equal to all preceding prices, resulting in spans of 1, 2, 3, 4, 5.

Constraints

Constraints & assumptions

  • 1 <= prices.length <= 10^5
  • 1 <= prices[i] <= 10^9
  • All prices[i] are integers.

What interviewers evaluate

  • Correctness: The solution accurately calculates the span for all elements according to the problem definition.
  • Efficiency: The algorithm achieves optimal time complexity, ideally O(N), where N is the number of days.
  • Space Complexity: The solution uses an appropriate amount of memory, ideally O(N) in the worst case for the stack.
  • Code Quality: The code is well-structured, readable, and demonstrates good programming practices.

Loading editor...