Number of Valid Subarrays - Practice Coding Problems

Number of Valid Subarrays - Problem

Given an integer array nums, return the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray.

A subarray is a contiguous part of an array.

Example: For array [1, 4, 2, 5, 3], the subarray [1, 4, 2] is valid because the leftmost element 1 is not larger than 4 and 2. However, [4, 2] is not valid because 4 > 2.

Input & Output

Example 1 — Basic Case

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

› Output: 7

💡 Note: Valid subarrays: [1], [1,4], [1,4,2], [1,4,2,5], [1,4,2,5,3], [4], [5]. The element 1 can extend through the entire array since it's the minimum.

Example 2 — Single Element

$ Input: nums = [3]

› Output: 1

💡 Note: Only one subarray [3], which is valid since the leftmost (and only) element is not larger than itself.

Example 3 — Decreasing Array

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

› Output: 15

💡 Note: Every possible subarray is valid since each leftmost element is always >= subsequent elements. Total: 5+4+3+2+1 = 15 subarrays.

Constraints

1 ≤ nums.length ≤ 50,000
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

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

Valid Check

Count subarrays where first element ≤ all elements

Count Result

Total valid subarrays: 7

Key Takeaway

🎯 Key Insight: Use a monotonic stack to efficiently find the span where each element can serve as the leftmost leader

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is using a monotonic stack to efficiently find how far each element can extend as a leftmost element. The optimal approach uses a stack to maintain decreasing elements and calculates valid subarray counts in O(n) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - Optimal Solution	O(n)	O(n)	Use a monotonic decreasing stack to efficiently find the span of valid subarrays for each element
Brute Force - Check All Subarrays	O(n²)	O(1)	For each starting position, extend the subarray while the leftmost element remains valid

Monotonic Stack - Optimal Solution — Algorithm Steps

Step 1: Use a stack to maintain indices in decreasing order of values
Step 2: For each element, pop smaller elements and find its valid range
Step 3: Add the number of subarrays starting at current position to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Stack Setup

Maintain indices in decreasing order of values

Pop & Calculate

Pop larger elements and calculate valid subarrays

Push Current

Add current index to stack

Code -

solution.c — C

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

int solution(int* nums, int n) {
    int* stack = (int*)malloc(n * sizeof(int));
    int top = -1;
    int result = 0;
    
    for (int i = 0; i < n; i++) {
        while (top >= 0 && nums[stack[top]] > nums[i]) {
            top--;
        }
        
        if (top < 0) {
            result += i + 1;
        } else {
            result += i - stack[top];
        }
        
        stack[++top] = i;
    }
    
    free(stack);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n elements in worst case

⚡ Linearithmic Space

12.8K Views

Medium Frequency

~25 min Avg. Time

324 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

Monotonic Stack - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler