Number of Smooth Descent Periods of a Stock

Medium

Asked by:

13 views

Topics:

ArraysDynamic Programming

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the i^th day.

A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.

Return the number of smooth descent periods.

Example 1:

Input: prices = [3,2,1,4]
Output: 7
Explanation: There are 7 smooth descent periods:
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Note that a period with one day is a smooth descent period by the definition.

Example 2:

Input: prices = [8,6,7,7]
Output: 4
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3:

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Constraints:

1 <= prices.length <= 10⁵
1 <= prices[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the `prices` array?
Can the values in the `prices` array be negative or non-integer?
If the `prices` array is empty or null, what should I return?
Is a single day considered a smooth descent period?
Are all smooth descent periods required to be contiguous, or can they overlap?

Brute Force Solution

Approach

The brute force strategy involves checking every possible continuous period of stock prices. We're looking for periods where the price decreases by exactly 1 each day. We simply count the valid periods as we find them.

Here's how the algorithm would work step-by-step:

Start by considering each individual day as a smooth descent period of length one.
Then, consider every pair of consecutive days. Check if the price on the second day is exactly one less than the price on the first day. If it is, we found another smooth descent period.
Next, consider every group of three consecutive days. Check if each consecutive day's price is exactly one less than the previous day's price. If so, count this longer period.
Continue this process, increasing the length of the period we are checking each time, until we have considered the entire range of available days.
In each step, if the prices satisfy our 'smooth descent' criteria (decreasing by 1 each day), we increment our counter.
After checking every possible period, return the total number of smooth descent periods we counted.

Code Implementation

def get_number_of_smooth_descent_periods(prices):
    number_of_prices = len(prices)
    number_of_smooth_descent_periods = 0

    # Iterate through all possible starting positions
    for start_index in range(number_of_prices):
        # Iterate through all possible lengths of periods
        for period_length in range(1, number_of_prices - start_index + 1):
            is_smooth_descent = True
            
            # Check if the current period is a smooth descent.
            for index_in_period in range(period_length - 1):

                if prices[start_index + index_in_period] - prices[start_index + index_in_period + 1] != 1:
                    is_smooth_descent = False
                    break

            # Increment count if smooth descent found
            if is_smooth_descent:
                number_of_smooth_descent_periods += 1

    return number_of_smooth_descent_periods

Big(O) Analysis

Time Complexity

O(n²) – The brute force algorithm iterates through all possible subarrays of the input array of size n. The outer loop determines the starting index of the subarray, which can be any of the n elements. The inner loop extends the subarray from the starting index to the end of the array. Thus, the number of smooth descent periods check operations is proportional to the sum 1 + 2 + ... + n, which equals n*(n+1)/2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force algorithm only uses a few constant space variables to iterate through the input array and count smooth descent periods. It doesn't create any auxiliary data structures that scale with the input size N (the number of stock prices). Therefore, the space complexity remains constant regardless of the input size.

Optimal Solution

Approach

The problem asks us to count how many periods of time a stock's price decreases smoothly. The key is to avoid recomputing information by building on previous calculations, counting periods as we go. We look at the price drops and smartly keep track of how many smooth periods end at each day, then add them all up.

Here's how the algorithm would work step-by-step:

Start by thinking of each individual day as a smooth descent period of length 1. This is our starting point.
Now, go through the stock prices day by day, starting from the second day.
For each day, check if the price is exactly one less than the price of the previous day. If it is, it means we can extend a smooth descent period.
If the price is one less than the previous day, then the number of smooth descent periods ending on this day is one more than the number of smooth descent periods ending on the previous day. We're extending existing periods.
If the price isn't one less than the previous day, the smooth descent period ending on this day is just of length 1 (the day itself).
As you go through the prices, keep a running total of all the smooth descent periods ending at each day.
At the very end, the total number you have is the answer: the total number of smooth descent periods in the stock's history.

Code Implementation

def get_descent_periods(prices):
    number_of_days = len(prices)
    descent_periods_ending_here = [1] * number_of_days
    total_descent_periods = number_of_days

    for day_index in range(1, number_of_days):
        # Check if current price continues descent
        if prices[day_index] == prices[day_index - 1] - 1:

            # Extend descent period from previous day
            descent_periods_ending_here[day_index] = \
                descent_periods_ending_here[day_index - 1] + 1

            # Update total smooth descent periods
            total_descent_periods += \
                descent_periods_ending_here[day_index] - 1

    return total_descent_periods

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of stock prices once, where n is the number of days (or the length of the prices array). Inside the loop, a constant number of operations are performed for each element, specifically checking if the current price is one less than the previous price and updating counters. Therefore, the time complexity is directly proportional to the input size n, making it O(n).

Space Complexity

O(1) – The algorithm uses a single variable to keep track of the number of smooth descent periods ending on the previous day and a variable to accumulate the total count. These variables require constant extra space. No auxiliary data structures that scale with the input size N (number of stock prices) are used. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 since there are no price points and therefore no smooth descent periods.
Input array with only one element	Return 1 since a single price point is considered a smooth descent period of length 1.
Input array with prices in strictly descending order	The result should be a sum of consecutive integers from 1 to n where n is the length of the array.
Input array with all identical prices	Each individual day is a smooth descent period, so the result should equal the length of the array.
Input array with prices in strictly ascending order	The result should equal the length of the array, since each day is individually a smooth descent period.
Input array with alternating increasing and decreasing prices (e.g., [1, 2, 1, 2, 1])	The result should correspond to the number of individual days plus the count of descending pairs with difference of 1.
Very large input array (approaching memory limits)	The algorithm should use O(1) space, avoiding large auxiliary data structures and preventing out-of-memory errors.
Integer overflow when calculating the number of periods	Use a 64-bit integer (long) to accumulate the count of smooth descent periods.

Null or empty input array

How to Handle:

Return 0 since there are no price points and therefore no smooth descent periods.

Input array with only one element

How to Handle:

Return 1 since a single price point is considered a smooth descent period of length 1.

Input array with prices in strictly descending order

How to Handle:

The result should be a sum of consecutive integers from 1 to n where n is the length of the array.

Input array with all identical prices

How to Handle:

Each individual day is a smooth descent period, so the result should equal the length of the array.

Input array with prices in strictly ascending order

How to Handle:

The result should equal the length of the array, since each day is individually a smooth descent period.

Input array with alternating increasing and decreasing prices (e.g., [1, 2, 1, 2, 1])

How to Handle:

The result should correspond to the number of individual days plus the count of descending pairs with difference of 1.

Very large input array (approaching memory limits)

How to Handle:

The algorithm should use O(1) space, avoiding large auxiliary data structures and preventing out-of-memory errors.

Integer overflow when calculating the number of periods

How to Handle:

Use a 64-bit integer (long) to accumulate the count of smooth descent periods.