MediumNo. 2110

Number of Smooth Descent Periods of a Stock — LeetCode 2110 Python Solution

Topics
Array, Math, Two Pointers, Dynamic Programming, Sliding Window
Reading time
2 min

The problem

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith 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.

Example

Input
prices = [3,2,1,4]
Output
7
Explanation
There are 7 smooth descent periods:

Python solution

PythonSolution
class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        ans = 0
        i, n = 0, len(prices)
        while i < n:
            j = i + 1
            while j < n and prices[j - 1] - prices[j] == 1:
                j += 1
            cnt = j - i
            ans += (1 + cnt) * cnt // 2
            i = j
        return ans

Complexity

Time
O(n)where n is the length of the array prices
Space · auxiliary
O(1)

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2110. Number of Smooth Descent Periods of a Stock is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0189Rotate ArrayMedium
0837New 21 GameMedium
1040Moving Stones Until Consecutive IIMedium
1610Maximum Number of Visible PointsHard
0048Rotate ImageMedium
0066Plus OneEasy

Frequently asked questions

How hard is LeetCode 2110. Number of Smooth Descent Periods of a Stock?

LeetCode 2110. Number of Smooth Descent Periods of a Stock is rated Medium on LeetCode.

What is the time complexity of LeetCode 2110. Number of Smooth Descent Periods of a Stock?

The Python solution on this page runs in O(n), where n is the length of the array \textit{prices}.

What is the space complexity of LeetCode 2110. Number of Smooth Descent Periods of a Stock?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2110. Number of Smooth Descent Periods of a Stock cover?

LeetCode 2110. Number of Smooth Descent Periods of a Stock is tagged Array, Math, Two Pointers, Dynamic Programming and Sliding Window on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.