Sliding Window and Prefix Sum

Solution and explanation

Sliding window

A window is a contiguous range [left, right] of an array or string. Instead of recomputing every subarray from scratch, slide the window: add the element entering on the right and remove the one leaving on the left. This turns many O(n·k) or O(n²) problems into O(n).

• Fixed-size window: size k stays constant (maximum sum of k consecutive days of sales).
• Variable-size window: expand right until a condition breaks, then shrink left until it holds again (longest substring without repeats, smallest subarray with sum ≥ target).

// Fixed window template
int windowSum = 0;
for (int right = 0; right < a.length; right++) {
    windowSum += a[right];                     // element enters
    if (right >= k) windowSum -= a[right - k]; // element leaves
    if (right >= k - 1) { /* use windowSum */ }
}

Prefix sum

prefix[i] = a[0] + … + a[i−1]. Then the sum of any range [l, r] is prefix[r+1] − prefix[l] in O(1) after O(n) preprocessing.

a      = [3, 1, 4, 1, 5]
prefix = [0, 3, 4, 8, 9, 14]
sum(1..3) = prefix[4] - prefix[1] = 9 - 3 = 6   (1 + 4 + 1)

int[] prefix = new int[a.length + 1];
for (int i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] + a[i];
int rangeSum = prefix[r + 1] - prefix[l];

Prefix sum + HashMap

Storing counts of prefix sums in a HashMap answers "how many subarrays sum to k" in O(n), even with negative numbers (where a sliding window fails).

When to use which

• All numbers non-negative and you need contiguous ranges → sliding window.
• Many range-sum queries or negative numbers → prefix sums (with a HashMap).

Complexity

• Sliding window: O(n) time, O(1) or O(k) space. Prefix sums: O(n) build, O(1) per query, O(n) space.

Solution and explanation

Problem

Find the maximum sum of any contiguous subarray of exactly k elements.

[2, 1, 5, 1, 3, 2], k = 3 → 9 (5 + 1 + 3)

Approach 1: sum every window

For each start, add k elements. O(n·k).

Approach 2: fixed sliding window (optimal)

static int maxSumK(int[] a, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += a[i];
    int best = windowSum;
    for (int i = k; i < a.length; i++) {
        windowSum += a[i] - a[i - k];     // add new, remove old
        best = Math.max(best, windowSum);
    }
    return best;
}

Dry run

• First window [2,1,5] = 8
• Slide: +1 −2 → 7; +3 −1 → 9; +2 −5 → 6 → best 9

Complexity

• Brute force O(n·k). Sliding window O(n) time, O(1) space.

Solution and explanation

Problem

Find the length of the longest substring with all distinct characters.

"abcabcbb" → 3 ("abc")
"bbbbb"    → 1
"pwwkew"   → 3 ("wke")

Approach 1: check every substring

O(n³) naive or O(n²) with a set per start.

Approach 2: variable sliding window with last-seen positions (optimal)

Keep the window [left, right] free of repeats. When s[right] was seen inside the window, jump left past its previous position.

static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last.containsKey(c) && last.get(c) >= left) left = last.get(c) + 1;
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry run on "abcabcbb"

• a b c → window "abc", best 3
• a repeats (at 0) → left 1; b repeats → left 2; c repeats → left 3 …
• best stays 3.

Complexity

• O(n) time, O(min(n, alphabet)) space.

Solution and explanation

Problem

Given strings s and t, find the smallest substring of s containing every character of t (with multiplicity).

s = "ADOBECODEBANC", t = "ABC" → "BANC"

Approach: variable window with counts (optimal)

1. Count the characters needed from t.
2. Expand right; when a needed character's count is satisfied, increase formed.
3. While all characters are satisfied, record the window and shrink from the left.

static String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int required = t.length(), left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) required--;       // a needed char entered
        while (required == 0) {
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
            if (++need[s.charAt(left++)] > 0) required++;   // a needed char left
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

Complexity

• O(|s| + |t|) time: each index enters and leaves the window once. O(1) space (128 counters).

Note: brute force over all substrings is O(n²) windows × O(n) checks = O(n³).

Solution and explanation

Problem

Count contiguous subarrays whose sum equals k. Numbers may be negative.

[1, 1, 1], k = 2 → 2
[1, 2, 3], k = 3 → 2  ([1,2] and [3])

Approach 1: every subarray

Two loops with a running sum: O(n²).

Approach 2: prefix sum + HashMap (optimal)

A subarray (j, i] sums to k when prefix[i] − prefix[j] = k, i.e. prefix[j] = prefix[i] − k. Count how often each prefix sum has occurred.

static int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);                       // empty prefix
    int sum = 0, result = 0;
    for (int x : nums) {
        sum += x;
        result += count.getOrDefault(sum - k, 0);
        count.merge(sum, 1, Integer::sum);
    }
    return result;
}

Dry run on [1, 2, 3], k = 3

• sum 1: need −2 → 0; store 1
• sum 3: need 0 → 1 (subarray [1,2]); store 3
• sum 6: need 3 → 1 (subarray [3]) → total 2

Complexity

• O(n²) brute force. Prefix + HashMap O(n) time, O(n) space.

Note: a sliding window does not work here because negative numbers break the "shrink when too large" rule.

Solution and explanation

Problem

Answer many queries sum(l, r) on a fixed array efficiently.

Approach 1: loop per query

O(n) per query → O(n·q) total.

Approach 2: prefix sums (optimal for a fixed array)

class NumArray {
    private final int[] prefix;
    NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
    }
    int sumRange(int l, int r) { return prefix[r + 1] - prefix[l]; }
}

Example

nums = [-2, 0, 3, -5, 2, -1]; prefix = [0, -2, -2, 1, -4, -2, -3]

• sumRange(0, 2) = 1 − 0 = 1
• sumRange(2, 5) = −3 − (−2) = −1

With updates

If values change between queries, use a Fenwick tree (Binary Indexed Tree) or a segment tree: O(log n) for both update and query.

2D version

prefix[i][j] over a matrix gives any sub-rectangle sum in O(1) using inclusion–exclusion.

Complexity

• Prefix sums: O(n) build, O(1) per query, O(n) space.

Solution and explanation

Problem

Find the length of the longest subarray whose sum equals k.

[10, 5, 2, 7, 1, 9], k = 15 → 4 ([5, 2, 7, 1])

Approach 1: all subarrays

O(n²).

Approach 2: sliding window (only when all numbers are non-negative)

Expand right; while the sum exceeds k, shrink left; record the length when sum == k. O(n), O(1) space.

static int longestNonNegative(int[] a, int k) {
    int left = 0, sum = 0, best = 0;
    for (int right = 0; right < a.length; right++) {
        sum += a[right];
        while (sum > k && left <= right) sum -= a[left++];
        if (sum == k) best = Math.max(best, right - left + 1);
    }
    return best;
}

Approach 3: prefix sum + first-occurrence HashMap (works with negatives)

Store the first index where each prefix sum appears; if sum − k was seen at index j, the subarray (j, i] sums to k.

static int longestSubarray(int[] a, int k) {
    Map<Integer, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0, -1);
    int sum = 0, best = 0;
    for (int i = 0; i < a.length; i++) {
        sum += a[i];
        if (firstIndex.containsKey(sum - k)) best = Math.max(best, i - firstIndex.get(sum - k));
        firstIndex.putIfAbsent(sum, i);         // keep the earliest index for the longest span
    }
    return best;
}

Complexity

• Brute force O(n²). Sliding window O(n)/O(1) for non-negative arrays. Prefix + HashMap O(n)/O(n) in general.