Distilled • LeetCode • Sliding/Rolling/Moving Window
 Pattern: Sliding/Rolling/Moving Window
 Introduction
 Approach: Brute Force
 Complexity
 Approach: Sliding Window
 [1/Easy] Two Sum
 [Easy] Maximum Sum Subarray of Size K
 [3/Medium] Longest Substring Without Repeating Characters
 [15/Medium] 3Sum
 [18/Medium] 4Sum
 [76/Hard] Minimum Window Substring
 [167/Medium] Two Sum II  Input Array Is Sorted
 [198/Medium] House Robber
 [1291/Medium] Sequential Digits
Pattern: Sliding/Rolling/Moving Window
Introduction

In many problems dealing with an array (or a LinkedList), we are asked to find or calculate something among all the subarrays (or sublists) of a given size. For example, take a look at this problem:

Given an array, find the average of all subarrays of ‘K’ contiguous elements in it.

Let’s understand this problem with a real input:
Array: [1, 3, 2, 6, 1, 4, 1, 8, 2], K=5
 Here, we are asked to find the average of all subarrays of ‘5’ contiguous elements in the given array. Let’s solve this:
1. For the first 5 numbers (subarray from index 04), the average is: (1+3+2+61)/5 => 2.2(1+3+2+6−1)/5=>2.2
1. The average of next 5 numbers (subarray from index 15) is: (3+2+61+4)/5 => 2.8(3+2+6−1+4)/5=>2.8
1. For the next 5 numbers (subarray from index 26), the average is: (2+61+4+1)/5 => 2.4(2+6−1+4+1)/5=>2.4
...
 Here is the final output containing the averages of all subarrays of size 5:
Output: [2.2, 2.8, 2.4, 3.6, 2.8]
Approach: Brute Force
 A bruteforce algorithm will calculate the sum of every 5element subarray of the given array and divide the sum by ‘5’ to find the average. This is what the algorithm will look like:
def find_averages_of_subarrays(K, arr):
result = []
for i in range(len(arr)K+1):
# find sum of next 'K' elements
_sum = 0.0
for j in range(i, i+K):
_sum += arr[j]
result.append(_sum/K) # calculate average
return result
def main():
result = find_averages_of_subarrays(5, [1, 3, 2, 6, 1, 4, 1, 8, 2])
print("Averages of subarrays of size K: " + str(result))
main()
Complexity
 Time:

Since for every element of the input array, we are calculating the sum of its next \(K\) elements, the time complexity of the above algorithm will be \(O(N*K)\) where \(N\) is the number of elements in the input array.

Can we find a better solution? Do you see any inefficiency in the above approach?

The inefficiency is that for any two consecutive subarrays of size ‘5’, the overlapping part (which will contain four elements) will be evaluated twice. For example, take the abovementioned input:

As you can see, there are four overlapping elements between the subarray (indexed from 04) and the subarray (indexed from 15). Can we somehow reuse the
sum
we have calculated for the overlapping elements? 
The efficient way to solve this problem would be to visualize each subarray as a rolling/sliding window of ‘5’ elements. This means that we will slide the window by one element when we move on to the next subarray. To reuse the
sum
from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window. This will save us from going through the whole subarray to find thesum
and, as a result, the algorithm complexity will reduce to \(O(N)\).

Approach: Sliding Window
def find_averages_of_subarrays(K, arr):
result = []
windowSum, windowStart = 0.0, 0
for windowEnd in range(len(arr)):
windowSum += arr[windowEnd] # add the next element
# slide the window, we don't need to slide if we've not hit the required window size of 'k'
if windowEnd >= K  1:
print(windowEnd, K)
result.append(windowSum / K) # calculate the average
windowSum = arr[windowStart] # subtract the element going out
windowStart += 1 # slide the window ahead
return result
def main():
result = find_averages_of_subarrays(5, [1, 3, 2, 6, 1, 4, 1, 8, 2])
print("Averages of subarrays of size K: " + str(result))
main()
 Note that in some problems, the size of the sliding window is not fixed. We have to expand or shrink the window based on the problem constraints.
[1/Easy] Two Sum
 In general, sum problems can be categorized into two categories:
 There is an array and you add some numbers to get to (or close to) a target, or
 You need to return indices of numbers that sum up to a (or close to) a target value.
 Note that when the problem is looking for a indices, sorting the array is probably NOT a good idea.
Problem
 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
 You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.
 Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
 Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
 Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
 Constraints:
2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109
 Only one valid answer exists.
 See problem on LeetCode.
