1. At Most Problems

---

💡 The Core Trick

Exactly K = AtMost(K) − AtMost(K−1)

Any “count subarrays with exactly K” problem can be solved by:

1. Solving “at most K” with the sliding window count pattern
2. Subtracting “at most K-1”

This works because: exactly(K) = atMost(K) - atMost(K-1)

---

📐 The AtMost Template

int atMost(vector<int>& A, int K) {
    if (K < 0) return 0;    // guard for atMost(-1) calls
    int res = 0, j = 0;
    // ... window state variables ...
    for (int i = 0; i < A.size(); i++) {
 
        // 1. add A[i] to state
        // ...
 
        // 2. shrink while state > K
        while (/* state > K */) {
            // remove A[j] from state
            j++;
        }
 
        // 3. count: all subarrays ending at i, starting from j..i are valid
        res += i - j + 1;
    }
    return res;
}

Why res += i - j + 1?

If [j..i] is valid, so are [j+1..i], [j+2..i], ..., [i..i]. That’s exactly i - j + 1 valid subarrays all ending at i.

---

🔢 Problems

930. Binary Subarrays With Sum Medium

Count subarrays with exactly S ones.
State: running sum of 1s.

int numSubarraysWithSum(vector<int>& A, int S) {
    return atMost(A, S) - atMost(A, S - 1);
}
int atMost(vector<int>& A, int S) {
    if (S < 0) return 0;
    int res = 0, sum = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        sum += A[i];
        while (sum > S) sum -= A[j++];
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

---

992. Subarrays with K Different Integers Hard

Count subarrays with exactly K distinct integers.
State: frequency map + distinct count.

int subarraysWithKDistinct(vector<int>& A, int K) {
    return atMost(A, K) - atMost(A, K - 1);
}
int atMost(vector<int>& A, int K) {
    unordered_map<int, int> count;
    int res = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        count[A[i]]++;
        if (count[A[i]] == 1) K--;
        while (K < 0) {
            count[A[j]]--;
            if (count[A[j]] == 0) K++;
            j++;
        }
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(n)`

---

1248. Count Number of Nice Subarrays Medium

Count subarrays with exactly k odd numbers.
State: count of odd numbers.

int numberOfSubarrays(vector<int>& nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}
int atMost(vector<int>& A, int k) {
    int res = 0, odds = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        odds += A[i] % 2;
        while (odds > k) odds -= A[j++] % 2;
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

---

713. Subarray Product Less Than K Medium

Count subarrays with product strictly less than K. (At most variant — no subtraction needed!)
State: running product.

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int prod = 1, res = 0, j = 0;
    for (int i = 0; i < nums.size(); i++) {
        prod *= nums[i];
        while (prod >= k) prod /= nums[j++];
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

---

⚠️ When NOT to use At Most trick

At Most trick requires monotonic state

Works only when adding an element can ONLY increase the state, and removing can ONLY decrease it. If elements can be negative (e.g., sum problems with negatives), the while loop breaks. → Switch to Prefix Sum + HashMap for those cases.

---