Array and Hashing Patterns: Two Pointers, Sliding Window, Prefix Sum and Frequency Maps

Version note: The code in this post was built with .NET 10 and C# 14 and verified with tests written with xUnit v3 4.0.2 and Microsoft.Extensions.TimeProvider.Testing 10.11.0; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

Bookstore's marketing team wants a "buy two books together for exactly 60 TL, shipping free" campaign. We need a method that finds two books in the catalog whose prices add up to exactly 60. The first solution that comes to mind is to try every book with every other book.

With 1,000 books in the catalog this solution takes around 0.14 ms. How long does it take when the catalog reaches 100,000 books: 30 ms, 3 seconds? How long does the version that does the same job with a Dictionary take with 100,000 books?

Two Sum: From O(n²) to O(n)

All the patterns in this post share one idea: do the repeated work of the nested loop once and remember the result. The cleanest example is two sum.

namespace Algorithms.Patterns;

public static class TwoSum
{
    // O(n^2): every pair
    public static (int, int)? BruteForce(int[] prices, int target)
    {
        for (int i = 0; i < prices.Length; i++)
            for (int j = i + 1; j < prices.Length; j++)
                if (prices[i] + prices[j] == target) return (i, j);
        return null;
    }

    // O(n): remember what we have seen, ask "have I seen the complement?"
    public static (int, int)? WithDictionary(int[] prices, int target)
    {
        Dictionary<int, int> seenAt = new(prices.Length);
        for (int i = 0; i < prices.Length; i++)
        {
            if (seenAt.TryGetValue(target - prices[i], out int j)) return (j, i);
            seenAt.TryAdd(prices[i], i); // keep the first index for duplicates
        }
        return null;
    }

    // sorted input: two pointers, O(n) and no extra memory
    public static (int, int)? SortedTwoPointers(int[] sorted, int target)
    {
        int left = 0, right = sorted.Length - 1;
        while (left < right)
        {
            int sum = sorted[left] + sorted[right];
            if (sum == target) return (left, right);
            if (sum < target) left++;   // need a bigger sum: only moving left can do that
            else right--;               // need a smaller sum
        }
        return null;
    }
}

Brute force answers "is there a price that adds up to 60 with this one?" for every price by walking the whole list. The Dictionary version asks the same question at every step but gets the answer in O(1): it keeps the prices seen so far in a hash table. If the price is 12, it looks for 48; if 48 has been seen, the pair is found. The cost is O(n) extra memory. The two pointers version does the same job on sorted input with no extra memory; we come back to it shortly.

The one detail that needs care is duplicate values. If the target is 60 and the list has a single 30, the 30 must not pair with itself. Because looking for the complement happens before adding the current price, this works correctly on its own:

[Fact]
public void TwoSum_DuplicateValues_UsesTwoDifferentIndexes()
{
    Assert.Equal((0, 2), TwoSum.WithDictionary([30, 10, 30], 60));
    Assert.Null(TwoSum.WithDictionary([30, 10], 60));
}

The benchmark measures the worst case: the only matching pair is the last two elements of the list, so both versions have to go all the way to the end.

