Counting Subarrays with a Sliding Window: At Most, At Least and Exactly K

"At most": add hi − lo + 1

When validity survives shrinking, the longest valid window ending at hi contains every valid subarray ending at hi: they are exactly its suffixes, the subarrays starting at lo, lo + 1, …, hi. So instead of recording a length, add hi − lo + 1. The loop is the longest-window loop with one line changed.

Subarrays of [10, 5, 2, 6] with product below 100.

Step 1 / 4

nums
100lo/hi512263
product10count1
Multiply by 10: the window 0..0 has product 10. The 1 subarray ending at 0 that start at 0 or later all qualify. Total 1.
Step 2 / 4

nums
100lo51hi2263
product50count3
Multiply by 5: the window 0..1 has product 50. The 2 subarrays ending at 1 that start at 0 or later all qualify. Total 3.
Step 3 / 4

nums
10051lo22hi63
product10count5
Multiply by 2: the window 0..2 has product 100. Not below 100, so divide out 10; now 10. The 2 subarrays ending at 2 that start at 1 or later all qualify. Total 5.
Step 4 / 4

nums
10051lo2263hi
product60count8
Multiply by 6: the window 1..3 has product 60. The 3 subarrays ending at 3 that start at 1 or later all qualify. Total 8.

The code

The guard for k ≤ 1 matters: no product of positive integers is below 1, and without it the shrinking loop would divide past the right end.

def count_product_below(nums, k):
    if k <= 1:
        return 0                       # no product of positive integers is below 1
    total = lo = 0
    prod = 1
    for hi, x in enumerate(nums):
        prod *= x
        while prod >= k:               # shrink until the window is valid
            prod //= nums[lo]
            lo += 1
        total += hi - lo + 1           # every start from lo to hi works
    return total

#include <vector>

long long solve(const std::vector<int>& nums, long long k) {
    if (k <= 1) return 0;                 // no product of positive integers is below 1
    long long total = 0, prod = 1;
    int lo = 0;
    for (int hi = 0; hi < (int)nums.size(); ++hi) {
        prod *= nums[hi];
        while (prod >= k) prod /= nums[lo++];   // shrink until valid
        total += hi - lo + 1;                   // every start from lo to hi works
    }
    return total;
}

class Solution {
    public long countProductBelow(int[] nums, long k) {
        if (k <= 1) return 0;               // no product of positive integers is below 1
        long total = 0, prod = 1;
        int lo = 0;
        for (int hi = 0; hi < nums.length; hi++) {
            prod *= nums[hi];
            while (prod >= k) prod /= nums[lo++];   // shrink until valid
            total += hi - lo + 1;                   // every start from lo to hi works
        }
        return total;
    }
}

function countProductBelow(nums, k) {
  if (k <= 1) return 0;                // no product of positive integers is below 1
  let total = 0, lo = 0, prod = 1;
  for (let hi = 0; hi < nums.length; hi++) {
    prod *= nums[hi];
    while (prod >= k) prod /= nums[lo++];   // shrink until valid
    total += hi - lo + 1;                   // every start from lo to hi works
  }
  return total;
}

fn solve(nums: &[i64], k: i64) -> i64 {
    if k <= 1 { return 0; }               // no product of positive integers is below 1
    let (mut total, mut prod, mut lo) = (0i64, 1i64, 0usize);
    for hi in 0..nums.len() {
        prod *= nums[hi];
        while prod >= k {                 // shrink until valid
            prod /= nums[lo];
            lo += 1;
        }
        total += (hi + 1 - lo) as i64;    // every start from lo to hi works
    }
    total
}

import Data.Array

