If you’ve ever needed to make calculations on a contiguous array of numbers, the sliding window technique would be a useful skill to have in your toolkit. You should think of the sliding window technique when you see the keyword “contiguous.”
Photo by Seasons Windows
With the help of the sliding window technique, you only need to loop through the array once, thus reducing the time complexity to O(n).
Below is a list of practice problems from Leetcode that can be solved using the sliding window technique. You can familiarize yourself with how the sliding window technique is used.
https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters/
class Solution:
def countGoodSubstrings(self, s: str) -> int:
ans = 0
lookup = {}
for i in range(len(s)):
lookup[s[i]] = lookup.get(s[i], 0) + 1
if i - 3 >= 0:
lookup[s[i - 3]] -= 1
if lookup[s[i - 3]] == 0:
lookup.pop(s[i - 3])
if i - 2 >= 0 and len(lookup) == 3:
ans += 1
return ans
https://leetcode.com/problems/maximum-average-subarray-i/
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
avg = float("-inf")
total = 0
l = 0
for r in range(len(nums)):
total += nums[r]
if (r - l + 1) > k:
total -= nums[l]
l += 1
if (r - l + 1) == k:
avg = max(avg, total / k)
return avg
https://leetcode.com/problems/diet-plan-performance/
class Solution:
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
points = 0
running_calories = 0
for i in range(len(calories)):
running_calories += calories[i]
if i >= k - 1:
if running_calories < lower:
points -= 1
elif running_calories > upper:
points += 1
running_calories -= calories[i - k + 1]
return points
https://leetcode.com/problems/longest-substring-without-repeating-characters/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
unique = set()
l = 0
ans = 0
for r in range(len(s)):
while s[r] in unique:
unique.remove(s[l])
l += 1
unique.add(s[r])
ans = max(ans, r - l + 1)
return ans
https://leetcode.com/problems/repeated-dna-sequences/
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
ans = []
lookup = {}
for i in range(len(s)):
if i - 9 >= 0:
t = s[i - 9: i + 1]
lookup[t] = lookup.get(t, 0) + 1
if lookup.get(t) == 2:
ans.append(t)
return ans
https://leetcode.com/problems/permutation-in-string/
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
k = len(s1)
lookup1 = {}
lookup2 = {}
for i in range(len(s1)):
lookup1[s1[i]] = lookup1.get(s1[i], 0) + 1
for j in range(len(s2)):
lookup2[s2[j]] = lookup2.get(s2[j], 0) + 1
if j - k + 1 >= 0:
if lookup1 == lookup2:
return True
lookup2[s2[j - k + 1]] -= 1
if lookup2[s2[j - k + 1]] == 0:
lookup2.pop(s2[j - k + 1])
return False
https://leetcode.com/problems/minimum-size-subarray-sum/
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
ans = float("inf")
running_sum = 0
l = 0
for r in range(len(nums)):
running_sum += nums[r]
while running_sum >= target:
ans = min(ans, r - l + 1)
running_sum -= nums[l]
l += 1
return ans if ans != float("inf") else 0
https://leetcode.com/problems/find-all-anagrams-in-a-string/
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
p_dict = {}
s_dict = {}
k = len(p)
for j in range(len(p)):
p_dict[p[j]] = p_dict.get(p[j], 0) + 1
for i in range(len(s)):
s_dict[s[i]] = s_dict.get(s[i], 0) + 1
l = i - k + 1
if l >= 0:
if s_dict == p_dict:
ans.append(l)
s_dict[s[l]] -= 1
if s_dict[s[l]] == 0:
s_dict.pop(s[l])
return ans
https://leetcode.com/problems/fruit-into-baskets/
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
ans = 1
lookup = {}
l = 0
for r in range(len(fruits)):
lookup[fruits[r]] = lookup.get(fruits[r], 0) + 1
if len(lookup) <= 2:
ans = max(ans, r - l + 1)
if len(lookup) > 2:
lookup[fruits[l]] -= 1
if lookup[fruits[l]] == 0:
lookup.pop(fruits[l])
l += 1
return ans
https://leetcode.com/problems/subarray-product-less-than-k/
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
ans = 0
prod = 1
l = 0
r = 0
while r < len(nums):
prod *= nums[r]
while l <= r and prod >= k:
prod /= nums[l]
l += 1
ans += r - l + 1
r += 1
return ans