Array & Pointer Patterns

Linear array processing is the bedrock of algorithmic problem solving, yet naive multi-loop solutions frequently succumb to quadratic slowdowns. Master five fundamental pointer and accumulator paradigms—Prefix Sums, Difference Arrays, Two Pointers, Sliding Windows, and Floyd's Cycle Detection—that transform intractable $\mathcal{O}(n^2)$ scans into optimal $\mathcal{O}(n)$ time.

This module formalizes optimal linear sequence manipulation techniques, replacing repetitive traversals with analytical precomputation, stateful pointers, and invariant-driven boundary tracking.

By the end of this chapter, you will be able to:

1. Accelerate Static Range Queries: Formulate 1D and 2D prefix sums to answer arbitrary range sum queries in $\mathcal{O}(1)$ time.
2. Execute Batch Range Updates: Apply difference arrays to perform multiple offline range additions in $\mathcal{O}(1)$ time per update, reconstructing the final state in $\mathcal{O}(n)$ time.
3. Eliminate Quadratic Nested Loops: Design inward-converging and same-direction two-pointer strategies that traverse sorted sequences in linear time.
4. Implement Resizable Sliding Windows: Maintain running subarray states across fixed-length intervals and variable-length condition boundaries with amortized $\mathcal{O}(n)$ operations.
5. Prove Floyd's Cycle Detection: Derive the mathematical distance relation between head-to-entry and meet-to-entry segments in cyclic pointer structures.

Given an array $A$ of $n$ elements, answer $Q$ range sum queries of the form:

"What is the sum of elements from index $L$ to index $R$ inclusive?"

• Brute Force: Iterate from $L$ to $R$ for each query $⟹\mathcal{O}(n)$ per query, $\mathcal{O}(Q\cdot n)$ total.
• Prefix Sum Optimization: Precompute cumulative sums in $\mathcal{O}(n)$ time; answer each query in $\mathcal{O}(1)$ time and $\mathcal{O}(Q+n)$ overall.

Define array $P$ of length $n+1$ where $P[i]={\sum }_{k=0}^{i-1}A[k]$, with $P[0]=0$:

Trace Example:

Query: Sum from $L=2$ to $R=4$ (elements $4+1+5=10$):

To query the sum of any rectangular submatrix with top-left $(r_1,c_1)$ and bottom-right $(r_2,c_2)$ in $\mathcal{O}(1)$ time, construct 2D array $P$:

The query sum is computed via the 2D Principle of Inclusion-Exclusion:

Given an initial array of size $n$, perform $Q$ range additions of the form:

"Add value $v$ to all elements from index $L$ to index $R$ inclusive."

• Brute Force: Loop through indices $L\dots R$ for every update $⟹\mathcal{O}(n)$ per update, $\mathcal{O}(Q\cdot n)$ total.
• Difference Array Optimization: Apply updates in $\mathcal{O}(1)$ time per operation, reconstructing the final values in a single $\mathcal{O}(n)$ sweep.

Maintain difference array $D$ of size $n+1$, where $D[i]=A[i]-A[i-1]$ (with $A[-1]=0$). For each update tuple $(L,R,v)$:

1. $D[L]\leftarrow D[L]+v$ (initiates offset $+v$ from $L$ onward)
2. $D[R+1]\leftarrow D[R+1]-v$ (neutralizes offset $+v$ beyond $R$)

After applying all $Q$ operations, the cumulative prefix sum of $D$ yields the final array $A$:

export function applyRangeUpdates(
  n: number,
  updates: Array<[number, number, number]>
): number[] {
  const diff = new Array(n + 1).fill(0);

  for (const [L, R, val] of updates) {
    diff[L] += val;
    if (R + 1 < n) {
      diff[R + 1] -= val;
    }
  }

  const result = new Array(n);
  let running = 0;
  for (let i = 0; i < n; i++) {
    running += diff[i];
    result[i] = running;
  }

  return result;
}

The two-pointer technique coordinates two indices moving through a linear sequence, pruning search spaces and converting $\mathcal{O}(n^2)$ exhaustive comparisons into $\mathcal{O}(n)$ scans:

export function twoSumSorted(
  numbers: number[],
  target: number
): [number, number] | null {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const currentSum = numbers[left] + numbers[right];

    if (currentSum === target) {
      return [left, right];
    } else if (currentSum < target) {
      left++; // Increase sum by shifting to larger element
    } else {
      right--; // Decrease sum by shifting to smaller element
    }
  }

  return null;
}

A sliding window maintains a contiguous range $[L,R]$ across an array or string. By adding newly entering elements and evicting outgoing elements incrementally, it evaluates subarray properties in $\mathcal{O}(n)$ total time.

export function variableSlidingWindow(
  nums: number[],
  targetSum: number
): number {
  let left = 0;
  let currentSum = 0;
  let minLength = Infinity;

  for (let right = 0; right < nums.length; right++) {
    currentSum += nums[right]; // Expand window

    while (currentSum >= targetSum) {
      minLength = Math.min(minLength, right - left + 1);
      currentSum -= nums[left]; // Contract window
      left++;
    }
  }

  return minLength === Infinity ? 0 : minLength;
}

Floyd's Cycle-Finding Algorithm uses two pointers: slow advancing 1 step per cycle, and fast advancing 2 steps.

Let:

• $L$ = Distance from head to the cycle entry node.
• $C$ = Total perimeter length of the cycle.
• $d$ = Distance from cycle entry to the initial meeting point inside the cycle.

When the two pointers collide:

• Distance traversed by slow: $D_{\text{slow}}=L+d$
• Distance traversed by fast: $D_{\text{fast}}=L+d+k\cdot C$, where $k\ge 1$ represents completed loops.

Since fast travels at double the speed of slow:

The distance from head to the cycle entry node ($L$) is algebraically equivalent to $(k-1)$ full loops plus the distance from the collision point to the entry node ($C-d$).

Therefore, resetting slow to head while keeping fast at the meeting point and advancing both at 1 step per iteration guarantees they will collide at the exact cycle entry node.

interface ListNode {
  val: number;
  next: ListNode | null;
}

export function detectCycleEntry(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return null;

  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  // Phase 1: Detect cycle existence
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (slow !== fast) return null; // No cycle

  // Phase 2: Find cycle entry node
  slow = head;
  while (slow !== fast) {
    slow = slow!.next;
    fast = fast!.next;
  }

  return slow;
}

1. Halim, S., Halim, F., & Skiena, S. S. (2020). Competitive Programming 4: The Lower Bound of Programming Contests. CP4 Pte Ltd.
2. Laaksonen, A. (2020). Guide to Competitive Programming: Learning and Improving Algorithms Through Contests (2nd ed.). Springer.
3. Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.