Skills for tackling LeetCode problems - Sliding window.
Problem Statement: Given an array, find the average of all subarrays of “K” continuous elements in it.
The Brute-Force solution will calculate the sum of every K-element subarray, which would have O(NK) time complexity. To be more efficient, we can reuse the sum from the previous subarray - subtract the element going out of the window and add the element enter the window. This algorithm would have O(N) time complexity.
def find_averages_of_subarrays(K, arr):
res = []
SUM, start = 0.0, 0
for end in range(len(arr)):
SUM += arr[end] # add the entering element
if end >= K - 1:
res.append(SUM / K)
SUM -= arr[start] # subtract the going-out element
start += 1
return res
1. Maximum Sum Subarray of Size K
Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any continuous subarray of size ‘k’.
# Time complexity O(n), space complexity O(1)
def max_sub_array_of_size_k(K, arr):
MAX, SUM, start = 0,0.0, 0
for end in range(len(arr)):
SUM += arr[end] # add the entering element
if end >= K - 1:
MAX = max(MAX, SUM)
SUM -= arr[start] # subtract the going-out element
start += 1
return MAX
2. Smallest Subarray with a Greater Sum
Given an array of positive numbers and a positive number ‘S’, find the length of the smallest continuous subarray whose sum is greater than or equal to ‘S’. Return 0 if no such subarray exists.
# Time complexity O(n), space complexity O(1)
import math
def smallest_subarray_with_given_sum(s, arr):
MIN, SUM, start = math.inf, 0.0, 0
for end in range(len(arr)):
SUM += arr[end] # add the entering element
while SUM >= s:
MIN = min(MIN, end - start + 1)
SUM -= arr[start] # subtract the going-out element
start += 1
if MIN == math.inf:
return 0
return MIN
3. Longest Substring with maximum K Distinct Characters
Given a string, find the length of the longest substring in it with no more than ‘K’ distinct characters.
# Time complexity O(N), space complexity O(K)
import math
def longest_substring_with_k_distinct(str1, k):
MAX, start = 0, 0
Hash = {}
for end in range(len(str1)):
if str1[end] not in Hash:
Hash[str1[end]] = 1
else:
Hash[str1[end]] += 1
while len(Hash) > k: # number of char is more than K
Hash[str1[start]] -= 1
if Hash[str1[start]] == 0:
del Hash[str1[start]] # otherwise it will count to len(Hash)
start += 1
MAX = max(MAX, end - start + 1)
return MAX
4. Fruits into Baskets
Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.
# Time complexity O(N), space complexity O(1)
import math
def fruits_into_baskets(str1):
MAX, start = 0, 0
Hash = {}
for end in range(len(str1)):
if str1[end] not in Hash:
Hash[str1[end]] = 1
else:
Hash[str1[end]] += 1
while len(Hash) > 2: # make sure no more than two distinct types
Hash[str1[start]] -= 1
if Hash[str1[start]] == 0:
del Hash[str1[start]]
start += 1
MAX = max(MAX, end - start + 1)
return MAX
5. Longest Substring with Distinct Characters
Given a string, find the length of the longest substring, which has all distinct characters.
# Time complexity O(N), space complexity O(K)
def non_repeat_substring(str1):
start = 0
MAX = 0
Hash = {}
for end in range(len(str1)):
if str1[end] in Hash: # start from the last of teh same letters
start = max(start, Hash[str1[end]] + 1)
Hash[str1[end]] = end # store the index of the unique letters in HashMap
MAX = max(MAX, end - start + 1) # calculate the longest sub string
return MAX
6. Longest Substring with Same Letters after Replacement
Given a string with lowercase letters only, if you are allowed to replace no more than ‘K’ letters with any letter, find the length of the longest substring having the same letters after replacement.
# Time complexity O(N), space complexity O(1)
def length_of_longest_substring(str1, k):
start, MAX_length, MAX_repeat = 0,0,0
Hash = {}
for end in range(len(str1)):
# keep track of the number of repeated letters
if str1[end] not in Hash:
Hash[str1[end]] = 1
else:
Hash[str1[end]] += 1
# max number of repeated letter in that window
MAX_repeat = max(MAX_repeat, Hash[str1[end]])
# if the number of different letters exceed k, shrink the window
if (end - start + 1 - MAX_repeat) > k:
Hash[str1[start]] -= 1
start += 1
# iterate through the str1 and find the max length
MAX_length = max(MAX_length, end - start + 1)
return MAX_length
7. Longest Subarray with Ones after Replacement
Given an array containing 0s and 1s, if your are allowed to replace no more than ‘k’ os with 1s, find the length of the longest contiguous subarray having all 1s.
# Time complexity O(n), space complexity O(1).
def length_of_longest_substring(arr, k):
start, MAX_length, MAX_count = 0,0,0
for end in range(len(arr)):
if arr[end] == 1:
MAX_count += 1
while (end - start + 1 - MAX_count) > k:
if arr[start] == 1:
MAX_count -= 1
start += 1
MAX_length = max(MAX_length, end - start + 1)
return MAX_length
