Sliding Window Algorithmic Mental Model

The term "mental model" is quite significant. The concept I aim to explain is that we are working on creating a method to recognize a wide range of issues that we might encounter in an application or various settings. These could involve different kinds of problems, questions, or algorithms, not the exact questions themselves. Our goal isn't to memorize specific algorithms or solutions. Instead, we aim to internalize the mental model, or at least grasp it from a more abstract perspective. This approach allows us to use our understanding across a diverse array of problems.

What is the Sliding Window Algorithm?

The sliding window technique is a highly useful concept to have in our toolbox for solving a wide range of problems.

At its core, the sliding window approach involves envisioning two shapes. The first shape resembles a rectangle, which can stand for various data structures like an array or a linked list. This rectangle holds sequences of data that are next to each other. For instance, picture an array of letters or numbers. With this in mind, we place a "window" over a part of this array. Then, we pose a question related to optimizing something, and we ponder whether our current setup is the best solution. We note down the result and then shift the window. As we move the window, we assess if the current subset is an improvement or not. When we identify a point where the performance is the best so far, surpassing previous records, we store that value as our maximum. We keep moving the window, taking action based on whether the current scenario is better or not until we reach the end of the data structure, which marks the stopping point. At this juncture, we hopefully have stored the optimized value in an extra data structure or variable. We then return this value from the function we're working on. This technique is specifically referred to as the fixed-sized sliding window technique.

Another approach to this is called the dynamically resizing sliding window technique. This approach works a bit differently. Instead of having a fixed size, the window grows and shrinks as needed. It's like a caterpillar moving along a tree. It grows and shrinks alternatively. When certain conditions are met, the window on the left side shrinks. The process is similar to how we grow the window, but with this approach, there's more flexibility in the window's size. Eventually, we continue growing until we reach the end of the array, which serves as our stopping point.

It's not a matter of choosing between the two techniques, but rather deciding which one to use based on the specific problem at hand. Different questions call for different solutions. The dynamically resizing approach might be suitable for one type of question, while the fixed-sized approach works better for another. The nature of the problem usually guides us in choosing the appropriate technique.

What are the benefits of using the Sliding Window Algorithm?

Now, let's consider why we'd want to employ this technique and what the alternatives are. A less efficient way that's often used is what's called the brute force approach. Imagine having an array, and the idea is to start at an index and go through all possible combinations that meet a given criteria. This process involves iterating over the array multiple times, with each iteration considering a different starting point and a different range of elements.

However, this brute force approach leads to duplicating a lot of work. As we iterate through the array, we end up revisiting values we've already processed before. This results in unnecessary iterations, making the overall process less optimal. This approach has a time complexity of O(N*K), where N is the array's length and K represents the number of iterations. Another way to describe this complexity is as N squared.

The sliding window technique offers a solution to this inefficiency. It optimizes the process to a linear time algorithm. With the sliding window approach, we eliminate the need for redundant iterations and double-checking values. Instead of duplicating work, we move the window along the array, performing calculations by adding and subtracting values. This way, we maintain a linear traversal. We never halt the traversal, and we avoid reevaluating values we've already processed. This is the key advantage of the sliding window technique over the brute force approach.

How to spot a Sliding Window Algorithm problem?

The first thing to notice is that these kinds of problems are best suited for items that can be worked with in intervals. This means we go through them one by one, step by step. This becomes clear because what we're focused on is the uninterrupted sequence of elements. This refers to items that are grouped together right next to each other. They might be in the middle of an array or somewhere else, but they form a subset or a smaller group that comes one after another. This is usually what we're aiming to find.

And of course, we're aware that these problems work well with various data types. We're talking about strings, arrays of numbers or characters, and even linked lists. Linked lists might not be stored in a continuous manner in memory, but we can still go through them in a continuous way, just like we would with arrays or strings.

• Items we can go through one by one.Continuous sequence of elements.Examples include strings, arrays, linked lists, and so on.

Now, when it comes to the way questions will be presented and the kinds of algorithms we'll encounter, it's essentially a range of various scenarios. However, the focus is on specific criteria that we're interested in. These criteria often involve tasks like finding the smallest or largest element, identifying the longest or shortest sequence, and determining if something is present within a given string or array. In essence, we're aiming to locate minimums, maximums, lengths, or if specific elements are contained. This approach is also valuable for computations like running averages.

The key concept is that we'll likely need to calculate and keep track of certain values. These values will typically be related to the minimum, maximum, longest, shortest, or presence of elements. What's important to remember is that everything will be in a continuous, sequential manner. These are the types of questions or queries we need to be mindful of when working with data structures.

• Minimum, Maximum, Longest, Shortest, Contained.There might be a need to calculate something.

Certainly, let's delve into how to identify sliding window problems and quickly recognize when they are suitable for the sliding window technique:

1. Fixed Length

• Maximum Sum of Subarray for Size K.

In this scenario, we are dealing with a constant length of three. Our goal is to maximize the sum – specifically, the maximum sum of a subarray with a size of K. This situation aligns well with the sliding window technique applied to fixed lengths.

Input Array: [a, b, c, d, e, f, g, h, i, j]

Window of Size K = 3:
[a, b, c] => Sum = a + b + c

Sliding Window Approach:
  [a, b, c] d, e, f, g, h, i, j
   a, [b, c, d] e, f, g, h, i, j
   a, b, [c, d, e] f, g, h, i, j
   ...

Maximum Sum of Subarray = Max(a + b + c, b + c + d, c + d + e, ...)        

1. Dynamic Variant

• Smallest Sum Greater Than or Equal to a Value S.

