⚡Flashcard Drill➔
NeetCode #696LC-2393Medium1-D Dynamic Programming
← Back to All Problems

#696 · #2393 · Count Strictly Increasing Subarrays(统计严格递增子数组的数目)

📌 Problem Statement & Constraints

Given an integer array nums, return the number of contiguous subarrays that are strictly increasing. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Every contiguous subarray of a strictly increasing run is itself strictly increasing.
  2. Let cur be the length of the strictly increasing run ending at the current index.
  3. If nums[i] > nums[i-1], extend the run with cur += 1; otherwise restart with cur = 1.
  4. Each index contributes exactly cur new increasing subarrays, namely all suffixes of the current run.

💻 Benchmark Python3 Implementation

class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        total = 0
        cur = 0                        # length of the increasing run ending here
        for i, x in enumerate(nums):
            if i > 0 and x > nums[i - 1]:
                cur += 1
            else:
                cur = 1
            total += cur               # every suffix of the run is valid
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single left-to-right pass.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Using >= instead of >: the subarrays must be strictly increasing, so equal neighbours break the run.
  • Counting only maximal runs: every sub-run counts, which is why cur is added at each index.
  • Resetting cur to 0: the current element alone is always a length-1 increasing subarray, so the reset value is 1.
  • Enumerating subarrays directly: that is O(n^2) and too slow for n = 10^5.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems