Problem Description

You are given an integer array prices where prices[i] represents the stock price on day i.

A smooth descent period is defined as one or more consecutive days where the price drops by exactly 1 each day compared to the previous day. The first day of any period doesn't need to follow this rule (it can start from any price).

For example:

• If prices are [3, 2, 1], this forms one smooth descent period of length 3 (price drops from 3→2→1, each by exactly 1)
• If prices are [5, 4, 3, 2], this forms one smooth descent period of length 4
• If prices are [5, 3, 2], the segment [5, 3] doesn't form a smooth descent (drops by 2, not 1), but [3, 2] forms a smooth descent period of length 2

Your task is to count the total number of smooth descent periods in the array. This includes all possible subarrays that satisfy the smooth descent condition.

For a smooth descent period of length n:

• It contains n single-day periods
• It contains n-1 two-day periods
• It contains n-2 three-day periods
• And so on...

The total count for a period of length n is n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2.

Return the total count of all smooth descent periods in the given price array.

Intuition

The key insight is that we need to find all contiguous segments where prices decrease by exactly 1 each day, then count all possible subarrays within each segment.

When we find a smooth descent segment of length n, we need to count how many valid periods it contains. Let's think about this with an example: if we have prices [5, 4, 3, 2] (length 4), the valid periods are:

• Length 1: [5], [4], [3], [2] → 4 periods
• Length 2: [5,4], [4,3], [3,2] → 3 periods
• Length 3: [5,4,3], [4,3,2] → 2 periods
• Length 4: [5,4,3,2] → 1 period

Total: 4 + 3 + 2 + 1 = 10 periods

This follows the pattern n + (n-1) + (n-2) + ... + 1, which equals n*(n+1)/2 using the arithmetic series formula.

So our strategy becomes:

1. Find each maximal smooth descent segment (where prices drop by exactly 1 consecutively)
2. For each segment of length cnt, add cnt*(cnt+1)/2 to our answer
3. Move to the next segment and repeat

We use two pointers to efficiently identify these segments: pointer i marks the start of a segment, and we advance pointer j as long as the smooth descent condition holds (prices[j-1] - prices[j] == 1). Once the condition breaks, we've found a complete segment from index i to j-1, calculate its contribution, then move i to j to start looking for the next segment.

This approach ensures we count every valid smooth descent period exactly once while traversing the array only once, giving us an efficient O(n) solution.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

We implement the solution using a two-pointer technique to identify and count smooth descent periods efficiently.

Algorithm Steps:

1. Initialize variables:

   • ans = 0 to store the total count of smooth descent periods
   • i = 0 as the starting pointer for the current segment
   • n = len(prices) to store the array length

2. Main loop - iterate through the array:

   while i < n:

   For each position i, we need to find the longest smooth descent period starting from this position.

3. Find the end of current smooth descent segment:

   j = i + 1
   while j < n and prices[j - 1] - prices[j] == 1:
       j += 1

   • Start j at i + 1 (the next position)
   • Keep advancing j as long as the price drops by exactly 1 from the previous day
   • Stop when we reach the end of array or the smooth descent condition breaks

4. Calculate contribution of current segment:

   cnt = j - i
   ans += (1 + cnt) * cnt // 2

   • cnt = j - i gives us the length of the current smooth descent segment
   • Using the arithmetic series formula, a segment of length cnt contributes (1 + cnt) * cnt // 2 smooth descent periods
   • This is equivalent to 1 + 2 + 3 + ... + cnt

5. Move to the next segment:

   i = j

   Update i to j to start searching for the next smooth descent segment.

6. Return the result: After processing all segments, return ans which contains the total count.

Time Complexity: O(n) where n is the length of the prices array. Each element is visited at most twice (once by pointer i and once by pointer j).

Space Complexity: O(1) as we only use a constant amount of extra space for variables.

Example Walkthrough

Let's walk through the solution with prices = [8, 6, 5, 4, 3, 5, 4].

Initial State:

• ans = 0, i = 0, n = 7

Iteration 1: Starting at i = 0 (price = 8)

• Set j = 1
• Check: prices[0] - prices[1] = 8 - 6 = 2 ≠ 1
• Smooth descent breaks immediately
• Segment length: cnt = j - i = 1 - 0 = 1
• Contribution: (1 + 1) * 1 // 2 = 1
• Update: ans = 0 + 1 = 1, i = 1

Iteration 2: Starting at i = 1 (price = 6)

