Pattern Guide
Counting Patterns
"Count pairs, subarrays, paths. Always ask: what structure enables efficient counting?"
Counting problems ask "how many X satisfy condition Y?" The brute force is O(n²) or O(2^n). Efficient counting exploits structure: prefix sums for subarrays, hashmaps for pair conditions, bit manipulation for subsets, DP for sequences. Learn to recognize which technique each signal requires.
Problems you can solve with this pattern
5 problems · click any to start solving
// Count subarrays with sum EXACTLY k
// O(n) with prefix sum + hashmap
function countSubarraysSum(nums, k) {
const map = new Map([[0, 1]]); // prefix sum 0 seen once
let count = 0, sum = 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 sum AT MOST k (all positive):
function atMost(nums, k) {
let lo=0, sum=0, count=0;
for (let hi=0; hi<nums.length; hi++) {
sum += nums[hi];
while (sum > k) sum -= nums[lo++];
count += hi - lo + 1; // all subarrays ending at hi with valid sum
}
return count;
}
// Count subarrays with sum EXACTLY k using atMost:
// f(exactly k) = f(atMost k) - f(atMost k-1)
// Count pairs with sum = target
function countPairs(nums, target) {
const map = new Map();
let count = 0;
for (const n of nums) {
count += map.get(target - n) ?? 0;
map.set(n, (map.get(n) ?? 0) + 1);
}
return count;
}Counting problems have a deceptive pattern: they look like search problems but actually need mathematical insight. "Count subarrays with sum k" seems to need nested loops but is O(n) with prefix sums. "Count pairs with XOR = target" seems O(n²) but is O(n) with a hashmap. The key: identify what property you're counting, find the right structure that compresses the redundancy.
| Count what? | Technique | Complexity |
|---|---|---|
| Subarrays with sum = k | Prefix sum + HashMap | O(n) |
| Pairs (i,j) with nums[i]+nums[j]=target | HashMap (complement lookup) | O(n) |
| Inversions in array | Merge sort or BIT | O(n log n) |
| Subarrays with at most k distinct | Sliding window | O(n) |
| Subsets with property | Bitmask DP | O(2^n) |
| Numbers in [lo, hi] satisfying digit property | Digit DP | O(log n × state) |
| Sequences satisfying recurrence | DP | O(n²) or O(n) |
| Points in convex hull | Andrew's monotone chain | O(n log n) |
Key Templates
// Count subarrays with sum EXACTLY k
// O(n) with prefix sum + hashmap
function countSubarraysSum(nums, k) {
const map = new Map([[0, 1]]); // prefix sum 0 seen once
let count = 0, sum = 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 sum AT MOST k (all positive):
function atMost(nums, k) {
let lo=0, sum=0, count=0;
for (let hi=0; hi<nums.length; hi++) {
sum += nums[hi];
while (sum > k) sum -= nums[lo++];
count += hi - lo + 1; // all subarrays ending at hi with valid sum
}
return count;
}
// Count subarrays with sum EXACTLY k using atMost:
// f(exactly k) = f(atMost k) - f(atMost k-1)
// Count pairs with sum = target
function countPairs(nums, target) {
const map = new Map();
let count = 0;
for (const n of nums) {
count += map.get(target - n) ?? 0;
map.set(n, (map.get(n) ?? 0) + 1);
}
return count;
}- "Count subarrays with sum = k" → prefix sum + hashmap O(n)
- "Count subarrays with exactly k odd/distinct" → atMost(k) - atMost(k-1)
- "Count pairs with XOR condition" → XOR trie
- "Count inversions" → merge sort or BIT
- "Count paths in grid" → DP (unique paths pattern)
- "Count numbers with digit property" → digit DP
- "Count subsets with property" → bitmask DP (n ≤ 20)
- "Count with range [lo, hi]" → f(hi) - f(lo-1) (difference trick)