SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Sliding Window (Variable Size) Visualizer

Grow the window with r until it meets the condition, then shrink it with l as far as it stays valid.

Start the Sliding Window (Variable 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. Find the shortest window with sum ≥ 7. r grows it, l shrinks it. [2, 3, 1, 2, 4, 3]
  2. Expand: add 2. Sum = 2.
  3. Expand: add 3. Sum = 5.
  4. Expand: add 1. Sum = 6.
  5. Expand: add 2. Sum = 8.
  6. Sum 8 ≥ 7. Length 4 is the new shortest.
  7. Shrink: remove 2 from the left. Sum = 6.
  8. Expand: add 4. Sum = 10.
  9. Sum 10 ≥ 7, length 4. Not shorter than 4.
  10. Shrink: remove 3 from the left. Sum = 7.
  11. Sum 7 ≥ 7. Length 3 is the new shortest.
  12. Shrink: remove 1 from the left. Sum = 6.
  13. Expand: add 3. Sum = 9.
  14. Sum 9 ≥ 7, length 3. Not shorter than 3.
  15. Shrink: remove 2 from the left. Sum = 7.
  16. Sum 7 ≥ 7. Length 2 is the new shortest.
  17. Shrink: remove 4 from the left. Sum = 3.
  18. Done. The shortest window is [4..5], length 2.

Try it with your own input →

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

int minSubArrayLen(int target, int[] a) {
  int l = 0, sum = 0, best = MAX;
  for (int r = 0; r < a.length; r++) {
    sum += a[r];
    while (sum >= target) {
      best = Math.min(best, r - l + 1);
      sum -= a[l++];
    }
  }
  return best == MAX ? 0 : best;
}
def min_sub_array_len(target, a):
    l, s, best = 0, 0, float('inf')
    for r in range(len(a)):
        s += a[r]
        while s >= target:
            best = min(best, r - l + 1)
            s -= a[l]; l += 1
    return 0 if best == float('inf') else best
int minSubArrayLen(int target, const vector<int>& a) {
  int l = 0, sum = 0, best = INT_MAX;
  for (int r = 0; r < (int)a.size(); r++) {
    sum += a[r];
    while (sum >= target) {
      best = min(best, r - l + 1);
      sum -= a[l++];
    }
  }
  return best == INT_MAX ? 0 : best;
}
#include <limits.h>

int minSubArrayLen(int target, int a[], int n) {
  int l = 0, sum = 0, best = INT_MAX;
  for (int r = 0; r < n; r++) {
    sum += a[r];
    while (sum >= target) {
      if (r - l + 1 < best) best = r - l + 1;
      sum -= a[l++];
    }
  }
  return best == INT_MAX ? 0 : best;
}
function minSubArrayLen(target, a) {
  let l = 0, sum = 0, best = Infinity;
  for (let r = 0; r < a.length; r++) {
    sum += a[r];
    while (sum >= target) {
      best = Math.min(best, r - l + 1);
      sum -= a[l++];
    }
  }
  return best === Infinity ? 0 : best;
}

In an interview

LeetCode 209, Minimum Size Subarray Sum: the shortest subarray with sum at least the target.

Each index enters and leaves the window once, so the nested while loop is still O(n) overall. Interviewers often ask why.

More patterns