Sliding Window & Prefix Sum Exercises (with Solutions)
Time to practice. Solve each problem yourself first — pick the right tool (fixed window, variable window, or prefix sum), code it, trace a small input by hand, and reason about its complexity. Only then open the answer sheet. Every View answer link jumps to a full, multi-language solution on the sliding window & prefix sum solutions page.
How to practice: Set a timer (15–20 min per problem). Stuck? Re-read the sliding window introduction or prefix sums before peeking. The pattern recognition is the skill you’re building.
Warm-ups
Q1. Maximum average of a size-k window. Given an integer array nums and an integer k, return the maximum average value of any contiguous subarray of length k. Target O(n) time, O(1) extra space.
Q2. Count windows with sum below a threshold. Given nums (non-negative) and a size k, count how many length-k windows have a sum strictly less than a given limit. Single pass.
Core problems
Q3. Longest substring without repeating characters. Given a string s, return the length of the longest substring that contains no repeated character. Aim for O(n).
Q4. Smallest subarray with sum ≥ target. Given an array of positive integers and a value target, return the length of the shortest contiguous subarray whose sum is at least target, or 0 if none exists. Target O(n).
Q5. Subarray sum equals k. Given an integer array nums (values may be negative) and an integer k, count the number of contiguous subarrays that sum to exactly k. Better than O(n²).
Challenge
Q6. Longest substring with at most K distinct characters. Given a string s and an integer k, return the length of the longest substring containing at most k distinct characters. Target O(n).
Q7. Range sum queries (immutable). Preprocess an integer array so that many sumRange(l, r) queries (inclusive) each answer in O(1). State the build cost.
Done? Review every solution on the answer sheet — even the ones you solved, since there’s often a cleaner template. Then continue to trees.