[GlobalSetup]
public void Setup()
{
    // distinct even prices >= 10; the only matching pair is the last two items (worst case for both)
    _prices = [.. Enumerable.Range(0, N).Select(i => 10 + i * 2)];
    _prices[^2] = 1;
    _prices[^1] = 3;
    _target = 4;
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method     | N      | Mean             | Ratio | Allocated |
|----------- |------- |-----------------:|------:|----------:|
| BruteForce | 1000   |       135.716 us |  1.00 |         - |
| Dictionary | 1000   |         3.287 us |  0.02 |   22192 B |
|            |        |                  |       |           |
| BruteForce | 10000  |    12,393.128 us | 1.000 |         - |
| Dictionary | 10000  |        35.698 us | 0.003 |  202226 B |
|            |        |                  |       |           |
| BruteForce | 100000 | 1,691,487.141 us | 1.001 |         - |
| Dictionary | 100000 |       323.704 us | 0.000 | 2172963 B |

Back to the opening question. With 1,000 books brute force takes 0.14 ms; with 100,000 books, 1.69 seconds. The data grew 100 times and the time grew about 12,500 times: quadratic growth itself (10,000 times expected, plus the effect of a large array no longer fitting in the cache). The Dictionary version goes from 3.3 µs to 324 µs on the same data, in proportion to the data; at 100,000 books it is more than 5,000 times faster than brute force. The price is in the "Allocated" column: a 2.1 MB Dictionary for 100,000 prices. The measurement ran while other work was running on the machine; look at the ratios. The general technique of collapsing nested loops into a single pass like this is in the Big-O and Complexity series post "Deriving Time Complexity from Code".

Frequency Maps and Grouping

The most common form of two sum's "remember what you have seen" is counting. How many books of each genre were sold, how many orders each customer placed, how many times each word was searched? The hand-written version and CountBy, which arrived in .NET 9:

public static Dictionary<string, int> CountByHand(IEnumerable<string> genres)
{
    Dictionary<string, int> counts = [];
    foreach (string genre in genres)
        counts[genre] = counts.GetValueOrDefault(genre) + 1;
    return counts;
}

[Fact]
public void FrequencyMap_ByHand_MatchesCountBy()
{
    string[] genres = ["sci-fi", "classic", "sci-fi", "poetry", "sci-fi", "classic"];

    Dictionary<string, int> byHand = FrequencyMap.CountByHand(genres);
    Dictionary<string, int> byLinq = genres.CountBy(g => g).ToDictionary();

    Assert.Equal(byLinq, byHand);
    Assert.Equal(3, byHand["sci-fi"]);
}

CountBy and AggregateBy do what used to be done with GroupBy(...).Select(g => (g.Key, g.Count())) without building an intermediate list per group; the details are in the LINQ (Language Integrated Query) series post "LINQ and .NET 9: CountBy, AggregateBy and Index". The hand-written loop follows the same logic; both are O(n) time and memory proportional to the number of distinct keys.

One step beyond the frequency map is grouping with a cleverly chosen key. To find words made of the same letters (anagrams), it is enough to sort each word's letters and use that as the key: "dune" and "nude" both land on the key "denu".

// anagram groups: same letters, any order -> same sorted key
public static List<List<string>> GroupAnagrams(IEnumerable<string> words)
{
    Dictionary<string, List<string>> groups = [];
    foreach (string word in words)
    {
        char[] letters = word.ToCharArray();
        Array.Sort(letters);
        string key = new(letters);
        if (!groups.TryGetValue(key, out List<string>? group))
            groups[key] = group = [];
        group.Add(word);
    }
    return [.. groups.Values];
}

In real life the same idea shows up as a "normalized key": e-mail addresses stripped of case and whitespace, ISBNs (International Standard Book Numbers) with the hyphens removed, customer records that write the same address differently. Once you find the right key, grouping is a single pass over a Dictionary.

Two Pointers

If the input is sorted, you do not even need a hash table. SortedTwoPointers puts one pointer on the smallest price and the other on the largest. If the sum is below the target, the only way to increase it is to move the left one forward; if it is above, to move the right one back. One pointer moves per step and the work ends when they meet: at most n steps, O(1) extra memory.

The intuition for why it never misses a pair: when the sum is below the target we drop the left price, because that price cannot reach the target even with the largest price, so it cannot with any other price either. Each step eliminates a price that has been proven not to be part of the answer.

The same two pointer idea also removes duplicates from a sorted array without extra memory. One pointer reads, the other marks where the next unique value will be written:

// removes duplicates from a sorted array in place, returns the new length
public static int Dedupe(int[] sorted)
{
    if (sorted.Length == 0) return 0;
    int write = 1;
    for (int read = 1; read < sorted.Length; read++)
    {
        if (sorted[read] != sorted[write - 1])
            sorted[write++] = sorted[read];
    }
    return write;
}

[Fact]
public void Dedupe_SortedArray_KeepsFirstOfEachValue()
{
    int[] ids = [1, 1, 2, 3, 3, 3, 7];

    int length = TwoPointers.Dedupe(ids);

    Assert.Equal([1, 2, 3, 7], ids[..length]);
}

The read and write pointers are also the solution to the RemoveAll exercise in the series' second post: each element is copied at most once, so it is O(n).

Sliding Window

A sliding window computes a value over a consecutive range (the window) and, when the window moves one step, accounts only for the element entering and the element leaving instead of recomputing from scratch. There are two kinds. A fixed-width window answers questions such as "the highest sales total over 7 consecutive days":

// best total of any k consecutive days: fixed-size window, add the new day, drop the old one
public static long MaxSumOfK(int[] dailySales, int k)
{
    long window = 0;
    for (int i = 0; i < k; i++) window += dailySales[i];
    long best = window;
    for (int i = k; i < dailySales.Length; i++)
    {
        window += dailySales[i] - dailySales[i - k];
        best = Math.Max(best, window);
    }
    return best;
}

In a variable-width window, the window grows on the right until a condition breaks, then shrinks on the left. The classic example is "the longest substring without repeating characters":

// length of the longest substring without repeating characters
public static int LongestUnique(string text)
{
    Dictionary<char, int> lastSeen = [];
    int best = 0, start = 0;
    for (int end = 0; end < text.Length; end++)
    {
        // a repeat inside the window: jump start past its previous position
        if (lastSeen.TryGetValue(text[end], out int previous) && previous >= start)
            start = previous + 1;
        lastSeen[text[end]] = end;
        best = Math.Max(best, end - start + 1);
    }
    return best;
}

[Theory]
[InlineData("abcabcbb", 3)]
[InlineData("bbbb", 1)]
[InlineData("", 0)]
[InlineData("abba", 2)]
public void LongestUnique_ReturnsLength(string text, int expected) =>
    Assert.Equal(expected, SlidingWindow.LongestUnique(text));

The "abba" test exists for that previous >= start check. When the second b is seen, start jumps to 2. Then a arrives; a was last seen at index 0, but that is now outside the window. Without the check, start would go back to 1 and the result would wrongly be 3.

A real sliding window at Bookstore: accept at most N requests from a client to the search API (Application Programming Interface) in the last 60 seconds. We keep the times of accepted requests in a queue and, on every new request, drop the times that have left the window from the front:

// sliding log: allows at most "limit" requests in any "window"-long period
public sealed class SlidingWindowRateLimiter(int limit, TimeSpan window, TimeProvider clock)
{
    private readonly Queue<DateTimeOffset> _accepted = new();

    public bool TryAcquire()
    {
        DateTimeOffset now = clock.GetUtcNow();
        // evict timestamps that left the window: the window is (now - window, now]
        while (_accepted.Count > 0 && _accepted.Peek() <= now - window)
            _accepted.Dequeue();
        if (_accepted.Count >= limit) return false;
        _accepted.Enqueue(now);
        return true;
    }
}

To be able to test time, we take a TimeProvider instead of DateTime.UtcNow; in the test we advance the clock by hand with FakeTimeProvider. Exactly where the window boundary lies (second 59 must be rejected, second 60 accepted) is an off-by-one question, and the test spells it out:

[Fact]
public void RateLimiter_AtMostLimitPerWindow()
{
    FakeTimeProvider clock = new(new DateTimeOffset(2026, 11, 8, 10, 0, 0, TimeSpan.Zero));
    SlidingWindowRateLimiter limiter = new(limit: 3, TimeSpan.FromSeconds(60), clock);

    bool[] first = [limiter.TryAcquire(), limiter.TryAcquire(), limiter.TryAcquire(), limiter.TryAcquire()];
    clock.Advance(TimeSpan.FromSeconds(59));
    bool at59 = limiter.TryAcquire();
    clock.Advance(TimeSpan.FromSeconds(1));
    bool at60 = limiter.TryAcquire();

    Assert.Equal([true, true, true, false], first);
    Assert.False(at59);
    Assert.True(at60);
}

In production you do not need to write this yourself: SlidingWindowRateLimiter in System.Threading.RateLimiting and ASP.NET Core's rate limiting middleware apply the same idea with less memory by splitting the window into segments. Our sliding log version is exact but keeps as many timestamps as the limit; the segmented version is approximate but uses constant memory.

Prefix Sum

Bookstore's sales report screen asks "total sales from this date to that date" thousands of times a day. Summing the range on every query is O(range length). A prefix sum reduces it to a single subtraction: if prefix[i] is the total of the first i days, the total of the range [from, to] is prefix[to + 1] - prefix[from].

public sealed class PrefixSum
{
    private readonly long[] _prefix; // _prefix[i] = sum of the first i days; _prefix[0] = 0

    public PrefixSum(int[] values)
    {
        _prefix = new long[values.Length + 1];
        for (int i = 0; i < values.Length; i++) _prefix[i + 1] = _prefix[i] + values[i];
    }

    // sum of values[from..to] inclusive, O(1)
    public long RangeSum(int from, int to) => _prefix[to + 1] - _prefix[from];
}

Making the array one element longer and choosing _prefix[0] = 0 is deliberate: thanks to the definition "the total of the first 0 days", the formula does not change when the range starts at the beginning, and there is no special case. The totals are long because summing a year of daily sales in an int can overflow. Building is O(n), each query O(1).

Where prefix sums meet hash tables is one of the nicest examples: "how many consecutive ranges add up to exactly k?" When values can be negative (refunds), a sliding window does not work, because growing the window does not always increase the sum. But since the total of the range [i, j] is prefix[j] - prefix[i], the number of ranges ending at j with total k equals the number of previously seen prefixes whose value is prefix[j] - k:

// how many contiguous ranges sum to exactly k (values may be negative, e.g. refunds)
public static int CountEqualTo(int[] values, int k)
{
    Dictionary<long, int> prefixCounts = new() { [0] = 1 }; // the empty prefix
    long prefix = 0;
    int count = 0;
    foreach (int value in values)
    {
        prefix += value;
        // a range ending here sums to k if an earlier prefix equals prefix - k
        count += prefixCounts.GetValueOrDefault(prefix - k);
        prefixCounts[prefix] = prefixCounts.GetValueOrDefault(prefix) + 1;
    }
    return count;
}

[Theory]
[InlineData(new[] { 1, 1, 1 }, 2, 2)]
[InlineData(new[] { 3, 4, 7, -2, 2, 1, 4, 2 }, 7, 6)]
[InlineData(new[] { 5 }, 5, 1)]
public void SubarraySum_CountsRanges(int[] values, int k, int expected) =>
    Assert.Equal(expected, SubarraySum.CountEqualTo(values, k));

The { [0] = 1 } initial entry is the most forgotten line in this post. To count ranges that start at the very beginning of the array, the prefix that has taken no elements, that is 0, must have been seen once. The third test catches exactly that: in the single-element array [5], the answer for k=5 is 1. Without the initial entry it would be 0.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.ArrayPatternTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (573ms)

Test run summary: Passed!
  total: 15
  failed: 0
  succeeded: 15

Which Pattern When?

Behind every row in the table is the same question: what is the nested loop computing over and over, and where can I compute it once and keep it? Sometimes the answer is a hash table, sometimes two indexes, sometimes a prefix array.

In Production

O(n) memory is not always better than O(n²) time. A Dictionary doing two sum over a 100-million-line log file needs gigabytes of memory; at that point sorting the data and using two pointers without extra memory, or leaving the job to the database (a JOIN or a GROUP BY), is the better call. This trade-off between time and memory is in the Big-O and Complexity series post "Space Complexity".

Use a prefix sum when the data will not change. If sales for past days change during the day (refunds, corrections), every change invalidates all later prefixes and rebuilding is O(n). For range sums over frequently updated data, structures such as a Fenwick tree or a segment tree do both operations in O(log n).

Keeping a rate limiter in a single process's memory means that with several instances each instance enforces its own limit. If you need a distributed limit, the counter must live somewhere shared such as Redis; that is covered in the System Design series post "Designing Rate Limiting: Token Bucket, Sliding Window and a Distributed Rate Limiter".

Common Pitfalls

Off-by-one at window boundaries. Decide at the top of the code whether a window is [start, end] or [start, end) and write it in a comment; whether you compute the length as end - start + 1 or end - start depends on it. Always test boundary values such as second 59 and second 60 in the rate limiter test.

Forgetting the initial entry in the prefix map. Without { [0] = 1 }, ranges that start at the beginning of the array are not counted, and the bug shows only on some inputs.

Reversing the order in two sum. Adding the current price to the dictionary and then looking for its complement pairs an element with itself in a case like 30 + 30 = 60.

Keeping totals in an int. Prefix sums and window totals grow quickly; use long, or catch overflow with checked where it matters.

A Small Experiment

★☆☆ Change SortedTwoPointers to return every pair whose sum is exactly the target. With duplicate prices, what do you need to do to avoid returning the same pair twice?

★★☆ Write a sliding window that finds "the longest consecutive run of sales containing at most k different genres". Keep the genres in the window in a frequency map; do not forget to remove a genre from the map when its count drops to zero.

★★★ Extend PrefixSum to two dimensions: write a PrefixSum2D that returns the total of any rectangle in a shelf × day grid in O(1). Hint: prefix[r + 1, c + 1] = grid[r, c] + prefix[r, c + 1] + prefix[r + 1, c] - prefix[r, c].

We saw that two pointers needs sorted input. In the next post we move on to sorting itself: why insertion sort is still valuable, merge sort, and the most overlooked property of sorting, stability. With a real bug where Array.Sort does not keep equal elements in order.