2110. Number of Smooth Descent Periods of a Stock

Problem Description

You are tasked with analyzing the price history of a stock, given as an array of integers named prices. Each element in this array corresponds to the price of the stock on a specific day. A smooth descent period is identified when there is a sequence of one or more consecutive days where each day's stock price is exactly 1 lower than the previous day's price (except for the first day of this sequence, which does not have this restriction).

The goal is to calculate the total number of smooth descent periods in the stock price history provided by prices.

Intuition

The intuition behind solving this problem is to traverse the prices array and identify segments where the prices are decreasing by exactly 1 each day. These segments are the smooth descent periods we are interested in counting.

To achieve this, we can iterate over the prices array using two pointers or indices. The first pointer i marks the start of a potential descent period, while the second pointer j explores the array to find the end of this descent. As long as the difference between the prices of two consecutive days (prices[j - 1] - prices[j]) equals 1, we continue moving j forward, extending the current descent period.

Once we reach the end of a descent period (when the difference is not equal to 1), we calculate the total number of descent periods within the segment marked by i and j. This calculation can be done by using the formula for the sum of the first n natural numbers, as the number of descent periods formed by a contiguous descending sequence is equivalent to the sum of an arithmetic series starting from 1. The formula ans += (1 + cnt) * cnt // 2 is used, where cnt is the length of the current descent period.

After adding to the total count ans, we set i to the current position of j and proceed to find the next potential descent period in the array. This process continues until we have traversed the entire array and evaluated all potential smooth descent periods.

By using this approach, we ensure a linear time complexity of O(n), where n is the number of days in the prices array, since each element is visited only once.

Learn more about Math and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological SortUniform Cost SearchMonotonic StackMemoization

I don’t know

Solution Approach

The solution uses a straightforward linear scan algorithm with two pointers to traverse the prices array without the need for additional data structures. Here's a step-by-step breakdown of how it's implemented:

Initialize a variable ans to 0. This will hold the cumulative number of smooth descent periods.
Set two pointers (or indices) i and j. i starts at 0, marking the beginning of a potential smooth descent sequence.
Initiate a while loop that will run as long as i is less than the length of the prices array (n).
Inside the loop, increment j starting from i+1 as long as j is less than n and the price difference between two consecutive days is exactly 1 (prices[j - 1] - prices[j] == 1). This locates the end of the current descending period.
Once the end of a descent period is found, calculate the length of this descent period (cnt = j - i). This count represents the number of contiguous days in the current smooth descent period.
Use the arithmetic series sum formula to find the total number of smooth descent periods in the current sequence. The formula to use is (1 + cnt) * cnt // 2, which is then added to ans.
After computing the number of descent periods for the current segment, move i to j, the position where the current descent segment ended. This is to start checking for a new descent period from this point forward.
Repeat steps 4 to 7 until the entire prices array has been scanned.
After completing the traversal, return the total count ans as the final answer.

The implementation uses the concept that the sum of an arithmetic series can calculate the number of distinct smooth descent periods within a given range. Since in each contiguous descent sequence, the difference is '1', it forms a series like 1, 2, ..., cnt. The sum of these numbers, representing different lengths of smooth descent periods that can be formed, is calculated using the equation (1 + cnt) * cnt // 2. By summing up such counts for all descending sequences found in prices, we obtain the overall number of smooth descent periods in the entire array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Example Walkthrough

To illustrate the solution approach, let's consider a small example where the given prices array is [5, 4, 3, 2, 8, 7, 6, 5, 4, 10].

Let's walk through the steps outlined in the solution approach:

Initialize ans to 0. This is where we will accumulate the number of smooth descent periods.
Set pointers i and j to 0 and 1, respectively, to start tracking a potential smooth descent period from the beginning of the array.
We now enter the while loop since i (0) is less than the length of the prices array (10).
The first potential descent starts at index 0 with a price of 5. We start moving j forward and find that prices[0] - prices[1] is 1, and the same goes for prices[1] - prices[2] and prices[2] - prices[3], until we reach prices[3] - prices[4] which is not 1 (since 2 - 8 is -6). Therefore, we have identified the first descent period from index 0 to 3.
We calculate the length of this descent period: cnt = j - i which in this case is 4 - 0 = 4.
Using the arithmetic series sum formula, we add the number of smooth descents in this sequence to ans: (1 + cnt) * cnt // 2 which is (1 + 4) * 4 // 2 = 10. So now, ans = 10.
We move i to the position where j is now (i = j), making i 4, and look for the next descent period starting from index 4.
Now j moves forward again, and we see that we have a descent from 8 at index 4 to 4 at index 8. We perform the same calculations as before and find that cnt = j - i = 9 - 4 = 5. The number of descents is (1 + cnt) * cnt // 2 which equals (1 + 5) * 5 // 2 = 15, and we add this to ans making it now 10 + 15 = 25.
Finally, we have finished the while loop since j has reached the end of the prices array.
Return the total count ans which is 25. This is the total number of smooth descent periods in the example price history.

This walkthrough demonstrates the process and calculations in the solution approach using the given problem description and solution strategy.

Solution Implementation