Another situation involves a dynamic variant. Here, the window isn't necessarily a fixed size like K; it can expand and contract, similar to a caterpillar's motion. In this case, we might be aiming to locate the smallest sum that's equal to or greater than a specific value. Let's consider it as finding the tiniest sum that meets the condition of being greater than or equal to a given value, S. To illustrate, picture an array where we're searching for the smallest sum among windows of various sizes. However, the size of the window we're examining must be equal to or exceed the value S. Essentially, we're trying to pinpoint a window that comes as close as possible to the value S.

Input Array: [p, q, r, s, t, u, v, w, x, y, z]

Window Size >= S:
[p, q, r, s, t, u, v] w, x, y, z

Moving Window to Find the Smallest Sum >= S:
[p, q, r, s] t, u, v, w, x, y, z
p, [q, r, s, t] u, v, w, x, y, z
...

Smallest Sum >= S is the Answer.        

1. Dynamic Variant with Auxiliary Data Structure

• Longest Substring with at Most K Distinct Characters
• String Permutations

This scenario shares similarities with the dynamic variant, but it often introduces an auxiliary data structure. An auxiliary data structure refers to using additional tools like a hash map, a hash set, or an extra array beyond what's typically used like a regular variable or boolean flag. This dynamic variant, enhanced by an auxiliary data structure, is where these problems become particularly intriguing. This approach brings a unique dimension to the types of problems we encounter.

For instance, a problem involving an auxiliary data structure might revolve around finding the longest substring with no more than K distinct characters. Here, the task involves examining sequential data, such as substrings, while adhering to the constraint of having K distinct characters or less. Given that we're dealing with distinct characters, employing a hash map or hash set becomes important. These structures can keep track of character occurrences and their frequency in the input string.

Another example could pertain to string permutations. In this case, we can envision having a larger input string and a secondary subset or another string. The question might be whether the second string is present as a permutation of the main string.

Input String: "abcaabcde"

Using Sliding Window and Auxiliary Data Structure:
[a, b, c, a] a, b, c, d, e
    [a, b, c, a, a] b, c, d, e
    a, [b, c, a, a, b] c, d, e
    ...

Longest Substring with at Most K Distinct Characters = "bcaabc"        

What matters even more than this is identifying the shared aspects— the commonalities or similarities among all these questions. The goal is to create an abstract algorithmic mental model that can be applied to solve each of these questions. The first key commonality is that everything is organized in a sequence. Keywords like "substring" and "subarray" clearly indicate sequential data groupings. These are telltale signs that point to the sliding-window technique.

Another aspect to focus on is that each question specifies some form of sequential criterion. This pertains to concepts we discussed earlier such as "longest," "smallest," and "contains." For example, in the case of permutations, the focus is on whether a certain set of characters exists. Moreover, whether we're dealing with maximizing or minimizing something, these aspects are unmistakable indicators and shared features within this subset of questions. They actually span a wide range of sliding-window problems.

Therefore, what's crucial to remember is to pinpoint one or two criterion points and base the window around them. For instance, consider a scenario where we want to maximize the sum while keeping the window size fixed at K. Similarly, we might be aiming to minimize the sum while maintaining criteria of being greater than or equal to S. In another instance, the aim could be to maximize the length of a substring with no more than K distinct characters. Lastly, in cases involving string permutations, we're merely trying to ascertain if a given input string exists within another string.

These recurring themes constitute the foundation of the sliding-window technique.

Examples of Sliding Window Algorithm problems

• Sliding Window Algorithm: Fixed Size

Let's consider an example problem: finding the maximum sum of a subarray of a given size K.

package main

import (
  "fmt"
)

func maxSumSubarray(arr []int, K int) int {
  maxSum, currentSum := 0, 0
  for i := 0; i < K; i++ {
    maxSum += arr[i]
  }
  currentSum = maxSum
  for i := K; i < len(arr); i++ {
    currentSum = currentSum - arr[i-K] + arr[i]
    maxSum = max(maxSum, currentSum)
  }
  return maxSum
}

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

func main() {
  arr := []int{2, 1, 5, 1, 3, 2, 9, 7}
  K := 3
  fmt.Println("Maximum sum:", maxSumSubarray(arr, K))
}        

• Dynamic-Size Sliding Window: Min Subarray Length

Let's consider an example problem: finding the minimum length of a subarray with a sum greater than or equal to a given value S.

package main

import (
  "fmt"
  "math"
)

func minSubarrayLength(arr []int, S int) int {
  minLength, windowStart, windowSum := math.MaxInt64, 0, 0
  for windowEnd := 0; windowEnd < len(arr); windowEnd++ {
    windowSum += arr[windowEnd]
    for windowSum >= S {
      minLength = min(minLength, windowEnd-windowStart+1)
      windowSum -= arr[windowStart]
      windowStart++
    }
  }
  if minLength == math.MaxInt64 {
    return 0
  }
  return minLength
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

func main() {
  arr := []int{2, 1, 5, 2, 3, 2}
  S := 7
  fmt.Println("Minimum length:", minSubarrayLength(arr, S))
}        

Conclusion

In conclusion, the sliding window technique is a versatile strategy for optimizing various problems. By using a shifting window to assess data subsets, we can identify the most efficient solution within a data structure like an array or linked list. This approach is particularly effective for performance enhancement tasks. Through careful traversal, we locate the optimal point and store its value for later use. This fixed-sized sliding window method offers an elegant and efficient way to achieve optimization in diverse scenarios.

Thank you ?? for taking the time ? to read this blog post ??. I hope you found the information ?? helpful and informative ??. If you have any questions ? or comments ??, please feel free to leave them below ??. Your feedback ?? is always appreciated.

Portfolio GitHub LinkedIn Twitter