Skip to content
DSA sliding window 11 min read

Sliding Window & Prefix Sum Solutions: Answer Sheet

This is the answer sheet for the sliding window & prefix sum exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here.

Q1. Maximum average of a size-k window

Idea: This is a fixed-size window. Find the maximum window sum by add-one/subtract-one sliding, then divide by k once at the end (dividing per step just adds rounding noise).

Complexity: O(n) time, O(1) space.

#include <vector>
#include <algorithm>
double maxAverage(const std::vector<int>& nums, int k) {
    long long sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];
    long long best = sum;
    for (int r = k; r < (int)nums.size(); r++) {
        sum += nums[r] - nums[r - k];
        best = std::max(best, sum);
    }
    return (double)best / k;
}

Pitfall: Comparing averages each step instead of sums invites floating-point error. Track the integer sum; divide once.

Q2. Count windows with sum below a threshold

Idea: Slide a fixed window of size k, maintaining the running sum with add-one/subtract-one, and increment a counter whenever the current window sum is < limit.

Complexity: O(n) time, O(1) space.

#include <vector>
int countWindows(const std::vector<int>& nums, int k, long long limit) {
    int n = nums.size();
    if (n < k) return 0;
    long long sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];
    int count = (sum < limit) ? 1 : 0;
    for (int r = k; r < n; r++) {
        sum += nums[r] - nums[r - k];
        if (sum < limit) count++;
    }
    return count;
}

Pitfall: Forgetting to test the very first window before the slide loop undercounts by one. Check it after building the first window.

Q3. Longest substring without repeating characters

Idea: A variable-size window. Grow the right edge; when the incoming character is already inside, shrink the left edge until the duplicate is gone. Track the widest valid window.

Complexity: O(n) time, O(min(n, alphabet)) space.

#include <string>
#include <unordered_map>
#include <algorithm>
int lengthOfLongest(const std::string& s) {
    std::unordered_map<char, int> count;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        count[s[r]]++;
        while (count[s[r]] > 1) count[s[l++]]--;
        best = std::max(best, r - l + 1);
    }
    return best;
}

Pitfall: Jumping l directly to “last seen index + 1” works but only if you guard against moving l backward; the shrink-while-duplicate version above avoids that trap entirely.

Q4. Smallest subarray with sum ≥ target

Idea: With positive values, growing the window only increases the sum and shrinking only decreases it — so a variable-size window works: expand r to reach the target, then shrink l as far as it stays >= target, recording the smallest width.

Complexity: O(n) time, O(1) space.

#include <vector>
#include <climits>
int minSubArrayLen(const std::vector<int>& nums, int target) {
    int l = 0, best = INT_MAX;
    long long sum = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        sum += nums[r];
        while (sum >= target) {
            best = std::min(best, r - l + 1);
            sum -= nums[l++];
        }
    }
    return best == INT_MAX ? 0 : best;
}

Pitfall: This monotonic shrink is only valid for non-negative values. With negatives, the sum isn’t monotonic in window size — switch to a prefix sum approach.

Q5. Subarray sum equals k

Idea: A sliding window fails here because negatives break monotonicity. Use prefix sums with a hash map: a subarray ending at r sums to k when some earlier prefix equals current - k. Count those earlier prefixes as you go.

Complexity: O(n) time, O(n) space.

#include <vector>
#include <unordered_map>
int subarraySum(const std::vector<int>& nums, int k) {
    std::unordered_map<long long, int> seen;
    seen[0] = 1;
    long long sum = 0;
    int count = 0;
    for (int x : nums) {
        sum += x;
        auto it = seen.find(sum - k);
        if (it != seen.end()) count += it->second;
        seen[sum]++;
    }
    return count;
}

Pitfall: Omitting the {0: 1} seed misses every subarray that starts at index 0. Also, look up sum - k before inserting sum.

Q6. Longest substring with at most K distinct characters

Idea: A variable-size window holding a frequency map. Grow r; whenever the map has more than k distinct keys, shrink l, removing keys whose count hits zero. Record the widest valid window.

Complexity: O(n) time, O(k) space.

#include <string>
#include <unordered_map>
#include <algorithm>
int longestKDistinct(const std::string& s, int k) {
    if (k == 0) return 0;
    std::unordered_map<char, int> count;
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        count[s[r]]++;
        while ((int)count.size() > k) {
            if (--count[s[l]] == 0) count.erase(s[l]);
            l++;
        }
        best = std::max(best, r - l + 1);
    }
    return best;
}

Pitfall: Failing to delete a key when its count drops to zero makes count.size overstate the distinct count, shrinking the window too aggressively.

Q7. Range sum queries (immutable)

Idea: Build a prefix sum array once with a leading zero; then sumRange(l, r) = prefix[r+1] - prefix[l] answers each query in O(1).

Complexity: O(n) build time, O(n) space, O(1) per query.

#include <vector>
class NumArray {
    std::vector<long long> prefix;
public:
    NumArray(const std::vector<int>& nums) : prefix(nums.size() + 1, 0) {
        for (int i = 0; i < (int)nums.size(); i++)
            prefix[i + 1] = prefix[i] + nums[i];
    }
    long long sumRange(int l, int r) { return prefix[r + 1] - prefix[l]; }
};

Pitfall: This assumes the array never changes. If values get updated between queries, a static prefix sum goes stale — use a Fenwick tree for O(log n) updates and queries.

That’s the full answer sheet. Back to the exercises or continue to trees.

Last updated June 25, 2026
Was this helpful?