Counting Subarrays with a Sliding Window

EditorialUpdated Oct 25, 2026

Counting instead of finding the best

Subarray Product Less Than K doesn't want the longest window. It wants to know how many subarrays have a product below k. For [10, 5, 2, 6] with k = 100, the answer is 8: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6] and [5, 2, 6].

An array of 30,000 numbers has 450,015,000 subarrays, so checking them one by one is out. But the window from Variable-Size Sliding Window: Longest and Shortest already does almost all the work. For each right end it finds the smallest start that follows the rule. Counting needs just one more line.

Counting with a sliding window on [10, 5, 2, 6] with k = 100. When the right pointer is at index 3, the window runs from index 1 to index 3, [5, 2, 6], with product 60, below 100. Every subarray that ends at index 3 and starts inside the window also has a product below 100: [6], [2, 6] and [5, 2, 6]. So this step adds right − left + 1 = 3 to the count, without listing them one by one.

Every window ending at right counts

After the shrink, [left, right] follows the rule: its product is below k. Now look at the windows that end at right but start later: [left + 1, right], [left + 2, right], …, [right, right]. Each sits inside [left, right], so each follows the rule too (a product of positive whole numbers only shrinks when you drop some). And every start before left breaks it, which is why the window shrank past them.

So exactly right − left + 1 valid subarrays end at right. Add that on every step. Each subarray has exactly one right end, so the total counts every valid subarray once, and the scan stays O(n).

Counting the windows that end at each right — The window is shaded. After any shrink (the amber number leaves), the green numbers are the window, and every subarray ending at right inside it gets counted.

Template for counting

The loop is the longest-window template with best = max(...) replaced by a count:

int numSubarrayProductLessThanK(const vector<int>& nums, int k) {
    if (k <= 1) return 0;                    // every number is at least 1, so no product is below 1
    long long product = 1;
    int left = 0, count = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        product *= nums[right];              // grow
        while (product >= k) {               // shrink until the product is below k
            product /= nums[left];
            left++;
        }
        count += right - left + 1;           // every window that ends at right and starts at left or later
    }
    return count;
}

def num_subarray_product_less_than_k(nums, k):
    if k <= 1:
        return 0                             # every number is at least 1, so no product is below 1
    product = 1
    left = count = 0
    for right, x in enumerate(nums):
        product *= x                         # grow
        while product >= k:                  # shrink until the product is below k
            product //= nums[left]
            left += 1
        count += right - left + 1            # every window that ends at right and starts at left or later
    return count

static int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;                    // every number is at least 1, so no product is below 1
    long product = 1;
    int left = 0, count = 0;
    for (int right = 0; right < nums.length; right++) {
        product *= nums[right];              // grow
        while (product >= k) {               // shrink until the product is below k
            product /= nums[left];
            left++;
        }
        count += right - left + 1;           // every window that ends at right and starts at left or later
    }
    return count;
}

function numSubarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;                    // every number is at least 1, so no product is below 1
    let product = 1, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];              // grow
        while (product >= k) {               // shrink until the product is below k
            product /= nums[left];
            left++;
        }
        count += right - left + 1;           // every window that ends at right and starts at left or later
    }
    return count;
}

Each prints 8, 0, 6 and 0 for [10, 5, 2, 6] with k = 100, [1, 2, 3] with k = 0, [1, 1, 1] with k = 2 and [5, 5, 5] with k = 5.

Look at the first line. Every number is at least 1, so no product is ever below 1: when k is 1 or less, the answer is 0. Without that line the shrink would never stop, because even an empty window's product, 1, is still not below k.

Exactly K: at most K, minus at most K − 1

Subarrays with K Different Integers asks for subarrays with exactly k different values. That rule isn't monotone: drop a value from a window with exactly k and you might still have k, or k − 1. There's no single smallest start to keep, so the window can't count it directly.

"At most k" is monotone, and the window counts it. Then subtract: every subarray has some number of different values, j. It's counted in at most(k) when j ≤ k, and in at most(k − 1) when j ≤ k − 1. The difference keeps exactly the subarrays with j = k.

For [1, 2, 1, 2, 3] with k = 2: at most 2 counts 12, at most 1 counts 5, and 12 − 5 = 7.

Exactly k as a subtraction, on [1, 2, 1, 2, 3] with k = 2. A long bar shows the 12 subarrays with at most 2 different values. Its first part, 5 subarrays, has at most 1; the rest, 7 subarrays, has exactly 2. So exactly 2 = at most 2 − at most 1 = 12 − 5 = 7.

long long atMostDistinct(const vector<int>& nums, int k) {   // subarrays with at most k different values
    unordered_map<int, int> count;
    long long total = 0;
    int left = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        count[nums[right]]++;
        while ((int)count.size() > k) {                        // too many different values: shrink
            if (--count[nums[left]] == 0) count.erase(nums[left]);
            left++;
        }
        total += right - left + 1;
    }
    return total;
}

long long subarraysWithKDistinct(const vector<int>& nums, int k) {
    return atMostDistinct(nums, k) - atMostDistinct(nums, k - 1);
}