Solution: Sliding Window
 This is the second type of the problems where we’re looking for indices, so sorting is not necessary. What you’d want to do is to go over the array, and try to find two integers that sum up to a target value. Most of the times, in such a problem, using dictionary (hastable) helps. You try to keep track of you’ve observations in a dictionary and use it once you get to the results.
 In this problem, you initialize a dictionary (
seen
). This dictionary will keep track of numbers (askey
) and indices (asvalue
).  So, you go over your array (line #1) using
enumerate
that gives you both index and value of elements in array.  As an example, let’s do
nums = [2,3,1]
andtarget = 3
. Let’s say you’re at indexi = 0
andvalue = 2
, ok? you need to findvalue = 1
to finish the problem, meaning,target  2 = 1
. 1 here is the remaining. Since remaining + value = target, you’re done once you found it.  So when going through the array, you calculate the remaining and check to see whether remaining is in the seen dictionary (line #3). If it is, you’re done!
 The current number and the remaining from
seen
would give you the output (line #4).  Otherwise, you add your current number to the dictionary (line #5) since it’s going to be a remaining for (probably) a number you’ll see in the future assuming that there is at least one instance of answer.
class Solution:
def twoSum(self, nums: List[int], target: int) > List[int]:
seen = {}
for i, value in enumerate(nums): #1
remaining = target  nums[i] #2
if remaining in seen: #3
return [i, seen[remaining]] #4
else:
seen[value] = i #5
Complexity
 Time: \(O(n)\)
 Space: \(O(1)\)
[Easy] Maximum Sum Subarray of Size K
Problem

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

Example 1:
Input: [2, 1, 5, 1, 3, 2], k=3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].
 Example 2:
Input: [2, 3, 4, 1, 5], k=2
Output: 7
Explanation: Subarray with maximum sum is [3, 4].
Solution: Brute force
 A basic brute force solution will be to calculate the sum of all ‘k’ sized subarrays of the given array to find the subarray with the highest sum. We can start from every index of the given array and add the next ‘k’ elements to find the subarray’s sum. Following is the visual representation of this algorithm for example 1:
def max_sub_array_of_size_k(k, arr):
max_sum = 0
window_sum = 0
for i in range(len(arr)  k + 1):
window_sum = 0
for j in range(i, i+k):
window_sum += arr[j]
max_sum = max(max_sum, window_sum)
return max_sum
def main():
print("Maximum sum of a subarray of size K: " + str(max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2])))
print("Maximum sum of a subarray of size K: " + str(max_sub_array_of_size_k(2, [2, 3, 4, 1, 5])))
main()
Complexity
 Time: \(O(N*K)\), where ‘N’ is the total number of elements in the given array.
Solution: Sliding window
 If you observe closely, you will realize that to calculate the sum of a contiguous subarray, we can utilize the sum of the previous subarray. For this, consider each subarray as a Sliding Window of size ‘k.’ To calculate the sum of the next subarray, we need to slide the window ahead by one element. So to slide the window forward and calculate the sum of the new position of the sliding window, we need to do two things:
 Subtract the element going out of the sliding window, i.e., subtract the first element of the window.
 Add the new element getting included in the sliding window, i.e., the element coming right after the end of the window.
 This approach will save us from recalculating the sum of the overlapping part of the sliding window. Here is what our algorithm will look like:
def max_sub_array_of_size_k(k, arr):
max_sum , window_sum = 0, 0
window_start = 0
for window_end in range(len(arr)):
window_sum += arr[window_end] # add the next element
# slide the window, we don't need to slide if we've not hit the required window size of 'k'
if window_end >= k1:
max_sum = max(max_sum, window_sum)
window_sum = arr[window_start] # subtract the element going out
window_start += 1 # slide the window ahead
return max_sum
def main():
print("Maximum sum of a subarray of size K: " + str(max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2])))
print("Maximum sum of a subarray of size K: " + str(max_sub_array_of_size_k(2, [2, 3, 4, 1, 5])))
main()
Complexity
 Time: \(O(N)\)
 Space: \(O(1)\)
[3/Medium] Longest Substring Without Repeating Characters
Problem

Given a string
s
, find the length of the longest substring without repeating characters. 
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
 Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
 Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
 Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
Solution: Brute Force
 Intuition:
 Check all the substring one by one to see if it has no duplicate character.
 Algorithm:
 Suppose we have a function
boolean allUnique(String substring)
which will return true if the characters in the substring are all unique, otherwise false. We can iterate through all the possible substrings of the given string s and call the functionallUnique
. If it turns out to be true, then we update our answer of the maximum length of substring without duplicate characters.  Now let’s fill the missing parts:
 To enumerate all substrings of a given string, we enumerate the start and end indices of them. Suppose the start and end indices are \(i\) and \(j\), respectively. Then we have \(0 \leq i \lt j \leq n\) (here end index \(j\) is exclusive by convention). Thus, using two nested loops with \(i\) from \(0\) to \(n  1\) and \(j\) from \(i+1\) to \(n\), we can enumerate all the substrings of \(s\).
 To check if one string has duplicate characters, we can use a set. We iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If so, we return
false
. After the loop, we returntrue
.
 Suppose we have a function