-- Fold carrying (window start, product, count); each step adds the starts that work for this end.
solve :: [Int] -> Int -> Int
solve nums k
  | k <= 1    = 0
  | otherwise = third (foldl step (0, 1, 0) (zip [0 ..] nums))
  where
    arr = listArray (0, length nums - 1) nums
    third (_, _, c) = c
    step (lo, prod, total) (hi, x) =
      let (lo', p') = shrink lo (prod * x)
      in (lo', p', total + hi - lo' + 1)
    shrink lo p
      | p >= k    = shrink (lo + 1) (p `div` (arr ! lo))
      | otherwise = (lo, p)

The same code is the reference solution to Count runs whose product is below k, where it is compiled and run against the tests in all six languages.

"At least": add lo

When validity survives growing, the valid starts for a fixed end are a prefix 0, 1, …, p. Shrink while the window is still valid; when the loop stops, lo has just passed the last valid start, so exactly lo starts work. Add lo.

Substrings of "abcabc" that hold a, b and c.

Step 1 / 6

s
a0lo/hib1c2a3b4c5
a1b0c0count0
'a' enters. No start works yet. Total 0.
Step 2 / 6

s
a0lob1hic2a3b4c5
a1b1c0count0
'b' enters. No start works yet. Total 0.
Step 3 / 6

s
a0b1loc2hia3b4c5
a0b1c1count1
'c' enters. The window holds all three, so shrink while it still does: lo moves from 0 to 1. Starts 0 to 0 all work for this end: add 1. Total 1.
Step 4 / 6

s
a0b1c2loa3hib4c5
a1b0c1count3
'a' enters. The window holds all three, so shrink while it still does: lo moves from 1 to 2. Starts 0 to 1 all work for this end: add 2. Total 3.
Step 5 / 6

s
a0b1c2a3lob4hic5
a1b1c0count6
'b' enters. The window holds all three, so shrink while it still does: lo moves from 2 to 3. Starts 0 to 2 all work for this end: add 3. Total 6.
Step 6 / 6

s
a0b1c2a3b4loc5hi
a0b1c1count10
'c' enters. The window holds all three, so shrink while it still does: lo moves from 3 to 4. Starts 0 to 3 all work for this end: add 4. Total 10.

"Exactly": the difference of two "at most" counts

"Exactly k distinct values" survives neither shrinking nor growing, so no single window counts it. But every subarray with at most k values has either exactly k or at most k − 1, so

exactly(k) = atMost(k) − atMost(k − 1)

Write atMost once, with the "add hi − lo + 1" loop, and call it twice.

Subarrays of [1, 2, 1, 2, 3] with exactly 2 distinct values: one pass for at most 2, one for at most 1.

Step 1 / 11

nums
10lo/hi21122334
atMost(2)1
At most 2: the window 0..0 has 1 value; add 1 subarrays ending at 0. Running total 1.
Step 2 / 11

nums
10lo21hi122334
atMost(2)3
At most 2: the window 0..1 has 2 values; add 2 subarrays ending at 1. Running total 3.
Step 3 / 11

nums
10lo2112hi2334
atMost(2)6
At most 2: the window 0..2 has 2 values; add 3 subarrays ending at 2. Running total 6.
Step 4 / 11

nums
10lo211223hi34
atMost(2)10
At most 2: the window 0..3 has 2 values; add 4 subarrays ending at 3. Running total 10.
Step 5 / 11

nums
10211223lo34hi
atMost(2)12
At most 2: the window 3..4 has 2 values; add 2 subarrays ending at 4. Running total 12.
Step 6 / 11

nums
10lo/hi21122334
atMost(1)1
At most 1: the window 0..0 has 1 value; add 1 subarrays ending at 0. Running total 1.
Step 7 / 11

nums
1021lo/hi122334
atMost(1)2
At most 1: the window 1..1 has 1 value; add 1 subarrays ending at 1. Running total 2.
Step 8 / 11

nums
102112lo/hi2334
atMost(1)3
At most 1: the window 2..2 has 1 value; add 1 subarrays ending at 2. Running total 3.
Step 9 / 11

nums
10211223lo/hi34
atMost(1)4
At most 1: the window 3..3 has 1 value; add 1 subarrays ending at 3. Running total 4.
Step 10 / 11

nums
1021122334lo/hi
atMost(1)5
At most 1: the window 4..4 has 1 value; add 1 subarrays ending at 4. Running total 5.
Step 11 / 11

answer7
Exactly 2 = at most 2 − at most 1 = 12 − 5 = 7.

TimeO(n) per pass

SpaceO(k)

The same identity counts subarrays with exactly k odd numbers, or with sum exactly S when the numbers are non-negative.

Counting windows

"At most": add hi − lo + 1

The code

"At least": add lo

"Exactly": the difference of two "at most" counts

Problems in this module