Skip to content
Katabench
Try free
7 min read The Katabench team

Sliding windows with fixed and variable sizes

Use a rolling sum for fixed-width windows and frequency counts for variable ones. Trace when the left edge moves and how C# handles negative values.

A meter reports the changes [4, -6, 7, 2, -3, 5] in stored energy, one per minute. Which three consecutive minutes have the highest total? The first three sum to 5. The next three share the -6 and the 7 with the first interval. Subtract the outgoing 4, add the incoming 2, and the next total is 3.

Now imagine a meter that records a source ID at each minute. You want the longest run served by at most two sources. A fixed schedule for evicting old readings no longer works. The right edge still advances by one minute at a time. The question that determines the algorithm is what makes the left edge move?

A fixed window has a departure schedule

With a width of three, once reading 3 arrives, reading 0 leaves. The pair of indices is always three apart. The middle values stay in the sum automatically, including when they are negative.

Each highlighted group contains three readings. A shift changes just two terms in the sum.
  1. First window

    1. 4
    2. -6
    3. 7
    4. 2
    5. -3
    6. 5

    Sum 5. Save it as the first maximum.

  2. Next minute

    1. 4
    2. -6
    3. 7
    4. 2
    5. -3
    6. 5

    Remove 4 and add 2. The sum falls to 3.

  3. Next minute

    1. 4
    2. -6
    3. 7
    4. 2
    5. -3
    6. 5

    Remove -6 and add -3. The sum rises to 6.

  4. Final minute

    1. 4
    2. -6
    3. 7
    4. 2
    5. -3
    6. 5

    Remove 7 and add 5. The sum is 4, so the maximum stays 6.

The update has two parts with different lifetimes. sum describes just the current interval. best survives across all intervals. Keeping those names distinct matters for an all-negative input. If every possible interval loses energy, the best interval still loses some. An initial maximum of zero would invent a three-minute interval the meter never measured.

C#
static long MaxSumOfWidth(int[] readings, int width)
{
    if (width < 1 || width > readings.Length)
        throw new ArgumentOutOfRangeException(nameof(width));

    long sum = 0;
    for (int i = 0; i < width; i++)
        sum += readings[i];

    long best = sum;
    for (int end = width; end < readings.Length; end++)
    {
        sum -= readings[end - width];
        sum += readings[end];
        best = Math.Max(best, sum);
    }

    return best;
}

An interval of width one returns the largest single reading. A width equal to the whole array returns its sum without entering the second loop. Both cases rely on recording the first complete interval before you slide. Using a long running sum also matters when the window moves. Collapsing the two lines to sum += incoming - outgoing makes C# subtract two int values first. That difference can overflow even when the final window sum fits in a long. C# arithmetic operators

For an array of length n and width w, summing from scratch reads w * (n - w + 1) elements. With 100,000 readings and a width of 20,000, that is 1,600,020,000 reads. The rolling calculation reads 20,000 to fill the initial window and two for each of the 80,000 shifts, for 180,000 array reads. Those are counts from the two loops, with no assumptions about the runtime or the processor.

A variable window needs an eviction rule

Consider the source-ID sequence [4, 4, 9, 4, 7, 7, 4, 7]. Up to index 3 the whole interval is valid. Reading 7 at index 4 introduces a third source. To restore the limit, dropping one 4 does nothing for the distinct count. Dropping the next 4 also leaves a 4 in the interval. Dropping the 9 finally eliminates a source, leaving the interval [4, 7] at indices 3 and 4. Those three evictions are why the implementation needs a frequency per source. A set alone cannot tell when the last 4 leaves.

After each insertion and its evictions, the left edge is the earliest start that gives a valid window ending here. The length at that point is the longest candidate with this right edge.

C#
static int LongestTwoSourceRun(int[] sources)
{
    var counts = new Dictionary<int, int>();
    int left = 0;
    int bestLength = 0;

    for (int right = 0; right < sources.Length; right++)
    {
        int incoming = sources[right];
        counts[incoming] = counts.GetValueOrDefault(incoming) + 1;

        while (counts.Count > 2)
        {
            int outgoing = sources[left];
            left++;
            counts[outgoing]--;
            if (counts[outgoing] == 0)
                counts.Remove(outgoing);
        }

        bestLength = Math.Max(bestLength, right - left + 1);
    }

    return bestLength;
}

After the repair at index 4, the remaining readings 7, 4 and 7 all extend the run. Its final length is five. Omitting the removal when a frequency reaches zero would leave source 9 in counts.Count after its last appearance. Taking the maximum before repair would make the first five readings look like a valid candidate, even though they contain three sources. Truncate the example after that first 7 and the error becomes visible. The answer for [4, 4, 9, 4, 7] is four.

Why can the algorithm leave the discarded starts behind for good? When [4, 4, 9, 4, 7] already contains three sources, extending its right edge can never reduce its source count. Every future run starting at index 0 will also fail. The same argument applies to each subsequent start discarded during repair. As soon as a start works, later starts ending at the same right edge can only make the run shorter.

Each reading enters once and leaves at most once. Even the inner loop that evicts three readings in one minute can perform at most n evictions over the entire scan. At most three keys appear in the dictionary, including the moment just before a repair. For the two-source problem, this gives O(n) time and O(1) auxiliary space. Increasing the limit to k sources allows up to k + 1 keys and changes the space bound accordingly.

Check whether a discarded start can become useful again

The fixed-width sum worked with negative readings because its eviction rule came straight from the clock. A different question, "longest interval whose total is at most 4," tempts you to shrink every time the sum exceeds 4. Try [6, -3, 1]. The first reading violates the limit, so that rule discards it. Two minutes later the entire interval sums to 4 and has length three. The discarded start was part of the answer.

For the meter measuring sources, a third source stays present in every rightward extension that retains the same start. On nonnegative readings, an oversized sum also stays oversized as you extend. With signed readings, check the actual condition before adopting a shrink loop. Questions that ask how many intervals have an exact signed total can use the repeated values of a running sum. Counting subarrays with prefix sums

One final detail matters when moving this code from an array to a live stream. Both loops use the array to retrieve whatever is leaving. An input iterator only exposes what is arriving. A rolling sum over the last 20,000 readings then needs a buffer for those 20,000 values, even though the array version uses only a handful of local variables. The source-ID version can instead store the most recent index of each source. When a third one arrives, jumping the left edge just past the least recent of those three positions removes that source entirely. The history your input provides changes what the implementation must retain.

The Max Sum Subarray of Size K and Fruit Into Baskets exercises let you try both eviction rules on long inputs. In the second exercise, pause when the third fruit type arrives and predict how many individual trees must leave before you update the maximum. C# coding challenges · Algorithm time budgets

Practice what you just read

More like this: C# coding challenges →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.