class Solution:
def lengthOfLongestSubstring(self, s: str) > int:
def check(start, end):
chars = [0] * 128
for i in range(start, end + 1):
c = s[i]
chars[ord(c)] += 1
if chars[ord(c)] > 1:
return False
return True
n = len(s)
res = 0
for i in range(n):
for j in range(i, n):
if check(i, j):
res = max(res, j  i + 1)
return res
Complexity
 Time: \(O(n^3)\)
 Space: \(O(min(n,m))\). We need \(O(k)\) space for checking a substring has no duplicate characters, where \(k\) is the size of the
Set
. The size of the Set is upper bounded by the size of the string \(n\) and the size of the charset/alphabet \(m\).
Solution: Sliding Window
 Algorithm:
 The naive approach is very straightforward. But it is too slow. So how can we optimize it?
 In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring \(s_{ij}\) from index \(i\) to \(j  1\) is already checked to have no duplicate characters. We only need to check if \(s[j]\) is already in the substring \(s_{ij}\).
 To check if a character is already in the substring, we can scan the substring, which leads to an \(O(n^2)\) algorithm. But we can do better.
 By using HashSet as a sliding window, checking if a character in the current can be done in \(O(1)\).
 A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e., \([i, j)\) (leftclosed, rightopen). A sliding window is a window “slides” its two boundaries to the certain direction. For example, if we slide \([i, j)\) to the right by 1 element, then it becomes \([i+1, j+1)\) (leftclosed, rightopen).
 Back to our problem. We use HashSet to store the characters in current window \([i, j)\) (\(j = i\) initially). Then we slide the index \(j\) to the right. If it is not in the HashSet, we slide \(j\) further. Doing so until \(s[j]\) is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index \(i\). If we do this for all \(i\), we get our answer.
class Solution:
def lengthOfLongestSubstring(self, s: str) > int:
chars = [0] * 128
left = right = 0
res = 0
while right < len(s):
r = s[right]
chars[ord(r)] += 1
# loop until
while chars[ord(r)] > 1:
l = s[left]
chars[ord(l)] = 1
left += 1
res = max(res, right  left + 1)
right += 1
return res
Complexity
 Time: \(O(2n) = O(n)\). In the worst case each character will be visited twice by ii and jj.
 Space: \(O(min(n,m))\). We need \(O(k)\) space for the sliding window, where \(k\) is the size of the
Set
. The size of the Set is upper bounded by the size of the string nn and the size of the charset/alphabet \(m\).
Solution: Sliding Window with Hashmap
 The above solution requires at most \(2n\) steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.
 The reason is that if \(s[j]\) have a duplicate in the range \([i, j)\) with index \(j'\), we don’t need to increase \(i\) little by little. We can skip all the elements in the range \([i, j']\) and let \(i\) to be \(j' + 1\) directly.
class Solution:
def lengthOfLongestSubstring(self, s: str) > int:
n = len(s)
ans = 0
# charMapping stores the mapping of the "current" index of a character
charMapping = {}
i = 0
# try to extend the range [i, j]
for j in range(n):
if s[j] in charMapping:
i = max(charMapping[s[j]], i)
ans = max(ans, j  i + 1)
charMapping[s[j]] = j + 1
return ans
Complexity
 Time: \(O(n)\). Index \(j\) will iterate \(n\) times.
 Space: \(O(min(m,n))\). Same as the previous approach.
Sliding Window with an Integer Array
 The previous implementations all have no assumption on the charset of the string
s
.  If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.
 Commonly used tables are:
int[26]
for Letters ‘a’  ‘z’ or ‘A’  ‘Z’int[128]
for ASCIIint[256]
for Extended ASCII
class Solution:
def lengthOfLongestSubstring(self, s: str) > int:
n = len(s)
ans = 0
# charMapping stores the mapping of the "current" index of a character
charMapping = [None] * 128
i = 0
# try to extend the range [i, j]
for j in range(n):
if charMapping[ord(s[j])] is not None:
i = max(charMapping[ord(s[j])], i)
ans = max(ans, j  i + 1)
charMapping[ord(s[j])] = j + 1
return ans
 Same approach, rephrased:
class Solution:
def lengthOfLongestSubstring(self, s: str) > int:
chars = [None] * 128
left = right = 0
res = 0
while right < len(s):
r = s[right]
index = chars[ord(r)]
if index != None and index >= left and index < right:
left = index + 1
res = max(res, right  left + 1)
chars[ord(r)] = right
right += 1
return res
Complexity
 Time: \(O(n)\). Index \(j\) will iterate \(n\) times.
 Space: \(O(m)\), where \(m\) is the size of the charset.
[15/Medium] 3Sum
Problem
 Given an integer array
nums
, return all the triplets[nums[i], nums[j], nums[k]]
such thati != j
,i != k
, andj != k
, andnums[i] + nums[j] + nums[k]
== 0. 
Notice that the solution set must not contain duplicate triplets.
 Example 1:
Input: nums = [1,0,1,2,1,4]
Output: [[1,1,2],[1,0,1]]
 Example 2:
Input: nums = []
Output: []
 Example 3:
Input: nums = [0]
Output: []
 Constraints:
0 <= nums.length <= 3000
105 <= nums[i] <= 105
 See problem on LeetCode.
Solution: Adapt to TwoSum
 Another way to solve this problem is to change it into a two sum problem. Instead of finding
a+b+c = 0
, you can finda+b = c
where we want to find two numbersa
andb
that are equal toc
. This is similar to the first problem. Remember if you wanted to use the exact same as the first code, it’d return indices and not numbers. Also, we need to rearrange this problem in a way that we havenums
andtarget
.
class Solution:
def threeSum(self, nums: List[int]) > List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)2):
if i > 0 and nums[i] == nums[i1]:
continue
output_2sum = self.twoSum(nums[i+1:], nums[i])
if output_2sum ==[]:
continue
else:
for idx in output_2sum:
instance = idx + [nums[i]]
res.append(instance)
output = []
for idx in res:
if idx not in output:
output.append(idx)
return output
def twoSum(self, numbers: List[int], target: int) > List[int]:
seen = {}
res = []
for i, value in enumerate(nums): #1
remaining = target  nums[i] #2
if remaining in seen: #3
res.append([value, remaining]) #4
else:
seen[value] = i #5
return res
Complexity
 Time: \(O(n^2)\)
 Space: \(O(n)\)
