The Sliding Window Mental Model

There are new variations of coding problems that pop up daily. Though practice does make perfect, you'll never be able to memorize or grind enough if the strategy is to only solve as many problems as possible. You will go crazy, unless you like that kinda thing. It's also not a good approach if you're looking to optimize your understanding of algorithms.

Just like certain types of data work best with certain data structures, most problems fit in specific categories. As I aim to grow in my career, I've seen my share of failures and success stories. One of my early failures was not having a concrete strategy for learning Data Structures and Algorithms. You(I) can be as consistent as you want, but if there isn't a plan in place to approach the problem and recognize the problem type in the wild, it would be a good idea to revisit your strategy.

Pattern 1: The Sliding Window

Variation 1: The fixed sized sliding window technique

1. Imagine you have 2 shapes

• SHAPE 1 - An array/list, linked list, etc...(a sequence of values)
• SHAPE 2 - A Window

2. Place the window over a portion/subset of this data structure/shape...

What are we doing in this type of problem?

• We're trying to optimize for something
• Ask yourself in reference to the problem, "Is this the best/worst that I can do with the data given?"

3. Slide the window...

• Continue to ask the same thing...keep tracking looking for the "best/worst" that you can do.

4. Return the best/worst/highest/lowest/minimum/maximum value

Variation 2: The Dynamically Resizable Sliding Window**

Dynamic in this case hints that the window can grow/shrink. The window slides still , but on the right side. Expands is also a good word to attach to it. On the left side, if we reach a specific set by the constraints of the questions, the window shrinks. This window continuously grows and shrinks, like a caterpillar almost, until the window reaches the end of the list/array.

Why do we want this technique in our problem solving arsenal?

• Sliding Window gives a more linear traversal and time, meaning faster than a typical brute force solution, which for this type of problem, could be Quadratic - O(N^2) or O(N *k)
• Optimized (Sliding Window) Time Complexity: O(N)
• Brute Force Time Complexity: Quadratic -O(N * k)
• N = # of Items In input List k = The window side input integer
• Brute Force isn't optimal and creates a lot of duplicate work until we hit the end of the list/array.
  • Example: Start at idx, iterate all combinations of the given criteria, and move to the next

The TLDR Strategy

Analyze each subarray/list of the input array as a sliding window of k(input value) elements. Slide the window/increment the left pointer by 1 as we move to the next subarray. To reuse the sum from the prior subarray, all you need to do is remove the ith element - 1 from the sum, and add in the newest value (end of the old subarray + 1) into the sum..

The Deeper Strategy

• Tracking Current Count/Sum with a variable
• Track Min/Max value of the data structure in a variable
• Open the window for the expected size if they give a K constraint
  • Example: Maximum Sum Subarray of Size K
• Each iteration, check if the current count/sum is the smallest/largest/optimal choice
• Replace the smallest/largest value with the new one IF it has been changed
• Slide (the widow) via incrementing left pointer until we make it to the end of the data structure
  • For loop automatically iterates after you've made it through one iteration of the entire data structure
  • While loop, you're incrementing the pointer by 1 to expand the window
• Return the optimal value

How do we find these problems in the wild?

• Type: Iterable items/data structure in sequential order?
  • Contiguous sequence of elements (grouped together one after the other)
  • Strings, Arrays, Linked Lists
• Type: Min/Max of Something, Longest, Shortest, Something contained within a DS
  • Maybe we need to calculate something

Common Sliding WIndow Problems

1. Fixed Length
   • Maximum Sum of A Contiguous Subarray of Size k
2. Dynamic Variant
   • Smallest Sum That is > or == To Some Value S
3. Dynamic Variant W/ Auxillary Data Structure(Dictionary)
   • Longest Substring w/ No More than K Distinct Characters
4. String Permutations

What are the commonalities/similarities/dead giveaways with these questions?

• Everything is grouped sequentially
  • subarray, substring, subsequence
• Longest/Smallest/Contains/Max/Min
• Example Wording
  • MAXIMUM Sum of A Contiguous SUBARRAY of SIZE K
  • SMALLEST Sum That is >= To Some Value S
  • Longest Substring w/ No More than K Distinct Characters

Coding Example

• Test Case: list = [10, 20, 30, 40, 11, 632], k = 4
• Find Average of Subarrays of Size K
• input: array/list of integers, an integer
• output: return an integer
• Clarify: You're given an array of numbers & an integer.Return the average of each subarray.

  def averageOfSubs(nums, k):
      currSum = 0
      listOfAverages = []
      l = 0 # Pointer 1
      for r in range(0, len(nums)): # Pointer 2
          currSum += nums[r] #The sum of the current window
          # If Condition isn't met until we have reached the window size 
          # that the question is requesting: (4)
          if r >= k - 1:
              print(nums[l:r + 1]) # Checking what values are included in the currSum calculation
              averageOfSubarray = currSum / k
              listOfAverages.append(averageOfSubarray)
              #We are ready to slide the window, so shift the 
              # left pointer out of the current sum and increment the pointer by 1
              currSum -= nums[l] 
              l += 1
      return listOfAverages

  print(averageOfSubs([10, 20, 30, 40, 11, 632], 4))