PLAN-101 Career OS
Intermediate 40 Minutes

Sliding Window: From Quadratic Loops to a Linear Scan

Derive a fixed-window algorithm, state its invariant and test the boundary cases yourself.

Key Learning Objectives

  • Recognise fixed-size contiguous-subarray questions.
  • Explain the rolling-sum invariant.
  • Implement O(n) maximum-window sum.
  • Handle invalid window sizes explicitly.

Spot the repeated work

Suppose you need the largest sum of exactly k consecutive values. The direct solution adds each length-k slice independently. There are about n-k+1 candidate slices, each requiring k additions, for O(nk) time. Adjacent slices overlap in k-1 places: recomputing their shared values wastes work. Sliding window is useful when the answer for a new contiguous interval can be updated cheaply from the previous interval. This fixed-length case has a particularly simple invariant.

Maintain a rolling sum

First compute the sum of the first k elements. When moving the window right by one place, subtract the element that leaves and add the element that enters. After each update, currentSum equals the sum of precisely the active k items. That invariant proves the algorithm is correct. The code scans each element a constant number of times, so time is O(n) and additional working memory is O(1). Be careful with all-negative arrays: initialising best to zero would be wrong.

function maxWindowSum(values: number[], k: number): number | null {
  if (k < 1 || k > values.length) return null;
  let sum = 0;
  for (let i = 0; i < k; i++) sum += values[i];
  let best = sum;
  for (let right = k; right < values.length; right++) {
    sum += values[right] - values[right - k];
    best = Math.max(best, sum);
  }
  return best;
}

The previous window sum changes by one outgoing and one incoming element; null reports an invalid window size.

Understand when the technique does not transfer directly

A fixed-size rolling sum is not automatically a solution to variable-size questions. For a shortest subarray with sum at least a target, shrinking a window assumes that extending the right edge cannot make the sum smaller; that works for nonnegative inputs but breaks with negative values. For mixed-sign numbers, prefix sums and an appropriate data structure may be necessary. Always write down the invariant and input assumptions before adapting a memorised template.

Build It: Study streak analyser

Given daily study hours, report the highest total for any consecutive seven days.

Project Deliverables

  • A typed rolling-window function.
  • Tests for negative values, one-element arrays, k equal to n and invalid k.
  • A complexity explanation in two sentences.

Acceptance Criteria

  • Output matches brute-force results for at least five test arrays.
  • No nested full-window recomputation in the final algorithm.
  • Invalid k is handled without throwing.

Next Steps & Related Learning

This interactive lesson is part of the LeetCode Practice curriculum. Continue exploring or try another interactive lesson:

View Full LeetCode Practice → Arrays, Contiguous Memory & Hash Tables → JavaScript Asynchronous Execution & V8 Event Loop → Relational Database Architecture, B-Trees & Query Optimization → Semantic HTML, Accessible Forms & Document Structure → Python Functions, Dictionaries and Reliable Data Processing → SQL Joins, Missing Rows and Query Correctness → React State, Events and Derived UI → Designing a Task API: HTTP Methods, Errors and Validation → Responsive CSS Layout: Flexbox, Grid and Fluid Constraints → TypeScript Union Types and Runtime Narrowing → Docker Images, Containers and Reproducible Builds → Git Branches, Pull Requests and Conflict Resolution → Graph Traversal: BFS, DFS and Visited Sets → AWS IAM: Least Privilege and Secure Cloud Access → API Pagination, Error Contracts and Safe Retries →