Sliding Window Technique for Subarrays and Substrings

The Fixed-Size Sliding Window

The simplest form of the sliding window technique involves a window of a fixed size, let's say k, that "slides" across an array or string. A naive approach to problems like this might involve nested loops: an outer loop to set the starting point of a subarray and an inner loop to process the k elements within it. This typically results in an O(N×k) time complexity.

The sliding window technique optimizes this by reusing information from the previous window. Instead of re-calculating everything for each new window, we can get the new window's state by making a small, constant-time adjustment.

Let's consider a classic problem: Given an array of integers, find the maximum sum of any contiguous subarray of size k.

The key insight is that as the window slides one position to the right, only two things change: one element is removed from the left, and one new element is added to the right.

To truly grasp this optimization and its impact on complexity, let's watch a detailed whiteboard explanation.

Now that you understand the logic, let's look at a C++ implementation.

This fixed-size pattern is a great starting point, but the real power of sliding windows comes from its dynamic variant.

The Variable-Size Sliding Window

In many problems, the size of the subarray or substring we're looking for is not given. Instead, we need to find the longest or shortest one that satisfies a certain property. This is where the variable-size sliding window comes in.

This pattern also uses two pointers, typically start and end (or left and right), which define the current window. The logic works as follows:

1. Expand: We always move the end pointer to the right, expanding the window and including new elements.
2. Check Condition: After each expansion, we check if the current window satisfies the problem's condition.
3. Shrink: If the condition is violated, we move the start pointer to the right, shrinking the window from the left until the condition is met again.

This expansion and contraction allow the window to dynamically change its size to find the optimal solution. The following video provides a superb introduction to this template.

Let's solidify this with a concrete example. Consider the problem: Given an array of non-negative integers, find the smallest subarray with a sum greater than or equal to a given value x.

The logic is:

• Expand the window by moving end to the right, adding arr[end] to current_sum.
• While current_sum >= x:
  • The condition is met. This window is a potential answer. Update the minimum length found so far.
  • Now, try to find an even smaller window. Shrink the window by subtracting arr[start] from current_sum and incrementing start.
• Repeat until end reaches the end of the array.

This approach ensures that for every possible end position, we find the shortest valid subarray ending at that position. The article below provides a clear C++ implementation of this pattern.

One of the most powerful aspects of this technique is its time complexity. It might seem like the nested while loops would lead to an O(N²) complexity, but it's actually O(N). The freeCodeCamp video explains why this is the case. Although it discusses a slightly different problem, the complexity analysis is universal for this pattern.

Application: A Classic Interview Problem

Now let's apply this to a classic coding interview question: Longest Substring Without Repeating Characters. Given a string, find the length of the longest substring that does not contain repeating characters.

This is a perfect fit for a variable-size sliding window:

• The "window" is the current substring we are examining.
• The condition is "the substring must have unique characters."
• We need a way to efficiently track the characters within the current window to check for duplicates. An unordered_set or unordered_map is ideal for this.

The logic proceeds as follows:

1. Initialize left = 0, max_length = 0, and an empty character set/map.
2. Iterate with a right pointer from 0 to n-1 (this expands the window).
3. Inside the loop, check if s[right] is already in our character set.
4. While s[right] is a duplicate:
   • The uniqueness condition is violated.
   • Shrink the window from the left: remove s[left] from the set and increment left.
5. Once the loop finishes, s[right] is no longer a duplicate in the window. Add s[right] to the set.
6. The current window [left, right] is valid. Update max_length = max(max_length, right - left + 1).
7. After the main loop finishes, return max_length.

The following resource provides a concise C++ implementation of this logic.

Conclusion

In this lesson, we added the sliding window technique to your algorithmic toolkit. It's an essential pattern for efficiently solving a wide range of problems on contiguous subarrays and substrings, making it a favorite in technical interviews.

Key Takeaways:

• Core Idea: The sliding window technique maintains a "window" over a portion of data and slides it across the sequence, updating its state efficiently at each step.
• Fixed-Size Window: Used when the problem specifies a fixed window size k. The key is the O(1) update: subtract the outgoing element and add the incoming element.
• Variable-Size Window: A more general pattern where the window expands (by moving the end pointer) and shrinks (by moving the start pointer) based on a condition. This is used for "longest/shortest subarray/substring" problems.
• Time Complexity: The main benefit of this technique is its efficiency. Both fixed and variable-size patterns typically run in O(N) time because each element is visited by the start and end pointers at most once.
• Data Structures: Auxiliary data structures like hash maps (unordered_map) or sets (unordered_set) are often used to maintain the state of the window, such as character counts or uniqueness checks.

In our next lesson, we'll tackle another common array problem: traversing a 2D matrix in a spiral pattern. This will complete our first module on core algorithmic concepts and array manipulations.