No history yet

Sliding Window Review

The Sliding Window Technique

When you need to analyze a contiguous part of a list or string, like a subarray or substring, a common first thought is to use nested loops. You might loop through every possible starting point, and for each start, loop through every possible end point. This works, but it's often inefficient.

The sliding window technique offers a more elegant solution. It transforms a problem that might seem to require a brute-force approach into something much faster. The core idea is to maintain a “window” over a portion of the data and slide that window across, updating your calculations as you go.

The sliding window pattern is a computational method aimed at reducing the use of nested loops in an algorithm.

Instead of re-evaluating each new subarray from scratch, you cleverly modify the previous window. As the window slides one step to the right, you add the new element that has entered the window and remove the element that has just left. This way, you only perform a couple of operations for each step, regardless of the window's size.

Fixed vs. Variable Windows

Sliding windows come in two main flavors: fixed-size and variable-size. The one you choose depends on the problem you're trying to solve.

A fixed-size window, as the name suggests, has a constant size. For example, if you need to find the maximum sum of any three consecutive numbers in an array, your window size is always 3. As you slide the window, it never grows or shrinks.

Problem: Find the maximum sum of any contiguous subarray of size k=3. Array: [1, 4, 2, 10, 23, 3, 1, 0, 20]

  1. First window: [1, 4, 2]. Sum = 7.
  2. Slide right: Remove 1, add 10. New window: [4, 2, 10]. New sum = 7 - 1 + 10 = 16.
  3. Slide right: Remove 4, add 23. New window: [2, 10, 23]. New sum = 16 - 4 + 23 = 35. ...and so on.

A variable-size window, on the other hand, expands and contracts based on certain conditions. The goal is often to find the longest or shortest subarray that satisfies a specific property. You might expand the window by moving its right edge, and when a condition is no longer met, you shrink it by moving its left edge.

Problem: Find the length of the longest substring with no more than k=2 distinct characters. String: "araaci"

  1. Window: "a". Distinct: 1. Length: 1.
  2. Expand -> "ar". Distinct: 2. Length: 2.
  3. Expand -> "ara". Distinct: 2. Length: 3.
  4. Expand -> "araa". Distinct: 2. Length: 4.
  5. Expand -> "araac". Distinct: 3 (a, r, c). This violates the condition (> k).
  6. Shrink from left: "raac". Distinct: 3. Still violates.
  7. Shrink from left: "aac". Distinct: 2. Condition met. Length: 3.
  8. Expand -> "aaci". Distinct: 3. Violates.
  9. Shrink from left: "aci". ...and so on. The max length found was 4.

The key is knowing when to expand and when to shrink the window to maintain the desired properties.

Quiz Questions 1/5

What is the primary advantage of the sliding window technique over a nested loop approach for problems involving contiguous subarrays or substrings?

Quiz Questions 2/5

You need to find the maximum sum of any contiguous subarray of size k=3 in the array [2, 1, 5, 1, 3, 2]. Which type of sliding window should you use?

This pattern is a powerful tool for optimizing solutions to a wide range of problems involving contiguous data.