Solution: Two pointers

This is similar to the Two Sum II  Input Array is Sorted problem except that it’s looking for three numbers. There are some minor differences in the problem statement. It’s looking for all combinations (not just one) of solutions returned as a list. And second, it’s looking for unique combinations, so repetition is not allowed.

Here, instead of looping (line #1) to
len(nums)  1
, we loop tolen(nums)  2
since we’re looking for three numbers. Since we’re returning values, sort would be a good idea. Otherwise, if thenums
is not sorted, you cannot reducingright
pointer or increasingleft
pointer easily. 
So, first you
sort
the array and defineres = []
to collect your outputs. In line #2, we check whether two consecutive elements are equal or not because if they are, we don’t want them (solutions need to be unique) and will skip to the next set of numbers. Also, there is an additional constrain in this line thati > 0
. This is added to take care of cases likenums = [1, 1, 1]
andtarget = 3
. If we didn’t havei > 0
, then we’d skip the only correct solution and would return[]
as our answer which is wrong (correct answer is[[1, 1, 1]]
. 
We define two additional pointers this time,
left = i + 1
andright = len(nums)  1
. For example, if nums =[2, 1, 0, 1, 2]
, all the points in the case of i=1 are looking at:i
at 1, left at 0 and right at 2. We then check temp variable similar to the previous example. There is only one change with respect to the previous example here between lines #5 and #10. If we have thetemp = target
, we obviously add this set tores
in line #5. However, we’re not done yet. For a fixedi
, we still need to check and see whether there are other combinations by just changing left and right pointers. That’s what we are doing in lines #6, 7, 8. If we still have the condition ofleft < right
andnums[left]
and the number to the right of it are not the same, we move left one index to right (line #6). Similarly, ifnums[right]
and the value to left of it is not the same, we move right one index to left. This way for a fixed i, we get rid of repetitive cases. For example, ifnums = [3, 1, 1, 3,5]
andtarget = 3
, one we get the first[3, 1, 5]
,left = 1
, but,nums[2]
is also 1 which we don’t want the left variable to look at it simply because it’d again return[3, 1, 5]
. So, we move left one index. Finally, if the repeating elements don’t exists, lines #6 to #8 won’t get activated. In this case we still need to move forward by adding 1 to left and extracting 1 from right (lines #9, 10).
class Solution:
def threeSum(self, nums: List[int]) > List[List[int]]:
nums.sort() # We need to sort the list first!
res = [] # Result list holding the triplets
# len(nums)2 is because we need at least 3 numbers to continue.
for i in range(len(nums)2): #1
# Since the list is sorted, if nums[i] > 0, then all
# nums[j] with j > i are positive as well, and we cannot
# have three positive numbers sum up to 0. Return immediately.
if nums[i] > 0:
break
# if i > 0 is because when i = 0, it doesn't need to check if it's a duplicate
# element since it doesn't even have a previous element to compare with.
# This condition also helps avoid a negative index, i.e., when i = 0, nums[i1] = nums[1]
# and you don't want to skip this iteration when nums[0] == nums[1]
# The nums[i] == nums[i1] condition helps us avoid duplicates.
# E.g., given [1, 1, 0, 0, 1], when i = 0, we see [1, 0, 1]
# works. Now at i = 1, since nums[1] == 1 == nums[0], we avoid
# this iteration and thus avoid duplicates.
if i > 0 and nums[i] == nums[i1]: #2
continue
# Classic two pointer solution
left = i + 1 #3
right = len(nums)  1 #4
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if curr_sum > 0: # sum too large, move right ptr
right = 1
elif curr_sum < 0: # sum too small, move left ptr
left += 1
else:
res.append([nums[i], nums[left], nums[right]]) #5
# the below 2 loops are to avoid duplicate triplets
# we need to skip elements that are identical to our
# current solution, otherwise we would have duplicated triples
while left < right and nums[left] == nums[left + 1]: #6
left += 1
while left < right and nums[right] == nums[right  1]:#7
right = 1 #8
right = 1 #9
left += 1 #10
return res
Complexity
 Time: \(O(n^2)\)
 Space: \(O(n)\)
[18/Medium] 4Sum
Problem
 Given an array
nums
ofn
integers, return an array of all the unique quadruplets[nums[a], nums[b], nums[c], nums[d]]
such that:0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.
 Example 1:
Input: nums = [1,0,1,0,2,2], target = 0
Output: [[2,1,1,2],[2,0,0,2],[1,0,0,1]]
 Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
 Constraints:
1 <= nums.length <= 200
109 <= nums[i] <= 109
109 <= target <= 109
 See problem on LeetCode.
Solution: Two pointers
class Solution:
def fourSum(self, nums: List[int], target: int) > List[List[int]]:
# Sort the initial list
nums.sort()
# HashMap for the solution, to avoid duplicates
solution = {}
# i = 0 ..... n1
for i in range(len(nums)):
#j = i+1 ..... n1
for j in range(i+1, len(nums)):
# Two pointer approach to find the remaining two elements
start = j+1
end = len(nums)  1
while start < end:
temp = nums[i] + nums[j] + nums[start] + nums[end]
if (temp == target):
solution[(nums[i], nums[j], nums[start], nums[end])] = True
start +=1
end =1
elif temp < target:
start += 1
else:
end =1
return solution.keys()
Complexity
 Time: \(O(n^3)\)
 Space: \(O(n)\)
Solution: Adapt to TwoSumII

You should have gotten the idea, and what you’ve seen so far can be generalized to nSum. Here, I write the generic code using the same ideas as before. What I’ll do is to break down each case to a 2Sum II problem, and solve them recursively using the approach in 2Sum II example above.

First sort nums, then I’m using two extra functions, helper and twoSum. The twoSum is similar to the 2sum II example with some modifications. It doesn’t return the first instance of results, it check every possible combinations and return all of them now. Basically, now it’s more similar to the 3Sum solution. Understanding this function shouldn’t be difficult as it’s very similar to 3Sum. As for helper function, it first tries to check for cases that don’t work (line #1). And later, if the N we need to sum to get to a target is 2 (line #2), then runs the twoSum function. For the more than two numbers, it recursively breaks them down to two sum (line #3). There are some cases like line #4 that we don’t need to proceed with the algorithm anymore and we can break. These cases include if multiplying the lowest number in the list by N is more than target. Since its sorted array, if this happens, we can’t find any result. Also, if the largest array (nums[1]) multiplied by N would be less than target, we can’t find any solution. So, break.

For other cases, we run the helper function again with new inputs, and we keep doing it until we get to N=2 in which we use twoSum function, and add the results to get the final output.
class Solution:
def fourSum(self, nums: List[int], target: int) > List[List[int]]:
nums.sort()
results = []
self.helper(nums, target, 4, [], results)
return results
def helper(self, nums, target, N, res, results):
if len(nums) < N or N < 2: #1
return
if N == 2: #2
output_2sum = self.twoSum(nums, target)
if output_2sum != []:
for idx in output_2sum:
results.append(res + idx)
else:
for i in range(len(nums) N +1): #3
if nums[i]*N > target or nums[1]*N < target: #4
break
if i == 0 or i > 0 and nums[i1] != nums[i]: #5
self.helper(nums[i+1:], targetnums[i], N1, res + [nums[i]], results)
def twoSum(self, nums: List[int], target: int) > List[int]:
res = []
left = 0
right = len(nums)  1
while left < right:
temp_sum = nums[left] + nums[right]
if temp_sum == target:
res.append([nums[left], nums[right]])
right = 1
left += 1
while left < right and nums[left] == nums[left  1]:
left += 1
while right > left and nums[right] == nums[right + 1]:
right = 1
elif temp_sum < target:
left +=1
else:
right = 1
return res
Complexity
 Time: TODO
 Space: TODO
[76/Hard] Minimum Window Substring
Problem

Given two strings
s
andt
of lengthsm
andn
respectively, return the minimum window substring ofs
such that every character int
(including duplicates) is included in the window. If there is no such substring, return the empty string""
. 
A substring is a contiguous sequence of characters within the string.

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
 Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
 Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
 Constraints:
m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.
 See problem on LeetCode.
Solution: Maintain number of times a char is needed and overall missing chars; run a sliding window
 Idea:
 The current window is
s[i:j]
and the result window iss[windowStart:windowEnd]
. Inneed[char]
, store how many times characterchar
is needed (can be negative) andmissing
tells how many characters are still missing. In the loop, first add the new character to the window. Then, if nothing is missing, remove as much as possible from the window start and then update the result.
 The current window is
 Algorithm:
 Create a dict for the target list
need = collections.Counter(t)
.  Meanwhile create a empty dict for slidewindow.
 Set two point left and right from the beginning
 Valid is to calculate the item in slidewindow,the valid variable represents the number of characters in the window that meet the need condition. If the size of valid and dict_t.size() is the same, it means that the window has met the condition  and has completely covered the string T.
 Pattern for sliderwindow:
 Create a dict for the target list
class Solution:
def minWindow(self, s: str, t: str) > str:
# hash table to store the required char frequency
need = collections.Counter(t)
# total character count we need to care about
missing = len(t)
# windowStart and windowEnd to be
windowStart, windowEnd = 0, 0
i = 0
# iterate over s starting over index 1
for j, char in enumerate(s, 1):
# if char is needed, then decrease missing (since we now have it)
if need[char] > 0:
missing = 1
# decrease the freq of char from need (can be negative  which basically denotes
# that we have few extra characters which are not required but present in between current window)
need[char] = 1
# we found a valid window
if missing == 0:
# trim chars from start to find the real windowStart
while i < j and need[s[i]] < 0:
# we're moving ahead (with i += 1 down below) so add to need[s[i]]
need[s[i]] += 1
# march ahead
i += 1
# if it's only one char case or curr window is smaller, then update window
if windowEnd == 0 or ji < windowEndwindowStart:
windowStart, windowEnd = i, j
# now reset the window to explore smaller windows
# make sure the first appearing char satisfies need[char]>0 (since we're )
need[s[i]] += 1
# missed this first char, so add missing by 1
missing += 1
#update i to windowStart+1 for next window
i += 1
return s[windowStart:windowEnd]
Complexity
 Time: \(O(n^2)\)
 Space: \(O(n)\) for
need
[167/Medium] Two Sum II  Input Array Is Sorted
Problem

Given a 1indexed array of integers numbers that is already sorted in nondecreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be
numbers[index1]
andnumbers[index2]
where1 <= index1 < index2 <= numbers.length
. 
Return the indices of the two numbers,
index1
andindex2
, added by one as an integer array[index1, index2]
of length 2. 
The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
 Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
 Example 3:
Input: numbers = [1,0], target = 1
Output: [1,2]
Explanation: The sum of 1 and 0 is 1. Therefore index1 = 1, index2 = 2. We return [1, 2].
 Constraints:
2 <= numbers.length <= 3 * 104
1000 <= numbers[i] <= 1000
numbers is sorted in nondecreasing order.
1000 <= target <= 1000
The tests are generated such that there is exactly one solution.
 See problem on LeetCode.
Solution: Sliding Window
 Follow the solution to Two Sum. The only change made below was to change the order of line #4. In the previous example, the order didn’t matter. But, here the problem asks for ascending order and since the values/indices in seen has always lower indices than your current number, it should come first. Also, note that the problem says it’s not zero based, meaning that indices don’t start from zero, which is why 1 was added to both of them.
class Solution:
def twoSum(self, numbers: List[int], target: int) > List[int]:
seen = {}
for i, value in enumerate(numbers):
remaining = target  numbers[i]
if remaining in seen:
return [seen[remaining]+1, i+1] #4
else:
seen[value] = i
Complexity
 Time: \(O(n)\)
 Space: \(O(1)\)
Solution: Two Pointers
 A better approach to solve this problem is to treat it as a two pointer problem. Since the array is already sorted, this works.
 You see the following approach in a lot of problems. What you want to do is to have two pointer (if it was 3sum, you’d need three pointers). One pointer move from left and one from right.
 Let’s say you have
numbers = [1,3,6,9]
and yourtarget = 10
. Now, left points to 1 at first, and right points to 9. There are three possibilities. If you sum numbers that left and right are pointing at, you gettemp_sum
(line #1). If temp_sum is your target, you’re done! You’ll return it (line #9).  If it’s more than your target, it means that right is pointing to a very large value (line #5) and you need to bring it a little bit to the left to a smaller (or maybe an equal) value (line #6) by adding one to the index. If the
temp_sum
is less than target (line #7), then you need to move your left to a little bit larger value by adding one to the index (line #9). This way, you try to narrow down the range in which you’re looking at and will eventually find a couple of number that sum to target, then, you’ll return this in line #9.  In this problem, since it says there is only one solution, nothing extra is necessary. However, when a problem asks to return all combinations that sum to target, you can’t simply return the first instance and you need to collect all the possibilities and return the list altogether (you’ll see something like this in 3sum).
class Solution:
def twoSum(self, numbers: List[int], target: int) > List[int]:
for left in range(len(numbers) 1): #1
right = len(numbers)  1 #2
while left < right: #3
temp_sum = numbers[left] + numbers[right] #4
if temp_sum > target: #5
right = 1 #6
elif temp_sum < target: #7
left +=1 #8
else:
return [left+1, right+1] #9
Complexity
 Time: \(O(n)\)
 Space: \(O(1)\)
[198/Medium] House Robber
Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array
nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. 
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
 Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
 Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 400
 See problem on LeetCode.
Solution: Recursion
 Recurrence relation:
rob(i) = max(rob(i  2) + currentHouseValue, rob(i  1))
class Solution:
def rob(self, nums: List[int]) > int:
if len(nums) <= 2:
return max(nums)
return self.robMax(nums, len(nums)  1) # start from the last/top
def robMax(self, nums, i):
if i < 0:
return 0 # when i < 0 we just have to return 0
return max(nums[i] + self.robMax(nums, i  2), self.robMax(nums, i  1))
Complexity
 Time: \(O(2^n)\)
 Space: \(O(n)\)
Solution: Recursive/TopDown DP
class Solution:
def rob(self, nums: List[int]) > int:
def robMax(nums, dp, i):
if i < 0:
return 0
# Look Before You Leap (LBYL)
if dp[i] != 1: # if the value of dp[i] is not default i.e. 1 that means we have already calculated it so we dont have to do it again we just have to return it
return dp[i]
dp[i] = max(nums[i] + robMax(nums, dp, i  2), robMax(nums, dp, i  1))
return dp[i]
if len(nums) <= 2:
return max(nums)
dp = [1 for _ in range(len(nums))] # cache
return robMax(nums, dp, len(nums)  1)
Solution: Iterative/BottomUp DP
 Algorithm:
 For each house, the robber has two choices  to rob or not to rob. Also, you can only rob when you didn’t rob the previous house. Here, we create a DP table with size
len(nums)
anddp[i]
represents the maximum amount of money you can rob until the \(i^{th}\) house. The goal of this problem is to calculatedp[1]
, which is the maximum amount of money you can rob until the last day.  Now, let’s write a formula for the two options we have at every stage:
 If you robbed the \((i  2)^th\) house (and thus didn’t rob the previous \((i  1)^th\) house, since you cannot rob adjacent houses), you can rob the current \(i^{th}\) house. This can be written as
dp[i  2] + nums[i]
, becausedp[i  2]
denotes the maximum amount of money you can rob for the \((i  2)^th\) house, and since you haven’t robbed the \(i_th\) house, you can add \(nums[i]\).  If you robbed on the previous \((i  1)^th\) house, you can’t rob the current house. This can be written as \(dp[i  1]\).
 If you robbed the \((i  2)^th\) house (and thus didn’t rob the previous \((i  1)^th\) house, since you cannot rob adjacent houses), you can rob the current \(i^{th}\) house. This can be written as
 You can choose the maximum value between these two choices above, and the larger one is the maximum amount you can rob up until the \(i^{th}\) house. This gives us the the following recurrence formula:
dp[i] = max(nums[i  2] + nums[i], dp[i  1])
 For each house, the robber has two choices  to rob or not to rob. Also, you can only rob when you didn’t rob the previous house. Here, we create a DP table with size
class Solution:
def rob(self, nums: List[int]) > int:
if not nums:
return 0
if len(nums) < 3:
return max(nums)
dp = [0] * len(nums)
# the base cases where dp[0] is the amount you can take from 1 house and
# dp[1] is the amount you can take from 2 houses (that will be the maximum of nums[0] and nums[1])
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for num in range(2, len(nums)):
# take max of (i) the current house and two houses (i  2) before the current house, and
# (ii) take all the gains we made up to the previous house.
# (since we cannot rob adjacent houses)
dp[num] = max(nums[num] + dp[num2], dp[num1]) # the recurrence relation
return dp[1] # the last value will be your maximum amount of robbery
Complexity
 Time: \(O(n)\)
 Space: \(O(n)\)
Solution: Sliding window; just bookkeep the last two values

In the above solution, if we notice carefully we just need the last two values and not a whole array so we can further optimize it.

Note that in calculating
dp[i]
, you are just referencingdp[i  2]
anddp[i  1]
. In other words, all you need is the two values (max until the previous house and the house before), and you can discard the old values in the DP table.
 Let
a
(rob1
orprev
in the below solutions) be the maximum robbed amount corresponding to the \((i  2)^th\) house, and letb
(rob2
orcurr
in the below solutions) be the maximum robbed amount corresponding to the \((i  1)^th\) house, today’s maximum would bemax(a + nums[i], b)
. And for the next house \(i\), this the maximum for the house before (i.e., the \((i  1)^th\) house), and the maximum of the \((i  2)^th\) house is nowb
. So you can write this formula:
a, b = b, max(a + nums[i], b)
 This indicates new
a
is replaced withb
, and newb
is replaced withmax(a + nums[i], b)
. By repeating this, you can calculate until the last day without storing all the values along the way. Finally,b
at the end is what you want. So you can write the improved version.
class Solution:
def rob(self, nums: List[int]) > int:
if len(nums) <= 2:
return max(nums)
rob1, rob2 = nums[0], max(nums[0], nums[1])
for n in nums[2:]:
temp = max(rob1 + n, rob2) # the max amount we can rob from the given house and from the prev's previous and from the previous house
rob1, rob2 = rob2, temp # update both the variables
return temp # return the max amount
 Get rid of the
temp
variable:
class Solution:
def rob(self, nums: List[int]) > int:
if len(nums) <= 2:
return max(nums)
rob1, rob2 = nums[0], max(nums[0], nums[1])
for n in nums[2:]:
# the max amount we can rob from the given house and from the prev's previous and from the previous house
rob1, rob2 = rob2, max(rob1 + n, rob2) # update both the variables
return rob2 # return the max amount
 Simplified:
class Solution:
def rob(self, nums: List[int]) > int:
prev, curr = 0
# every loop, calculate the maximum cumulative amount of money until current house
for i in nums:
# as the loop begins，curr represents dp[k1]，prev represents dp[k2]
# dp[k] = max{ dp[k1], dp[k2] + i }
prev, curr = curr, max(curr, prev + i)
# as the loop ends，curr represents dp[k]，prev represents dp[k1]
return curr
Complexity
 Time: \(O(n)\)
 Space: \(O(1)\)
[1291/Medium] Sequential Digits
Problem

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range
[low, high]
inclusive that have sequential digits. 
Example 1:
Input: low = 100, high = 300
Output: [123,234]
 Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
 Constraints:
10 <= low <= high <= 10^9
 See problem on LeetCode.
Solution: Start with a defined set of digits and run a sliding window
 One might notice that all integers that have sequential digits are substrings of string “123456789”. Hence to generate all such integers of a given length, just move the window of that length along “123456789” string.
 The advantage of this method is that it will generate the integers that are already in the sorted order.
 Algorithm:
 Initialize sample string “123456789”. This string contains all integers that have sequential digits as substrings. Let’s implement sliding window algorithm to generate them.
 Iterate over all possible string lengths: from the length of
low
to the length ofhigh
. For each length iterate over all possible start indexes: from
0
to10  length
. Construct the number from digits inside the sliding window of current length.
 Add this number in the output list
nums
, if it’s greater thanlow
and less thanhigh
.
 For each length iterate over all possible start indexes: from
 Return
nums
.
class Solution:
def sequentialDigits(self, low: int, high: int) > List[int]:
digits = "123456789"
nums = []
# Iterate over all possible string lengths: from the length of low to the length of high.
for length in range(len(str(low)), len(str(high)) + 1):
# For each length iterate over all possible start indexes: from 0 to len(digits)  length.
for start in range(len(digits)  length):
num = int(digits[start: start + length])
# Construct the number from digits inside the sliding window of current length.
if low <= num <= high:
# or if num >= low and num <= high:
# Add this number in the output list nums, if it's greater than low and less than high.
nums.append(num)
return nums
Complexity
 Time: \(O(9*9)=O(36)=O(1)\). Length of the
digits
string is 9, and lengths oflow
andhigh
are between 2 and 9. Hence the nested loops are executed no more than \(8 \times 8 = 64\) times. Actually, there are 36 integers with the sequential digits. Here is how we calculate it. Starting from 9 digits in the sample string, one could construct 9  2 + 1 = 8 integers of length 2, 9  3 + 1 = 7 integers of length 3, and so on and so forth. In total, it would make 8 + 7 + … + 1 = 36 integers.

Space: \(O(9*9)=O(36)=O(1)\). To keep not more than 36 integers with sequential digits.
 Similar approach, worse runtime:
class Solution:
def sequentialDigits(self, low: int, high: int) > List[int]:
digits = "123456789"
nums = []
for i in range(len(digits)):
for j in range(i+1, len(digits)):
num = int(digits[i:j+1])
if low <= num <= high:
# or if num >= low and num <= high:
nums.append(num)
return nums
Complexity
 Time: \(O(8*8)=O(36)=O(1)\). Length of the
digits
string is 9, and lengths oflow
andhigh
are between 2 and 9. Hence the nested loops are executed no more than \(8 \times 8 = 64\) times. Actually, there are 36 integers with the sequential digits. Here is how we calculate it. Starting from 9 digits in the sample string, one could construct 9  2 + 1 = 8 integers of length 2, 9  3 + 1 = 7 integers of length 3, and so on and so forth. In total, it would make 8 + 7 + … + 1 = 36 integers.
 Space: \(O(8*8)=O(36)=O(1)\). To keep not more than 36 integers with sequential digits.