Count Strictly Increasing Subarrays - Practice Coding Problems

Count Strictly Increasing Subarrays - Problem

You are given an array nums consisting of positive integers. Return the number of subarrays of nums that are in strictly increasing order.

A subarray is a contiguous part of an array. A sequence is strictly increasing if each element is greater than the previous element.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,2,4,5]

› Output: 8

💡 Note: Strictly increasing subarrays: [1], [3], [2], [4], [5], [1,3], [2,4], [4,5], [2,4,5] = 8 total

Example 2 — All Increasing

$ Input: nums = [1,2,3,4]

› Output: 10

💡 Note: All subarrays are increasing: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], [1,2,3,4] = 10 total

Example 3 — Single Element

$ Input: nums = [5]

› Output: 1

💡 Note: Only one subarray [5], which is trivially increasing

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,3,2,4,5]

Find Sequences

Identify increasing sequences: [1,3] and [2,4,5]

Count Subarrays

Each sequence contributes multiple valid subarrays

Key Takeaway

🎯 Key Insight: Use the formula length×(length+1)/2 to count subarrays from each increasing sequence

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that each increasing sequence of length n contributes n×(n+1)/2 subarrays. Best approach uses single pass tracking to identify sequences and calculate contributions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray to see if it's strictly increasing
Single Pass with Length Tracking	O(n)	O(1)	Track the length of current increasing sequence and calculate contributions

Brute Force - Check All Subarrays — Algorithm Steps

Generate all possible subarrays using nested loops
For each subarray, check if elements are in strictly increasing order
Count and return total valid subarrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Check Each

Verify if each subarray is strictly increasing

Count Valid

Sum up all valid strictly increasing subarrays

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int count = 0;
    
    // Check all possible subarrays
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            // Check if subarray nums[i:j+1] is strictly increasing
            int isIncreasing = 1;
            for (int k = i; k < j; k++) {
                if (nums[k] >= nums[k + 1]) {
                    isIncreasing = 0;
                    break;
                }
            }
            if (isIncreasing) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: n² subarrays, each taking O(n) to verify

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler