206: Two Pointers, Sliding Window, Prefix Sums, Difference Arrays, and Running State

Learning outcomes

By the end of this lesson, you can:

explain and apply opposing pointers in a realistic implementation;
explain and apply same-direction pointers in a realistic implementation;
explain and apply fixed sliding window in a realistic implementation;
explain and apply variable sliding window in a realistic implementation;
explain and apply prefix sums in a realistic implementation.

The goal is not to recognize a pattern by name and then force it onto the input. You should be able to explain why a boundary can move, what state remains valid as it moves, and what the implementation costs in time and storage.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same kind of concern appeared: perhaps a bounded search, a batch of range updates, a rolling metric, or a query over a sequence. The point of the exercise is not to memorize terminology. It is to make a defensible decision both in an interview-sized problem and in a production data-processing problem, where the right approach follows from the constraints rather than from a memorized template.

Terminology

Opposing pointers: On sorted or symmetric data, left and right pointers shrink a search space according to a monotonic decision. Pair-sum searches and palindrome checks are common examples.
Same-direction pointers: A slow/fast or read/write pair can compact, partition, remove duplicates, or detect cycles while preserving an invariant about a prefix of the data.
Fixed sliding window: Maintain aggregate state while one element enters and one element leaves a constant-size window. When the aggregate supports incremental updates, this replaces O(nk) recomputation with O(n) work.
Variable sliding window: Expand a window until a constraint fails, then shrink it until the constraint is restored. The method is useful only when feasibility changes predictably as the boundaries move.
Prefix sums: Precompute cumulative values so that a range sum can be answered in O(1) time after preprocessing.
Difference arrays: Record changes at interval boundaries and recover the actual values with a prefix pass. This is useful for many range increments when intermediate point values do not need to be read immediately.

These terms describe ways to preserve and update running state. The shared idea is to avoid repeating work that the previous position has already made unnecessary. The details differ: two pointers usually narrow or maintain a boundary, a window maintains a contiguous region, and prefix-based techniques move work into preprocessing.

Mental model

Treat Two Pointers, Sliding Window, Prefix Sums, Difference Arrays, and Running State as a design problem with observable inputs, outputs, invariants, and failure modes. Many linear-time array and string solutions work because a small invariant is preserved while a boundary moves. They do not repeatedly calculate every candidate subarray from scratch.

That optimization is only half the design. A strong implementation also makes its assumptions visible, handles boundary conditions deliberately, and leaves enough evidence to show why the design is safe. That evidence might be tests, types, input constraints, metrics, or a diagram of the state transition. If the algorithm depends on sorted input, non-negative values, a fixed width, or monotonic feasibility, state that dependency instead of letting it remain an accidental precondition.

A useful sequence for both interviews and production work is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a familiar loop. First state what must remain true after each update. Then choose the mechanism that enforces that invariant. This is also the fastest way to debug an off-by-one error: identify the first boundary at which the invariant stopped being true.

Deep dive

1. Opposing pointers

Suppose the data is sorted and you need to decide whether two values satisfy a target relationship. A left pointer starts at one end and a right pointer starts at the other. The ordering gives each comparison meaning: if the current pair is too small, moving the left pointer right is the only direction that can increase the sum; if it is too large, moving the right pointer left is the direction that can decrease it. Each move discards candidates that no longer need to be examined.

The same shape appears in symmetric checks such as testing a palindrome. The left and right values are compared, and the pointers move inward until they meet or a mismatch is found. The approach is safe only when the data and decision rule provide that monotonicity. On unsorted data, moving a pointer may discard a valid pair, so sorting may be required and its O(n log n) cost must be included.

On sorted or symmetric data, left/right pointers can shrink a search space according to a monotonic decision, as in pair sums or palindrome checks.

Decision rule: Use opposing pointers deliberately when they make the contract or invariant easier to prove. If they merely reduce typing while hiding an assumption about ordering, symmetry, or duplicate handling, prefer a more explicit design.

2. Same-direction pointers

Same-direction pointers move through the data in the same general direction, but they do not necessarily move at the same speed. A read pointer can scan every item while a write pointer marks the next position for an item that should remain. This is the compacting pattern. The region before the write pointer has a precise meaning, such as “all values retained so far.”

The same idea supports partitioning, duplicate removal, and cycle detection. The useful distinction from opposing pointers is not just the direction of movement; it is the prefix invariant. At any point, the already-processed prefix must be correct, while the unread suffix remains unprocessed. In-place versions also require care about whether overwriting values is allowed and whether callers expect the original array to remain unchanged.

A slow/fast or read/write pair can compact, partition, remove duplicates, or detect cycles while preserving a prefix invariant.

Decision rule: Use same-direction pointers deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding assumptions about mutation, ordering, or which prefix is valid, prefer the more explicit design.

3. Fixed sliding window

When every candidate region has the same width, recomputing its aggregate from all k elements wastes the overlap between adjacent windows. A fixed sliding window keeps the current aggregate, adds the element entering on the right, and removes the element leaving on the left. The first window costs O(k); each later window costs O(1), for O(n) total work and O(1) additional state when the aggregate permits it.

This works cleanly for sums, counts, and other invertible aggregates. It does not automatically work for every aggregate. For example, removing the outgoing minimum from a plain variable is not enough to discover the next minimum; a deque or another data structure may be needed. The window must also define whether its endpoints are inclusive and what happens when the input is shorter than k.

Maintain aggregate state as one element enters and one leaves a constant-size window, reducing O(nk) recomputation to O(n) when the aggregate can be updated incrementally.

Decision rule: Use a fixed sliding window deliberately when it makes the contract or invariant easier to prove. If the aggregate cannot be updated correctly when an item leaves, or if the width is not actually constant, prefer a different design.

4. Variable sliding window

Variable windows are useful when the answer is a contiguous range subject to a constraint, such as “at most K distinct values.” The right boundary expands the candidate range. If the constraint is violated, the left boundary advances and removes values from the running state until the constraint is valid again. A frequency map, count, or other compact state usually records what the current window contains.

The reason this can be linear is that each boundary moves forward at most n times. The catch is monotonicity. If a valid window becomes invalid when an element is added, and removing elements from the left can restore validity without needing to reconsider earlier positions, the strategy is a good fit. With negative values, for example, a sum threshold may not behave monotonically, so blindly applying the pattern can miss the answer.

Expand until a constraint fails, then shrink until it is restored. This pattern depends on monotonicity; it does not work blindly when adding or removing elements can change feasibility unpredictably.

Decision rule: Use a variable sliding window deliberately when it makes the contract or invariant easier to prove. If feasibility is not monotonic, or if the desired range is not contiguous, prefer a more explicit search or dynamic-programming/data-structure approach.

5. Prefix sums

Repeated range-sum queries are expensive if each query walks its entire interval. A prefix array shifts that work into a preprocessing pass. With a leading zero, prefix[i] represents the sum of the first i values, and the half-open range [left, right) is answered as prefix[right] - prefix[left]. That indexing convention removes a special case for a range beginning at zero.

The trade-off is storage and update behavior: changing an input value normally requires updating every later prefix, so prefix sums are strongest when the data is static or queries substantially outnumber updates. The same idea extends to prefix counts, XOR, and multidimensional prefix tables, although each extension has its own operation and indexing rules.

Precompute cumulative values so range sums become O(1). Prefix counts, XOR, and multidimensional prefix tables generalize the idea to many repeated range queries.

Decision rule: Use prefix sums deliberately when they make the contract or invariant easier to prove. If the data changes frequently, if memory is constrained, or if the operation does not support the required subtraction or inverse, choose a structure designed for updates instead.

6. Difference arrays

Many interval updates have the same shape: add a value to every position in [left, right]. Applying each update directly can cost O(length of the interval). A difference array records only the boundary effects: add the value at left, and subtract it immediately after right. A later prefix pass accumulates those changes into the final point values.

This turns a batch of q updates over n positions into O(n + q) work, with the usual care around the extra boundary at right + 1. It is an offline technique: during the update phase, the actual value at an individual point is not yet available. If callers need immediate reads or arbitrary updates and queries interleaved, use a different structure, such as a Fenwick tree or segment tree when those operations and constraints justify it.

Record changes at interval boundaries and recover actual values with a prefix pass. Difference arrays are ideal for many range increments when intermediate point values are not needed immediately.

Decision rule: Use difference arrays deliberately when they make the batch-update contract and invariant easier to prove. If updates and reads must be interleaved, or if the endpoint convention cannot be made explicit, prefer a structure that supports the required online operations.

Worked example

Consider an interview-sized problem and a production data-processing problem. In both cases, start by writing the requirement in one sentence, list the input and output contracts, and identify which concept owns each failure mode. The important move is separation: parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. A shorter happy-path demo can mix these concerns, but that makes edge cases and ownership much harder to reason about.

The following small function is intentionally simple. It illustrates running state without pretending that every problem needs a more elaborate pointer or window structure. Before choosing a data structure, state what the state means. Here, after each iteration, answer is the greatest value encountered in the processed prefix.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is a subtle contract issue in this deliberately small example: an empty array returns 0, which is only meaningful if zero is an accepted identity or default. If the requirement is “return the maximum element,” empty input needs an explicit contract, such as number | undefined, an exception, or validation before calling the function. The code also assumes numeric values have already passed the boundary contract. TypeScript's number type does not reject NaN at runtime.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. For this function, duplicates do not change the maximum, but that does not make duplicate handling irrelevant in a real batch pipeline. A retry could process the same batch twice, and concurrency could change the data between reading and processing. Those behaviors belong in the surrounding contract, not in an unrelated Math.max call.

This is the level of explanation expected in a senior code review or technical interview: identify the invariant, expose the boundary assumptions, describe the failure result, and account for the stated complexity rather than only presenting a loop.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality inputs. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

For these patterns, production questions include whether input ordering is guaranteed, whether a batch can be replayed, whether a prefix or difference array fits in memory, and whether integer overflow or numeric precision can corrupt an aggregate. A theoretically linear solution can still be unsuitable if it retains an unbounded frequency map or performs an expensive sort that the requirement did not allow.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted.

Guided lab

Solve longest substring with at most K distinct values, range-sum queries, and batch interval increments. For each problem, write the window or prefix invariant before coding and explain why the resulting design is O(n) or O(n + q). For the substring problem, make the monotonicity assumption explicit. For range sums, define the prefix indexing convention. For interval increments, specify whether the endpoints are inclusive and when the final prefix pass occurs.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

The lab does not require a production-sized application. It does require enough evidence to distinguish an algorithm that is correct under its stated constraints from one that merely passes the first example.

Edge cases and failure modes

Opposing pointers: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Same-direction pointers: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Fixed sliding window: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Variable sliding window: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Prefix sums: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.

Also test the boundary conventions that are specific to the implementation: a window of width zero or one, input shorter than the fixed width, K equal to zero, a query covering the first or last element, adjacent intervals, and an update that ends at the final index. These are the cases most likely to expose an off-by-one error or an incorrect empty-input assumption. Difference arrays are part of the lesson's topic as well, so apply the same boundary discipline to their extra terminal slot.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. In pointer code, log or inspect the pointer positions and the state they summarize. In a variable window, inspect the counts immediately before and after each shrink. In prefix code, compare one small range against a direct sum. In a difference-array implementation, inspect both boundary markers before running the reconstruction pass.

Interview questions

What problem does Opposing pointers solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Same-direction pointers solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Fixed sliding window solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Variable sliding window solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Prefix sums solve, and what trade-off or failure mode would make you choose a different approach?

Answer these in terms of the input contract and invariant, not just the pattern name. A strong answer should mention when the approach is invalid, what it costs, and what evidence you would use to debug a failure.

Checkpoint

Without notes, explain Two Pointers, Sliding Window, Prefix Sums, Difference Arrays, and Running State to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

If you cannot explain why a pointer may advance permanently, revisit monotonicity and the prefix invariant. If you cannot explain a range result in constant time, write out the prefix indices for a small example. The checkpoint is meant to expose gaps in reasoning, not to reward vocabulary recall.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.