The Sliding Window

The code below is representative of a “semi-involved” Sliding Window. Also, it’s worth reminding that the whole purpose of “memorizing code” is less about “rote memorization” and more about having “rapid access” to a useful pattern. With that in mind the “memory hack” for the sample below is not all encompassing but covers the key elements.

Sliding Window background: what is it, and why? A sliding window is great for situations where you need to identify some “sub set” or “sub array”. Sliding Window problems will frequently be of the fixed or dynamic variety, although I suppose other types may exist.

A fixed example would be comparing a subarray of X items, where X is always the same number. The sliding window has to add them up, or average them, or whatever, AND the sliding window (to save on memory from the Big O perspective) basically drops the first value (left side of the window) and replaces it with the next one up, as the right most value (the right side of the window) “slides up”.

A dynamic example is similar except the size of the window will also change. In other words, “find the longest or largest sub array with no repeating integers, words or otherwise”. The example below is of the dynamic variety. Though more difficult to memorize, it covers both varieties of the sliding window.

A more difficult/rarer use case of the sliding window might be where you have two separate sliding window running at the same time.

function longest_subarray_with_k_unique_words(arr, k) {
  let windowBegin = 0;
  let maxLength = 0;
  let wordFrequency = {};

  for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    const rightSideWord = arr[windowEnd];

    if (!(rightSideWord in wordFrequency)) {wordFrequency[rightSideWord] = 0}
    wordFrequency[rightSideWord] += 1

    while (Object.keys(wordFrequency).length > k) {
      const leftSideWord = arr[windowBegin];
      wordFrequency[leftSideWord] -= 1;
      if (wordFrequency[leftSideWord] === 0) {
        delete wordFrequency[leftSideWord];
      }
      windowBegin += 1; 
    }
    maxLength = Math.max(maxLength, windowEnd - windowBegin + 1);
  }

  return maxLength;
}

console.log(`longest subarray that contains K words is: ${longest_subarray_with_k_unique_words(["rat","house","house","cat","cat","rat"], 2)}`);

It can be thought of as the following for recall:

A Forex Trader watches sliding window washers snacking on hash browns delivered by a retired Turtle Bouncer, as Wile E Coyote eats the keys a Pawn Broker dropped into a deli sandwich and a Fat Math Teacher measures the maxLength of a window against its end minus its beginning. ADDITIONAL MEMORY TIPS: imagine the forex trader in an office building, looking out on to a scaffold where all the madness ensues.

The absurdity above covers:
–sliding window
-an extended for loop
-initialization of window start and window end
-a hash/object
-a single line if statement
-a while loop
-use of Object.keys
-use of delete on a hash/object
-Math.max(maxLength, windowEnd – windowStart) … or similar

Granted, the absurdity does not cover every initialization, nor how to go about adding or subtracting to make the window enlarge or shrink, but the expectation is that you will have enough to recreate what you need based on your ability to code.

Glossary of Code Personified

Return to the Pattern Directory