We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Smooth Descent Periods of a Stock

Number: 2233

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of stock prices, a smooth descent period is defined as one or more contiguous days where, starting from the second day, the price is exactly 1 less than the previous day. Single day periods count as smooth descent periods. Return the total number of smooth descent periods present in the array.

Key Insights

  • A single day is always considered a smooth descent period.
  • For any sequence of days that form a smooth descent, if the length of the sequence is L, then there are 1 + 2 + ... + L = L*(L+1)/2 smooth descent periods.
  • Iterate over the array while tracking the length of the current smooth descent sequence.
  • When the sequence breaks (i.e., the difference is not exactly 1), calculate the number of sub-periods for that sequence and reset the count.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the prices array exactly once. Space Complexity: O(1) - Only constant extra space is used.

Solution

The solution involves iterating through the stock prices while maintaining a counter for the current sequence of smooth descents. For each element, check if it continues the descent (i.e., the current price is exactly 1 less than the previous price). If so, increment the counter; otherwise, calculate the number of smooth descent periods for the sequence using the formula L*(L+1)/2 and then reset the counter. Finally, add any remaining sequence's periods to the result.

Code Solutions

# Function to calculate number of smooth descent periods
def getDescentPeriods(prices):
    # Variable to store the total count of descent periods
    total_periods = 0
    # Variable to store the length of the current descent period sequence
    current_sequence_length = 1

    # Iterate through price list starting from the second element
    for i in range(1, len(prices)):
        # If the current price is exactly 1 less than the previous price
        if prices[i-1] - prices[i] == 1:
            # Increase the length of the current descent sequence by 1
            current_sequence_length += 1
        else:
            # Calculate sub-periods count using arithmetic series formula
            total_periods += (current_sequence_length * (current_sequence_length + 1)) // 2
            # Reset the sequence length to 1 (current day alone is always valid)
            current_sequence_length = 1

    # Add the sub-periods count for the last sequence
    total_periods += (current_sequence_length * (current_sequence_length + 1)) // 2
    return total_periods

# Example usage:
prices = [3, 2, 1, 4]
print(getDescentPeriods(prices))  # Output: 7
← Back to All Questions