Problem Statement in English

You’re given an integer array prices representing the daily prices of a stock.

A smooth descent period is defined as a contiguous subarray where each day’s price is exactly one less than the previous day’s price. This rule does not apply to the first day of the period. Thus, a single day is also considered a smooth descent period.

Your task is to find the total number of smooth descent periods in the prices array.

Approach

All we really need to do in this problem is to find all the contiguous segments where the prices are decreasing by exactly 1 each day.

We can do this with a 2 pointer approach. The left pointer will mark the start of a smooth descent period, and the right pointer will iterate through the array.

Whenever we find that the current price is not one less than the previous price, we calculate the number of smooth descent periods in the segment from the left pointer to the right pointer - 1 using the formula for the sum of the first n natural numbers: n * (n + 1) / 2, where n is the length of the segment.

We then move the left pointer to the current position of the right pointer.

And we’re done.

Solution in Python


class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        l = res = 0

        for r in range(1, len(prices)):
            if prices[r - 1] - 1 != prices[r]:
                gap = r - l
                res += (gap * (gap + 1)) // 2
                l = r

        gap = len(prices) - l
        res += (gap * (gap + 1)) // 2

        return res

Complexity

  • Time: O(n)O(n)
    Since we iterate through the array

  • Space: O(1)O(1)
    Since we use only a constant amount of extra space.

And we are done.