1class Solution:
2    def getDescentPeriods(self, prices: List[int]) -> int:
3        # Initialize the total number of descent periods
4        total_periods = 0
5
6        # Initialize the starting index and find the length of the prices list
7        start_index = 0
8        length = len(prices)
9
10        # Iterate through the prices list
11        while start_index < length:
12            # Find the consecutive descending sequence by checking the price difference
13            end_index = start_index + 1
14            while end_index < length and prices[end_index - 1] - prices[end_index] == 1:
15                end_index += 1
16
17            # Calculate the length of the descent sequence
18            descent_length = end_index - start_index
19
20            # Using the arithmetic series sum formula, (n/2)*(first term + last term),
21            # here it simplifies to (1 + descent_length) * descent_length / 2
22            # since the difference between consecutive terms is 1.
23            total_periods += (1 + descent_length) * descent_length // 2
24
25            # Move the start index to the end of the current descent sequence
26            start_index = end_index
27
28        # Return the total number of descent periods found
29        return total_periods
30

1class Solution {
2    public long getDescentPeriods(int[] prices) {
3        long totalDescentPeriods = 0; // Initialize the result variable to keep track of the total descent periods.
4        int n = prices.length; // Get the total number of elements in the prices array.
5
6        // Iterate over the prices array.
7        for (int start = 0, end = 0; start < n; start = end) {
8            // Initialize end to the next element after start for the next potential descent.
9            end = start + 1;
10
11            // Find a contiguous subarray where each pair of consecutive elements
12            // have difference equals to 1. This forms a descent period.
13            // The while loop will continue until the condition fails,
14            // indicating we've reached the end of the current descent period.
15            while (end < n && prices[end - 1] - prices[end] == 1) {
16                ++end;
17            }
18
19            // Calculate the length of the current descent period.
20            int periodLength = end - start;
21          
22            // Using the arithmetic progression sum formula to count all individual
23            // and overlapping periods: n*(n+1)/2, where n is the length of the current descent.
24            totalDescentPeriods += (1L + periodLength) * periodLength / 2;
25        }
26
27        // Return the total number of descent periods found in the prices array.
28        return totalDescentPeriods;
29    }
30}
31

1class Solution {
2public:
3    long long getDescentPeriods(vector<int>& prices) {
4        long long totalDescentPeriods = 0;  // Holds the sum of all descent periods
5        int sequenceLength = prices.size(); // Total number of elements in prices
6
7        // Loop through each price in the vector
8        for (int start = 0, end = 0; start < sequenceLength; start = end) {
9            end = start + 1;
10
11            // Continue to find descending contiguous subsequences where each 
12            // element is one less than the previous one
13            while (end < sequenceLength && prices[end - 1] - prices[end] == 1) {
14                ++end;
15            }
16
17            // Calculate the length of the contiguous subsequence
18            int count = end - start;
19          
20            // Add the total number of descent periods that can be 
21            // formed with the subsequence of length 'count'
22            totalDescentPeriods += (1LL + count) * count / 2;
23        }
24
25        return totalDescentPeriods; // Return the final total of descent periods
26    }
27};
28

1// Counts the total number of "descent periods" in a given array of prices.
2// A "descent period" is defined as one or more consecutive days where the
3// price of a stock decreases by exactly 1 each day.
4function getDescentPeriods(prices: number[]): number {
5    let totalDescentPeriods = 0; // Store the total count of descent periods.
6    const pricesLength = prices.length; // The length of the 'prices' array.
7
8    // Iterate through the 'prices' array to identify descent periods.
9    for (let startIndex = 0, endIndex = 0; startIndex < pricesLength; startIndex = endIndex) {
10        endIndex = startIndex + 1;
11
12        // Check if the next price is one less than the current; if so, extend the descent period.
13        while (endIndex < pricesLength && prices[endIndex - 1] - prices[endIndex] === 1) {
14            endIndex++;
15        }
16
17        // Calculate the number of prices in the current descent period.
18        const descentPeriodLength = endIndex - startIndex;
19
20        // Calculate the count of descent periods using the formula for the sum of the first n integers.
21        totalDescentPeriods += Math.floor(((1 + descentPeriodLength) * descentPeriodLength) / 2);
22    }
23  
24    // Return the total count of descent periods found in the 'prices' array.
25    return totalDescentPeriods;
26}
27

Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Time and Space Complexity

The provided Python code defines a method getDescentPeriods which calculates the total number of "descent periods" within a list of prices. A descent period is defined as a sequence of consecutive days where the price of each day is one less than the price of the day before.

Time Complexity:

The time complexity of the code is O(n), where n is the number of elements in the prices list. This is because the function uses a while loop (and a nested while loop) that traverses the list exactly once. Each element is visited once by the outer loop, and the inner loop advances the index j without revisiting any previously checked elements. The computations within the loops are simple arithmetic operations, which take constant time. Therefore, the number of operations increases linearly with the number of elements in the input list, resulting in a linear time complexity.

Space Complexity:

The space complexity of the code is O(1). The code only uses a constant amount of space (variables ans, i, n, j, and cnt) that does not depend on the input list's size. It does not use any additional data structures that grow with the input size, so the amount of space used remains constant even as the size of the input list increases.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2110. Number of Smooth Descent Periods of a Stock

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity:

Space Complexity:

Recommended Readings