Sliding Window

This pattern focuses on traversing arrays (or linked lists). The idea is that we are looking for some (contiguous) sub-array with a particular property. We keep track of some indices that define our "window" (a sub-array) and iteratively "slide" the window in order to perform a search of sub-arrays. Sliding can mean shrinking or growing the window in any direction, or moving the window left or right any amount without changing the size.

A few things to remember about sliding the window

• We want to slide the window based on either simple local criteria or the same way every time

  • example of same way every time: just move the window left by one each time (without changing the window size)
  • example of based on simple criteria: grow the window leftward by one if the sum of the subarray is negative, or shrink the window leftward

• We often need to keep track of some property of the subarray (for example the sum, the average, the number of negative elements). To get the best runtime we should figure out how to update this property without recomputing it from the whole subarray. Instead, update the property using the elements that are being added or removed from the window.

Now consider the following problem:

Average of each size K-subarray

Given an array of integers, return in a new array the average of each subarray of length $k$. (Do this in order starting with the subarray that is the furthest left)

Example instance where the answer is [5, 7, 5, 8, 13]:

The naïve solution to this problem is to iterate through each subarray one at a time like so:

• slide the window rightward by one each time (not changing the size) until we reach the end
• add up all the elements of the subarray, and divide this number by $k$
• append this new average to the list we will return at the end

This solution yields a run-time of $O(n \times k)$ where $n$ is the length of our input array. This comes from searching through $O(n)$ sub-arrays and doing $O(k)$ work to compute each subarray average.

We can improve our runtime by not recalculating our average from scratch. Instead, keep track of the current sum of the subarray. Update the sum after sliding the window by adding the element on the right that moves into the window and subtracting the element on the left that moves out of the window. Each time, add this sum divided by $k$ to the list of subarray averages to be returned.

This solution yields a run-time of $O(n)$ where $n$ is the length of our input array. We still search through $O(n)$ sub-arrays, but now we do $O(1)$ work to compute each subarray average.

Problems for this Week

(easy) maximum-average-subarray-i

You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

(easy) minimum-difference-between-highest-and-lowest-of-k-scores

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k. Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized. Return the minimum possible difference.

(easy) find-the-k-beauty-of-a-number

The k-beauty of an integer num is defined as the number of substrings of num when it is read as a string that meet the following conditions:

• It has a length of k.
• It is a divisor of num.

Given integers num and k, return the k-beauty of num.

Note: Leading zeros are allowed, 0 is not a divisor of any value.

(A substring is a contiguous sequence of characters in a string)

Tip: I recommend turning the int into a string with built-in methods to begin (e.g. str(my_int) in python), this makes it easier to get the subsets of decimal digits. Modulo arithmetic is not the focus of this question. Then after turn the string into an int again to check if it is divisible by a number.

(easy) minimum-recolors-to-get-k-consecutive-black-blocks

You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the ith block. The characters 'W' and 'B' denote the colors white and black, respectively. You are also given an integer k, which is the desired number of consecutive black blocks. In one operation, you can recolor a white block such that it becomes a black block. Return the minimum number of operations needed such that there is at least one occurrence of k consecutive black blocks.

(medium) maximum-subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum

(medium) minimum-size-subarray-sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

(medium) fruit-into-baskets

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces. You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

(medium) longest-substring-without-repeating-characters

Given a string s, find the length of the longest substring without repeating characters.

(medium) longest-repeating-character-replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

(medium) max-consecutive-ones-iii

Given a binary array numsand an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k zeros.

(medium) permutation-in-string

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1's permutations is the substring of s2.

(medium) find-all-anagrams-in-a-string

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

(medium) minimum-window-substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique.

(medium) substring-with-concatenation-of-all-words

You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.