SimuVedaAlgorithms Lab Open in the lab

Patterns / Beginner

Sliding Window (Fixed Size) Visualizer

Keep one running sum. When the window slides right, add the value coming in and subtract the value going out.

Start the Sliding Window (Fixed Size) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Build the first window: add 2. Sum = 2. [2, 1, 5, 1, 3, 2, 9, 4, 1, 6]
  2. Build the first window: add 1. Sum = 3.
  3. Build the first window: add 5. Sum = 8.
  4. The first window [0..2] sums to 8. Best so far.
  5. Slide right: add 1, remove 2. Sum = 7.
  6. Slide right: add 3, remove 1. Sum = 9.
  7. 9 is the new best.
  8. Slide right: add 2, remove 5. Sum = 6.
  9. Slide right: add 9, remove 1. Sum = 14.
  10. 14 is the new best.
  11. Slide right: add 4, remove 3. Sum = 15.
  12. 15 is the new best.
  13. Slide right: add 1, remove 2. Sum = 14.
  14. Slide right: add 6, remove 9. Sum = 11.
  15. Done. The best window is [5..7] with sum 15.

Try it with your own input →

Sliding window (fixed size) in Java, Python, C++, C and JavaScript

int maxSumK(int[] a, int k) {
  int sum = 0;
  for (int i = 0; i < k; i++) sum += a[i];
  int best = sum;
  for (int r = k; r < a.length; r++) {
    sum += a[r] - a[r - k];
    best = Math.max(best, sum);
  }
  return best;
}
def max_sum_k(a, k):
    s = sum(a[:k])
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]
        best = max(best, s)
    return best
int maxSumK(const vector<int>& a, int k) {
  int sum = 0;
  for (int i = 0; i < k; i++) sum += a[i];
  int best = sum;
  for (int r = k; r < (int)a.size(); r++) {
    sum += a[r] - a[r - k];
    best = max(best, sum);
  }
  return best;
}
int maxSumK(int a[], int n, int k) {
  int sum = 0;
  for (int i = 0; i < k; i++) sum += a[i];
  int best = sum;
  for (int r = k; r < n; r++) {
    sum += a[r] - a[r - k];
    if (sum > best) best = sum;
  }
  return best;
}
function maxSumK(a, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += a[i];
  let best = sum;
  for (let r = k; r < a.length; r++) {
    sum += a[r] - a[r - k];
    best = Math.max(best, sum);
  }
  return best;
}

In an interview

LeetCode 643, Maximum Average Subarray I: find the k consecutive values with the largest sum.

Brute force re-adds k values for every window, O(n·k). The window makes it O(n). Say that comparison out loud in the interview.

More patterns