Count Subarrays With Fixed Bounds - Practice Coding Problems

Count Subarrays With Fixed Bounds - Problem

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

The minimum value in the subarray is equal to minK.
The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5

› Output: 2

💡 Note: The fixed-bound subarrays are [1,3,5] and [1,3,5,2]. Both have min=1 and max=5.

Example 2 — Single Element

$ Input: nums = [1,1,1,1], minK = 1, maxK = 1

› Output: 10

💡 Note: All possible subarrays have min=max=1. There are 4+3+2+1=10 total subarrays.

Example 3 — No Valid Subarrays

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

› Output: 0

💡 Note: No subarray can have max=4 since 4 is not in the array.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ minK, maxK ≤ 10⁶
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,5,2,7,5] with minK=1, maxK=5

Process

Find subarrays where min=1 and max=5

Output

Count = 2 valid subarrays

Key Takeaway

🎯 Key Insight: Track positions of boundary values and invalid elements to count valid subarrays efficiently

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is to track the positions of minK, maxK, and invalid elements. Best approach uses sliding window with position tracking. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays and check if min equals minK and max equals maxK
Sliding Window with Tracking	O(n)	O(1)	Track last positions of minK, maxK, and invalid elements to count valid subarrays efficiently

Brute Force - Check All Subarrays — Algorithm Steps

Iterate through all possible starting positions
For each start, extend subarray and track min/max
Count subarrays with correct bounds

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Generate all possible subarrays

Check

Find min and max of each subarray

Count

Count those with correct bounds

Code -

solution.c — C

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

long long solution(int* nums, int numsSize, int minK, int maxK) {
    long long count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            int minVal = INT_MAX;
            int maxVal = INT_MIN;
            
            for (int k = i; k <= j; k++) {
                if (nums[k] < minVal) minVal = nums[k];
                if (nums[k] > maxVal) maxVal = nums[k];
            }
            
            if (minVal == minK && maxVal == maxK) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[10000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int minK, maxK;
    scanf("%d", &minK);
    scanf("%d", &maxK);
    
    printf("%lld\n", solution(nums, numsSize, minK, maxK));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: start position, end position, and finding min/max

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

22.0K Views

Medium Frequency

~25 min Avg. Time

850 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