Frontend School

Price Drop Forecast

DSA
medium

Price Drop Forecast

Medium
Stack
Arrays
Monotonic Stack

Overview

Groww aims to provide its users with insightful market data. One such insight is forecasting potential short-term price drops. This problem asks you to build a tool that, for each day, predicts how many days it will take for the stock price to drop below or equal to its current level. This can help users identify potential support levels or exit points.

What you need to do / Task

Implement the function priceDropForecast that takes an array of daily stock prices prices and returns an array where each element result[i] represents the number of days until the price prices[i] drops to a value less than or equal to prices[i]. If the price never drops below or equals prices[i] for any future day, result[i] should be -1.

Input & output

  • Input:
    • prices: An array of positive integers, prices[i] representing the stock price on day i.
  • Output:
    • An array of integers result of the same length as prices. result[i] is the number of days until prices[i] drops below or equals itself, or -1 if it never does.

Clarifications

  • "Number of days until drop": If prices[i] drops to prices[j] where j > i and prices[j] <= prices[i], the number of days is j - i.
  • If multiple future days satisfy the condition, we are interested in the first such day (smallest j).
  • Prices are always positive integers.

Examples

1

Example 1

Input:

prices = [10, 8, 12, 11, 13, 9]

Output:

[1, -1, 1, 2, 1, -1]

Note:

  • For 10 (day 0): The next price <= 10 is 8 on day 1. Days until drop: 1 - 0 = 1.
  • For 8 (day 1): No future price is <= 8. Days until drop: -1.
  • For 12 (day 2): The next price <= 12 is 11 on day 3. Days until drop: 3 - 2 = 1.
  • For 11 (day 3): The next price <= 11 is 9 on day 5. Days until drop: 5 - 3 = 2.
  • For 13 (day 4): The next price <= 13 is 9 on day 5. Days until drop: 5 - 4 = 1.
  • For 9 (day 5): No future prices. Days until drop: -1.
2

Example 2

Input:

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

Output:

[1, 1, 1, 1, 1, 1, -1]

Note:

Each day, the price drops to the next day's price. For the last day, no future drop.

3

Example 3

Input:

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

Output:

[-1, -1, -1, -1, -1]

Note:

The prices are strictly increasing, so no future price ever drops below or equals the current price.

Constraints

Constraints & assumptions

  • 1 <= prices.length <= 10^5
  • 1 <= prices[i] <= 10^9
  • The input array prices will only contain positive integers.

What interviewers evaluate

  • Correctness: The solution accurately calculates the price drop forecast for all valid inputs.
  • Efficiency: The solution achieves optimal time and space complexity (typically O(N) time and O(N) space for stack-based problems).
  • Code Quality: Clean, readable, and well-structured code with appropriate data structures and variable names.
  • Problem-solving approach: Ability to identify and apply the correct algorithmic pattern (e.g., stack usage) to solve the problem.

Loading editor...