Sliding Window Algorithm

Here are some of my notes while I go over the sliding window algorithm.

Problem: Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’.

My Answer:

const max_sub_array_of_size_k = (k, arr) => {
  let end = 0;
  let start = 0;
  let max = 0;

  while(end < arr.length - 1) {
    if(end < k) {
      max += arr[end];
    } else {
      const current = max + arr[start] - arr[end];

      if(current > max){
        max = current;
      } else {
        start++;
      }
    }

    end++;
  }

  return max;
}

Types of alternatives:

  • if no conditional then can use hash map with counter to keep track of conditional to move sliding window
  • while loop expands the window, conditional for inner loop shrinks the window
  • may not need to go to end of array if not enough values left on end of window for conditional

Problem: Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.

We can remove the end pointer by merging it into the main loop:

const smallest_subarray_with_given_sum = (s, arr) => {
  let start = 0;
  let sum = 0;
  let length = Infinity;

  for (let end = 0; end < arr.length; end++) {
    const endNum = arr[end];
    sum += endNum;

    while (sum >= s) {
      sum -= arr[start];
      length = Math.min(length, end - start + 1);
      start++;
    }
  }

  return length === Infinity ? 0 : length;
}

removing the end from the first example will be:

const max_sub_array_of_size_k = (k, arr) => {
  let start = 0;
  let max = 0;

  for (let end = 0; end < arr.length; end++) {

    if(end < k) {
      max += arr[end];
      
    } else {
      const current = max + arr[start] - arr[end];

      if(current > max){
        max = current;
      } else {
        start++;
      }
    }
  }

  return max;
}

Sliding Window Template

function sliding_window(nums):
  Iterate over elements in our input
    Expand the window

    Meet the condition to stop expansion
      Process the current window   
      Contract the window

Try to rephrase the question. For example, “Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.” can be rephrased as “Find the largest window that has at most one 0 in it”. In this example (rephrase again), we need to “expand the window until we have seen two 0’s”. We can keep track of how many zeros we’ve collected with a counter variable.

Again in example, we iterate over array (expanding right side window – begin var or loop), count how many zeros we run across. Once we reach 2, we stop the expansion. Process current window then contract the window with end var. Processing means seeing if what we have now is the new max consecutive 1s in array. we know there’s a condition here that meets requirements because that’s why we stopped.

function sliding_window(nums) {
  let left = 0;
  let right = 0;

  let count = 0;
  let max = 0;

  while (right < nums.length) {
    if(nums[right] == 0) count += 1

    while(count == 2) {
      max = Math.max(max, right - left)

      if(nums[left] == 0) count -= 1
      left++;
    }

    right++;
  }

  if(count < 2) max = Math.max(max, right - left)
  return max
}

Leave a Reply

Your email address will not be published. Required fields are marked *