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 |
|
-
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 |
|
-
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 |
|
-
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; };