Skip to content

Sliding Window Pattern

This pattern involves creating a window which can either be an array or number from one position to another.

Depending on a certain condition, the window either increases or closes (and a new window is created).

Very useful for keeping track of a subset of data in an array/string etc.

maxSubarraySum(arr, n)

Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.

1
2
3
4
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2); // 10
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4); // 17
maxSubarraySum([4, 2, 1, 6], 1); // 6
maxSubarraySum([], 4); // null

  • Solution 1 (naive):

    • Time: $O(n^2)$
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    const maxSubarraySum = (arr, n) => {
  if (n > arr.length) return null;

  let ret = -Infinity;

  for (let i = 0; i < arr.length - n + 1; i++) {
    let temp = 0;
    for (let j = 0; j < n; j++)
      temp += arr[i + j];

    ret = Math.max(ret, temp);
  }

  return ret;
};

  • Solution 2 (refactor):

    • Time: $O(n)$
    • Space: $O(1)$
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    const maxSubarraySum = (arr, n) => {
  if (arr.length < n) return null;

  let ret = 0;
  let temp = 0;

  for (let i = 0; i < n; i++) ret += arr[i];

  temp = ret;
  for (let i = n; i < arr.length; i++) {
    temp = temp - arr[i - n] + arr[i];
    ret = Math.max(ret, temp);
  }

  return ret;
};

minSubArrayLen(arr, num)

Write a function called minSubArrayLen which accepts two parameters - an array of positive integers and a positive integer.

This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn’t one, return 0 instead.

1
2
3
minSubArrayLen([2, 3, 1, 2, 4, 3], 7); // 2 -> because [4, 3] is the smallest subarray
minSubArrayLen([2, 1, 6, 5, 4], 9); // 2 -> because [5, 4] is the smallest subarray
minSubArrayLen([3, 1, 62, 19], 52); // 1 -> because [62] is greater than 52

  • Solution

    • Time: $O(n)$
    • Space: $O(1)$
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    const minSubArrayLen = (arr, num) => {
  let i = 0; // start
  let j = 0; // end
  let sum = 0;
  let ret = Infinity;

  while (i < arr.length) {
    if (sum < num && j < arr.length) {
      sum += arr[j];
      j++;
    } else if (sum >= num) {
      ret = Math.min(ret, j - i);
      sum -= arr[i];
      i++;
    } else {
      break;
    }
  }

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

findLongestSubstring(str)

Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.

1
2
3
4
findLongestSubstring(''); // 0
findLongestSubstring('rithmschool'); // 7
findLongestSubstring('thecatinthehat'); // 7
findLongestSubstring('bbbbbb'); // 1

  • Solution:

    • Time: $O(n)$
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    const findLongestSubstring = str => {
  let ret = 0;
  let seen = {};
  let i = 0;

  for (let j = 0; j < str.length; j++) {
    let char = str[j];
    if (seen[char]) i = Math.max(i, seen[char]);
    ret = Math.max(ret, j - i + 1);
    seen[char] = j + 1;
  }

  return ret;
};