Pattern Guide
Counting Subarrays & Substrings
"Count subarrays satisfying constraints. Prefix sums, two pointers, "at most K" trick."
Count subarrays problems require counting contiguous segments satisfying a property: sum ≤ k, exactly k distinct elements, at most one zero, XOR = target. Key techniques: prefix sum counting (hashmap of prefix sums), "at most k" trick (exact k = atMost(k) - atMost(k-1)), two-pointer for monotone conditions, contribution technique (how many subarrays contain this element as min/max).
Problems you can solve with this pattern
4 problems · click any to start solving
// Count subarrays with sum = k using prefix sum HashMap
function subarraySum(nums, k) {
const map = new Map([[0, 1]]); // prefix sum → count
let sum = 0, count = 0;
for (const n of nums) {
sum += n;
count += (map.get(sum - k) || 0); // subarrays ending here with sum = k
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
// Count subarrays with exactly k distinct elements
// exactlyK(k) = atMost(k) - atMost(k-1)
function subarraysWithKDistinct(nums, k) {
function atMost(limit) {
const count = new Map();
let l = 0, result = 0;
for (let r = 0; r < nums.length; r++) {
count.set(nums[r], (count.get(nums[r]) || 0) + 1);
while (count.size > limit) {
const lv = nums[l++];
count.set(lv, count.get(lv) - 1);
if (!count.get(lv)) count.delete(lv);
}
result += r - l + 1; // all subarrays ending at r with ≤ limit distinct
}
return result;
}
return atMost(k) - atMost(k - 1);
}"Exactly k" = atMost(k) - atMost(k-1): convert exact-count problem to at-most, solved with two pointers. Prefix sum trick: count subarrays with sum = target using HashMap of prefix sum frequencies. XOR subarrays: same as sum but with XOR, HashMap of prefix XOR. Contribution: for each element as min/max, count subarrays where it's the min/max using next smaller/greater element.
// Count subarrays with sum = k using prefix sum HashMap
function subarraySum(nums, k) {
const map = new Map([[0, 1]]); // prefix sum → count
let sum = 0, count = 0;
for (const n of nums) {
sum += n;
count += (map.get(sum - k) || 0); // subarrays ending here with sum = k
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
// Count subarrays with exactly k distinct elements
// exactlyK(k) = atMost(k) - atMost(k-1)
function subarraysWithKDistinct(nums, k) {
function atMost(limit) {
const count = new Map();
let l = 0, result = 0;
for (let r = 0; r < nums.length; r++) {
count.set(nums[r], (count.get(nums[r]) || 0) + 1);
while (count.size > limit) {
const lv = nums[l++];
count.set(lv, count.get(lv) - 1);
if (!count.get(lv)) count.delete(lv);
}
result += r - l + 1; // all subarrays ending at r with ≤ limit distinct
}
return result;
}
return atMost(k) - atMost(k - 1);
}- Sum = k: prefix sum HashMap, count(prefix[i] - k)
- XOR = k: same but with XOR prefix array
- Exactly k distinct: atMost(k) - atMost(k-1)
- Contains all of set: last-seen positions, min(last_seen) + 1 per right pointer
atMost trick works when: "exactly k" = "at most k" - "at most k-1". This requires the property to be monotone: if subarray satisfies the property, any subarray containing it also satisfies it (or a related condition). Works for distinct counts, sum constraints with positive numbers.