templates · Two pointers, windows & prefix sums

Prefix sums + HashMap

  • Many "sum of nums[l..r]" queries on an array that does not change
  • "Count (or find the longest) subarray with sum exactly k"
  • The numbers can be negative, so a sliding window breaks
  • "Equal number of 0s and 1s": turn 0 into −1 and look for sum 0

Prefix sum + HashMapPrefix sums

the one rule

The invariant

When you stand at index i, the map holds every prefix sum that ends before i, so sum - k finds subarrays ending at i.

write it from memory

The template

prefix array, O(1) range sum

javajava.util.*
/** prefix[i] = nums[0] + … + nums[i - 1], so any range sum is one subtraction. */class RangeSum {    private final long[] prefix;     RangeSum(int[] nums) {        prefix = new long[nums.length + 1];           // one extra slot: prefix[0] = 0        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];    }     /** Sum of nums[left..right], both ends included. */    long sumRange(int left, int right) {        return prefix[right + 1] - prefix[left];    }}

The extra slot prefix[0] = 0 removes every "if left == 0" special case.

count subarrays with sum k

javajava.util.*
/** How many subarrays add up to exactly k. Works with negative numbers too. */static int countSumK(int[] nums, int k) {    Map<Long, Integer> seen = new HashMap<>();        // prefix sum → how many times seen    seen.put(0L, 1);                                  // the empty prefix, for subarrays starting at 0    long sum = 0;    int count = 0;    for (int x : nums) {        sum += x;                                     // prefix sum up to here        count += seen.getOrDefault(sum - k, 0);       // earlier prefixes that leave exactly k        seen.merge(sum, 1, Integer::sum);             // record AFTER the lookup    }    return count;}

If sum(0..i) - sum(0..j) = k, then nums[j+1..i] sums to k. So look up sum - k in the map.

fill in the blanks — only these lines change per problem

  1. line 3What the map stores: a count (for "how many") or the first index (for "longest").
  2. line 4The seed for the empty prefix: put(0, 1) for counting, put(0, -1) for lengths.
  3. line 8How the running value changes per element: sum += x, sum += (x == 0 ? -1 : 1) for equal 0s and 1s, or keep sum modulo k for "divisible by k".
  4. line 9Which earlier prefix you need: sum - k, or the same remainder for "divisible by k".

longest subarray with sum k

javajava.util.*
/** Longest subarray with sum exactly k. Store the FIRST index of each prefix sum. */static int longestSumK(int[] nums, int k) {    Map<Long, Integer> first = new HashMap<>();       // prefix sum → first index where it appeared    first.put(0L, -1);                                // empty prefix "ends" before index 0    long sum = 0;    int best = 0;    for (int i = 0; i < nums.length; i++) {        sum += nums[i];        Integer j = first.get(sum - k);        if (j != null) best = Math.max(best, i - j);  // subarray (j, i] sums to k        first.putIfAbsent(sum, i);                    // keep the earliest, for the longest answer    }    return best;}

Same idea, but the map stores the first index of each sum, and putIfAbsent keeps it.

fill in the blanks — only these lines change per problem

  1. line 11merge to count every time, putIfAbsent to keep only the first index.

complexity

What it costs

time O(n)
One pass; each HashMap get and put is O(1) on average (put is amortized, because the table sometimes resizes). The worst case with many collisions is higher, rare in practice.
space O(n)
The prefix array or the map can hold up to n + 1 different prefix sums.

watch out

Common bugs

  • Forgetting the seed put(0, 1). Then subarrays that start at index 0 are never counted.
  • Recording the current sum before the lookup. With k = 0 it then counts an empty subarray.
  • For remainders, Java's % can be negative: use ((sum % k) + k) % k.

use it

Practise it on

learn it properly