def subarrays_with_k_distinct(nums, k):
    def at_most(k):                          # subarrays with at most k different values
        count, left, total = {}, 0, 0
        for right, x in enumerate(nums):
            count[x] = count.get(x, 0) + 1
            while len(count) > k:            # too many different values: shrink
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            total += right - left + 1
        return total

    return at_most(k) - at_most(k - 1)

static long atMostDistinct(int[] nums, int k) {     // subarrays with at most k different values
    Map<Integer, Integer> count = new HashMap<>();
    long total = 0;
    int left = 0;
    for (int right = 0; right < nums.length; right++) {
        count.merge(nums[right], 1, Integer::sum);
        while (count.size() > k) {                     // too many different values: shrink
            if (count.merge(nums[left], -1, Integer::sum) == 0) count.remove(nums[left]);
            left++;
        }
        total += right - left + 1;
    }
    return total;
}

static long subarraysWithKDistinct(int[] nums, int k) {
    return atMostDistinct(nums, k) - atMostDistinct(nums, k - 1);
}

function atMostDistinct(nums, k) {            // subarrays with at most k different values
    const count = new Map();
    let total = 0, left = 0;
    for (let right = 0; right < nums.length; right++) {
        count.set(nums[right], (count.get(nums[right]) || 0) + 1);
        while (count.size > k) {                     // too many different values: shrink
            const c = count.get(nums[left]) - 1;
            if (c === 0) count.delete(nums[left]);
            else count.set(nums[left], c);
            left++;
        }
        total += right - left + 1;
    }
    return total;
}

function subarraysWithKDistinct(nums, k) {
    return atMostDistinct(nums, k) - atMostDistinct(nums, k - 1);
}

Each prints 7, 3 and 6 for [1, 2, 1, 2, 3] with k = 2, [1, 2, 1, 3, 4] with k = 3 and [1, 1, 1] with k = 1. The same subtraction solves Binary Subarrays With Sum (a sum of exactly goal, on 0s and 1s), Count Number of Nice Subarrays (exactly k odd numbers) and Substrings with K Distinct Characters.

At least: count the starts before left

Number of Substrings Containing All Three Characters flips the rule again: a window that holds a, b and c keeps holding them when it grows. So, for each right, shrink while the window still holds all three. When it stops, every start before left gave a window that held all three, so add left:

def number_of_substrings(s):
    count = {"a": 0, "b": 0, "c": 0}
    left = total = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while count["a"] and count["b"] and count["c"]:   # it still holds all three: shrink
            count[s[left]] -= 1
            left += 1
        total += left        # every start before left gives a window that holds all three
    return total

It prints 10, 3 and 1 for "abcabc", "aaacb" and "abc".

When to use it, and when it breaks

Clues: "count the subarrays / substrings such that…", with a rule of the kind the last lesson handled: at most k, a product or sum below k with positive numbers, at least one of each. "Exactly k" means two windows and a subtraction.

It breaks for the same reason the last lesson's window did: negative numbers. Here's the counter for "sum at most 0" on [-1, 2, -1]:

def count_sum_at_most(nums, k):
    window_sum = left = count = 0
    for right, x in enumerate(nums):
        window_sum += x
        while window_sum > k and left <= right:
            window_sum -= nums[left]
            left += 1
        count += right - left + 1
    return count

It returns 2, but there are 3: [-1], [-1] and the whole array, [-1, 2, -1], whose sum is 0. When 2 arrives the sum goes above 0, so the loop drops the first -1 for good, not knowing the next -1 would bring the sum back down. With all-positive numbers it's right (it matches a brute force on 400 random inputs). With negatives, Subarray Sum Equals K uses prefix sums and a hash map, in the Prefix Sum section.

Common mistakes

Adding right - left instead of right - left + 1.

On [10, 5, 2, 6] with k = 100 it returns 4, not 8. It forgets the window of just the one number at right: [10], [5], [2] and [6] are never counted.

No guard for k ≤ 1.

On [1, 2, 3] with k = 0 it crashes with IndexError: list index out of range. Every product is at least 1, so the product never drops below 0 and left runs off the end of the array. Return 0 when k ≤ 1.

Counting exactly k with one window. if len(count) == k: total += right - left + 1

On [1, 2, 1, 2, 3] with k = 2 it returns 11, not 7. The windows ending at right that start after left can have fewer than k values, so they don't all count. Use at most k minus at most k − 1.

Check yourself

Quiz

1 / 5

Multiple choice

Counting subarrays with a product below k: after the shrink, left = 1 and right = 3. How many subarrays does this step add?

Practice problems

From easier to harder:

Subarray Product Less Than K: the counting template.
Binary Subarrays With Sum: exactly a sum, as at most minus at most.
Count Number of Nice Subarrays: exactly k odd numbers, the same subtraction.
Number of Substrings Containing All Three Characters: at least, so count the starts before left.
Substrings with K Distinct Characters: exactly k letters.
Subarrays with K Different Integers: exactly k values, with a count per value.

Then try the Sliding Window Quiz at the end of this section.