We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Strictly Increasing Subarrays

Number: 2535

Difficulty: Medium

Paid? Yes

Companies: Bridgewater Associates

Problem Description

Given an array of positive integers, count the number of contiguous subarrays that are strictly increasing. A subarray is a contiguous portion of the array, and every single element subarray is considered strictly increasing.

Key Insights

  • Every single element subarray is strictly increasing by default.
  • A subarray of length > 1 is strictly increasing if each element is greater than its previous element.
  • Instead of enumerating every subarray, we can count the number of strictly increasing subarrays ending at each index.
  • By maintaining the length of the current increasing sequence, we can add the current sequence length (which represents the number of new subarrays ending at the current index) to a total counter.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array, since we do a single pass. Space Complexity: O(1) as we only use a few extra variables.

Solution

We iterate over the array while tracking the length of the current strictly increasing sequence. For each index, if the current element is greater than the previous one, we increment our counter for the sequence; otherwise, we reset it to 1. The current sequence length indicates how many new strictly increasing subarrays end at the current index. Summing these counts gives the final answer.

Code Solutions

# Python solution with line-by-line comments
def count_increasing_subarrays(nums):
    # Initialize total count with the count of single-element subarrays.
    total_subarrays = 0
    # Initialize current sequence length.
    current_length = 0
    
    # Iterate through each element in the list
    for i in range(len(nums)):
        # If the current element is the first element or greater than the previous element,
        # increase the length of the current strictly increasing sequence.
        if i == 0 or nums[i] > nums[i - 1]:
            current_length += 1
        else:
            # Otherwise, reset the sequence length to just the current element.
            current_length = 1
        # Add the current sequence length to the total since it represents all subarrays ending at i.
        total_subarrays += current_length
    
    return total_subarrays

# Example usage:
nums = [1,3,5,4,4,6]
print(count_increasing_subarrays(nums))  # Output: 10
← Back to All Questions