• Set j = 2
• Check: prices[1] - prices[2] = 6 - 5 = 1 ✓ (continue)
• Advance j = 3
• Check: prices[2] - prices[3] = 5 - 4 = 1 ✓ (continue)
• Advance j = 4
• Check: prices[3] - prices[4] = 4 - 3 = 1 ✓ (continue)
• Advance j = 5
• Check: prices[4] - prices[5] = 3 - 5 = -2 ≠ 1 (stop)
• Found segment [6, 5, 4, 3] from index 1 to 4
• Segment length: cnt = 5 - 1 = 4
• Contribution: (1 + 4) * 4 // 2 = 10
  • This counts: [6], [5], [4], [3] (4 singles)
  • Plus: [6,5], [5,4], [4,3] (3 pairs)
  • Plus: [6,5,4], [5,4,3] (2 triples)
  • Plus: [6,5,4,3] (1 quadruple)
  • Total: 4 + 3 + 2 + 1 = 10
• Update: ans = 1 + 10 = 11, i = 5

Iteration 3: Starting at i = 5 (price = 5)

• Set j = 6
• Check: prices[5] - prices[6] = 5 - 4 = 1 ✓ (continue)
• Advance j = 7
• We've reached the end of the array
• Found segment [5, 4] from index 5 to 6
• Segment length: cnt = 7 - 5 = 2
• Contribution: (1 + 2) * 2 // 2 = 3
  • This counts: [5], [4] (2 singles) and [5,4] (1 pair)
• Update: ans = 11 + 3 = 14, i = 7

End: i = 7 ≥ n, loop terminates

Final Answer: 14 smooth descent periods total

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array prices.

The algorithm uses a two-pointer approach with variables i and j. The outer while loop iterates through the array with pointer i, and the inner while loop advances pointer j to find consecutive descent periods (where each price is exactly 1 less than the previous price). Although there are nested loops, each element in the array is visited at most twice - once by pointer i and once by pointer j. Since i is always set to j after processing each descent period, both pointers traverse the array only once in total. Therefore, the overall time complexity is linear: O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space regardless of the input size. The variables used are:

• ans: stores the running count of descent periods
• i and j: two pointers for traversing the array
• n: stores the length of the array
• cnt: stores the length of the current descent period

All these variables require constant space, making the space complexity O(1).

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

Common Pitfalls

1. Off-by-One Error in Counting Segments

Pitfall: A common mistake is incorrectly calculating the contribution of each smooth descent segment. Developers might use the wrong formula or miscount the length.

Example of incorrect implementation:

# WRONG: Using wrong formula
ans += cnt * (cnt - 1) // 2  # This misses single-element periods

# WRONG: Miscounting the segment length
cnt = j - i - 1  # This would undercount by 1

Solution: Remember that a segment from index i to j-1 (where j is the first index that breaks the pattern) has length j - i. The number of subarrays in a segment of length n is n*(n+1)/2.

2. Incorrect Boundary Check in While Loop

Pitfall: Forgetting to check array bounds or using the wrong comparison operator when extending the smooth descent segment.

Example of incorrect implementation:

# WRONG: Missing boundary check
while prices[j - 1] - prices[j] == 1:  # Can cause IndexError
    j += 1

# WRONG: Using wrong indices
while j < n and prices[j] - prices[j + 1] == 1:  # IndexError when j = n-1
    j += 1

Solution: Always check j < n before accessing prices[j], and use prices[j-1] - prices[j] == 1 to compare consecutive elements correctly.

3. Handling Single-Element Arrays

Pitfall: Not properly handling edge cases like single-element arrays or forgetting that single elements count as smooth descent periods of length 1.

Example scenario:

prices = [5]  # Should return 1, not 0

Solution: The algorithm naturally handles this case since when i = 0 and the array has one element, j becomes 1, cnt = 1, and the formula (1+1)*1//2 = 1 gives the correct answer.

4. Integer Overflow in Formula Calculation

Pitfall: In languages with fixed integer sizes, calculating (1 + cnt) * cnt might cause overflow for very large values of cnt.

Solution: In Python, this isn't an issue due to arbitrary precision integers. In other languages, consider using appropriate data types or reformulating the calculation:

# Alternative formulation to avoid overflow in other languages
ans += cnt // 2 * (cnt + 1) if cnt % 2 == 0 else (cnt + 1) // 2 * cnt

5. Resetting the Loop Counter Incorrectly

Pitfall: After processing a segment, incorrectly updating the starting position for the next iteration.

Example of incorrect implementation:

# WRONG: Skipping potential segments
i = j + 1  # This would skip the element at index j

# WRONG: Creating infinite loop
i = i + 1  # This might reprocess parts of segments

Solution: Set i = j after processing each segment. This ensures we start the next search from the first element that broke the previous smooth descent pattern, which could potentially be the start of a new smooth descent period.