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 0-4), the average is: (1+3+2+6-1)/5 => 2.2(1+3+2+6−1)/5=>2.2
1. The average of next 5 numbers (subarray from index 1-5) is: (3+2+6-1+4)/5 => 2.8(3+2+6−1+4)/5=>2.8
1. For the next 5 numbers (subarray from index 2-6), the average is: (2+6-1+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 brute-force algorithm will calculate the sum of every 5-element 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 above-mentioned input:

    • As you can see, there are four overlapping elements between the subarray (indexed from 0-4) and the subarray (indexed from 1-5). 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 the sum 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:
    1. There is an array and you add some numbers to get to (or close to) a target, or
    2. 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 (as key) and indices (as value).
  • 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] and target = 3. Let’s say you’re at index i = 0 and value = 2, ok? you need to find value = 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:
  1. Subtract the element going out of the sliding window, i.e., subtract the first element of the window.
  2. 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 re-calculating 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 >= k-1:
      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 function allUnique. 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 return true.
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)\) (left-closed, right-open). 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)\) (left-closed, right-open).
    • 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 ASCII
    • int[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 that i != j, i != k, and j != k, and nums[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 Two-Sum

  • Another way to solve this problem is to change it into a two sum problem. Instead of finding a+b+c = 0, you can find a+b = -c where we want to find two numbers a and b that are equal to -c. 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 re-arrange this problem in a way that we have nums and target.
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[i-1]:
                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 to len(nums) - 2 since we’re looking for three numbers. Since we’re returning values, sort would be a good idea. Otherwise, if the nums is not sorted, you cannot reducing right pointer or increasing left pointer easily.

  • So, first you sort the array and define res = [] 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 that i > 0. This is added to take care of cases like nums = [1, 1, 1] and target = 3. If we didn’t have i > 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 and right = 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 the temp = target, we obviously add this set to res in line #5. However, we’re not done yet. For a fixed i, 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 of left < right and nums[left] and the number to the right of it are not the same, we move left one index to right (line #6). Similarly, if nums[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, if nums = [-3, 1, 1, 3,5] and target = 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[i-1] = nums[-1]
            # and you don't want to skip this iteration when nums[0] == nums[-1]
            # The nums[i] == nums[i-1] 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[i-1]: #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 of n 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 ..... n-1
        for i in range(len(nums)):
            #j = i+1 ..... n-1
            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 Two-Sum-II

  • 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[i-1] != nums[i]: #5
                    self.helper(nums[i+1:], target-nums[i], N-1, 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 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 "".

  • 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 is s[windowStart:windowEnd]. In need[char], store how many times character char is needed (can be negative) and missing 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.
  • 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:

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 j-i < windowEnd-windowStart:  
                    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 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

  • Return the indices of the two numbers, index1 and index2, 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 non-decreasing 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 your target = 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 get temp_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/Top-Down 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/Bottom-Up 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) and dp[i] represents the maximum amount of money you can rob until the \(i^{th}\) house. The goal of this problem is to calculate dp[-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], because dp[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]\).
    • 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])
      
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[num-2], dp[num-1]) # 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 book-keep 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 referencing dp[i - 2] and dp[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 or prev in the below solutions) be the maximum robbed amount corresponding to the \((i - 2)^th\) house, and let b (rob2 or curr in the below solutions) be the maximum robbed amount corresponding to the \((i - 1)^th\) house, today’s maximum would be max(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 now b. So you can write this formula:
a, b = b, max(a + nums[i], b)
  • This indicates new a is replaced with b, and new b is replaced with max(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[k-1],prev represents dp[k-2]
            # dp[k] = max{ dp[k-1], dp[k-2] + i }
            prev, curr = curr, max(curr, prev + i)
            # as the loop ends,curr represents dp[k],prev represents dp[k-1]

        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 of high.
      • For each length iterate over all possible start indexes: from 0 to 10 - 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 than low and less than high.
    • 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 of low and high 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 of low and high 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.