Prefix sums and frequency counts

Two small techniques, built on arrays and hash maps, solve a surprising number of problems. A prefix sum array stores the running total up to each position. The sum of any range from i to j is then prefix[j + 1] minus prefix[i].

You pay O(n) once to build it, and each range question after that is O(1). A frequency count tallies how often each value appears. Keep it in a hash map or, for a small alphabet like lowercase letters, an array of 26.

Anagrams, majority elements and "count the subarrays that sum to k" all come down to these; the last one keeps prefix sums in a hash map. In Java and C++, watch for integer overflow: a number growing past the largest value its type can hold and wrapping round to a wrong one.