Day 3 of 30 days of Data Structures and Algorithms and System Design Simplified — Sliding Window Technique
Sliding window…
Sliding Window
Importance : High
What is Sliding Window?
It’s a technique which is used to reduce multiple loops to a single loop using a window which in turn reduces the time complexity of the program. The size of window is of prime importance here.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
How does Sliding window works?
The sliding window technique is a method used in computer science and signal processing to examine a series of data points by moving a window or a subset of the data points through the larger set. The window is typically a fixed-size subset of the data, and as it “slides” through the larger set, it examines the subset of data points within the window at each position.
The basic idea behind sliding window is to have a fixed size window that slides over the input array or list and at each step, the algorithm performs a certain operation on the current window. The window is usually moved one element at a time, but can also be moved by a fixed step size.
Sliding window algorithms are often used for problems that involve finding a maximum or minimum value within a certain range, or for problems that involve counting the number of occurrences of a certain value within a range.
This involves two steps —
- Figure out the size of window and do the computation
- Move the window by 1 ( which is basically called sliding) and compute the result of new window.
Important Patterns and Techniques in Sliding Window Questions
Important patterns and techniques in sliding window questions include understanding the basic concept of a sliding window, and how to use it to solve problems efficiently. The sliding window is a technique used to scan through an array or a list while keeping track of a subset of its elements that satisfies certain constraints.
- Two pointers technique: Keeping two pointers, one at the start of the window and the other at the end. Move the end pointer to expand the window, and move the start pointer to shrink the window.
- Hashmap/Set: Keep track of the elements in the window using a hashmap or set. This allows for constant time checking of whether an element is in the window.
- Keep track of counts/frequencies of elements in the window.
- Remember the invariant: The state of the problem is completely determined by the elements in the current window.
How to identify Sliding Window Questions?
Those questions ( especially strings) in which you are asked to compute —
Min/max of subarray
Longest/count of characters of substrings
Permutation/combinations in Strings
Technique to solve Sliding window Questions
Once you have computed the sum of window of size k, move your window to get the sum of next overlapping window by leaving the leftmost element in the list and add/include the rightmost element. By doing this we are reducing the time complexity ( from O(n²) to O(n)) of re-computation of the part which is static/non-changing in every window of size k.
Only Most Important Questions with Solutions
Golden rule is — Learn by doing/implementing
In this we will see most important sliding window questions.
Lets dive in!
Longest Substring Without Repeating Characters
Question —
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "pwwkew"
Output: 3Solution :
Main Logic/Idea —
Start from first character ( left pointer) and keep adding the characters to the sliding window ( right pointer) until you find a duplicate character. Once the duplicate is found, move the sliding window to right by 1, shrink the window by leaving/taking out the left most character and keep adding characters from right until you find a duplicate. Use a set to remove the duplicates.
Implementation —
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
stringSet, lptr,ans = set(), 0, 0
for rptr in range(len(s)):
while s[rptr] in stringSet:
stringSet.remove(s[lptr])
lptr += 1
stringSet.add(s[rptr])
window = rptr - lptr +1
ans = max(ans,window)
return ansQuestion Link
Similar Pattern —
Longest Substring with At Most Two Distinct Characters
Longest Substring with At Most K Distinct Characters
Subarrays with K Different Integers
Number of Equal Count Substrings
Minimum Consecutive Cards to Pick UpLongest Nice Subarray
Full Code Video Explanation ( in progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Best Time to Buy and Sell Stock
Question —
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example :
Input: prices = [7,1,5,3,6,4]
Output: 5Solution :
Main Logic/Idea —
Buy the stock when price is low and sell when price is high. Sliding Window is decided by the two pointers say left and right. Left is initialized to start and right keeps on moving till the length of prices list. Profit is prices at right pointer minus left pointer and then calculate if thats the max profit.
Implementation —
class Solution:
def maxProfit(self, prices: List[int]) -> int:
lptr,rptr,maxProfit = 0,1,0
while rptr < len(prices):
if prices[lptr] < prices[rptr]:
ans = prices[rptr]- prices[lptr]
maxProfit= max(ans,maxProfit)
else:
lptr= rptr
rptr +=1
return maxProfitQuestion Link
Similar Pattern —
Best Time to Buy and Sell Stock IV
Best Time to Buy and Sell Stock with Cooldown
Maximum Difference Between Increasing Elements
Maximum Profit From Trading Stocks
Full Code Video Explanation ( in progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
A substring is a contiguous sequence of characters within the string.
Example :
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.Solution :
Main Logic/Idea —
Create two hashmaps to store the count of s and t. Start from left and keep adding the count of characters in s and comparing it with the count of characters in t.
As soon as the count is matched i.e t==v then store the window length, slide the window and start again by discarding the characters from the current window one by one and decrement t count by one.
Return the string window which contains all the characters in t corresponding to s.
Note : this is a very good problem to understand sliding window strategy.
Implementation —
class Solution:
def minWindow(self, s: str, t: str) -> str:
hashT, hashS,ans, ansLength,left = {},{},[-1,-1], float("infinity"),0
for i in t:
hashT[i] = 1+ hashT.get(i,0)
t,v = 0, len(hashT)
for p in range(len(s)):
i = s[p]
hashS[i] = 1+ hashS.get(i,0)
if i in hashT and hashS[i] == hashT[i]:
t+=1
while t == v:
if (p-left+1) < ansLength:
ans = [left,p]
ansLength=(p-left+1)
hashS[s[left]] -=1
if s[left] in hashT and hashS[s[left]] < hashT[s[left]]:
t -=1
left +=1
left,p =ans
return s[left:p+1] if ansLength !=float("infinity") else ""Question Link
Similar Pattern —
Smallest Range Covering Elements from K Lists
Full Code Video Explanation ( in progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
- For example,
"ACGAATTCCG"is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA. Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]Solution :
Main Logic/Idea —
Make use of set to see if the duplicate sequence of 10 is there in the given DNA array. Take left pointer and keep sliding it by 10 characters ( size of the window in 10 here)
Implementation —
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
newSet, ans= set(), set()
if s == "":
return []
for lptr in range(len(s)-9):
window = s[ lptr : lptr+10]
if window in newSet:
ans.add(window)
else:
newSet.add(window)
return list(ans)Question Link
Similar Pattern —
Strings Differ by One Character
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Minimum Size Subarray Sum
Question —
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example :
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal lengthSolution :
Main Logic/Idea —
Take two pointers ( lptr and rptr) and start from the first num in the array. Keep incrementing r through the length of array and calculate sum of no by adding nums[rptr]. When the sum is greater than total then calculate the window and return the min( window,ans). Also, subtract left nums from sum total and increment left pointer to a new slide window.
Implementation —
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
lptr, sumNo, ans = 0,0, float('inf')
for rptr in range(len(nums)):
sumNo += nums[rptr]
while sumNo >= target:
window = rptr - lptr +1
ans = min(ans,window)
sumNo -= nums[lptr]
lptr += 1
return 0 if ans == float('inf') else ansQuestion Link
Similar Pattern —
Maximum Size Subarray Sum Equals k
Maximum Length of Repeated Subarray
Minimum Operations to Reduce X to Zero
Maximum Product After K Increments
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Sliding Window Maximum
Question —
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example :
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]Solution :
Main Logic/Idea —
This question is a very good case for monotonically decreasing queue. For the current window, use two pointers left and right ( initialized to start of the array/list) and insert the values in the queue until you find a value greater than previous values. Once you find a value greater than previous values in the queue, start removing them and whatever value is left in the queue put in the output list. Next slide the window by one ( to the size of k)
Implementation —
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans, lptr,rptr = [],0,0
qu = collections.deque()
while rptr < len(nums):
while qu and nums[rptr] > nums[qu[-1]]:
qu.pop()
qu.append(rptr)
if qu[0] < lptr:
qu.popleft()
if k <= (rptr + 1):
ans.append(nums[qu[0]])
lptr += 1
rptr += 1
return ansQuestion Link
Similar Pattern —
Longest Substring with At Most Two Distinct Characters
Maximum Number of Robots Within Budget
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Longest Repeating Character Replacement
Question —
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example :
Input: s = "ABAB", k = 2
Output: 4Solution :
Main Logic/Idea —
Take a hashmap and get the count of each character in the string. Then calculate the no of positions the character can be replaced in the current window and left and right pointers using length of window minus count of character. Maintain the count of longest string after replacing the character in a variable say answer.
Implementation —
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
charMap, ans, lptr = {},0,0
for rptr in range(len(s)):
charMap[s[rptr]] = 1+ charMap.get(s[rptr],0)
windowLength = (rptr - lptr +1)
while k < (windowLength) - max(charMap.values()):
charMap[s[lptr]] -= 1
lptr += 1
ans = max(windowLength,ans)
return ansQuestion Link
Similar Pattern —
Longest Substring with At Most K Distinct Characters
Minimum Number of Operations to Make Array Continuous
Maximize the Confusion of an Exam
Longest Substring of One Repeating Character
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Permutation in String
Question —
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba")Solution :
Main Logic/Idea —
Take two arrays and get the count of s1 and s2 characters respectively. The two pointers lptr and rptr will form a window as you compare the count of each character in s1 to s2 and increment the ans if found a match.
Implementation —
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
str1,str2,ans,lptr = [0] * 26, [0] * 26,0, 0
if len(s1) > len(s2):
return False
for i in range(len(s1)):
str1[ord(s1[i]) - ord('a')] += 1
str2[ord(s2[i]) - ord('a')] += 1
for i in range(26):
ans += 1 if str1[i] == str2[i] else 0
for rptr in range(len(s1),len(s2)):
if ans == 26:
return True
idx = ord(s2[rptr]) - ord('a')
str2[idx] += 1
if str1[idx] == str2[idx]:
ans += 1
elif str1[idx] + 1 == str2[idx]:
ans -= 1
idx = ord(s2[lptr]) - ord('a')
str2[idx] -= 1
if str1[idx] == str2[idx]:
ans += 1
elif str1[idx] - 1 == str2[idx]:
ans -= 1
lptr += 1
return ans == 26Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Count Unique Characters of All Substrings of a Given String
Let’s define a function countUniqueChars(s) that returns the number of unique characters on s.
- For example, calling
countUniqueChars(s)ifs = "LEETCODE"then"L","T","C","O","D"are the unique characters since they appear only once ins, thereforecountUniqueChars(s) = 5.
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
Example 1:
Input: s = "ABC"
Output: 10Solution :
Main Logic/Idea —
Count the characters using dictionary map and then calculate the previous and next characters ( which should be unique). Lastly append in the ans list by adding the top character to previous and next character.
Implementation —
class Solution:
def uniqueLetterString(self, s: str) -> int:
ans, d = [0], defaultdict(list)
for index, char in enumerate(s):
d[char].append(index)
for key, value in d.items():
for i in range(len(value)):
current = value[i]
previous = value[i-1] if i-1 >= 0 else -1
nextchr = value[i+1] if i+1 < len(value) else len(s)
ans.append(ans[-1]+ (current - previous)*(nextchr-current))
return ans[-1]Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Fruit Into Baskets
Question —
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
- Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Example :
Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].Solution :
Main Logic/Idea —
Take maxlen, currlen, left and right pointer to the start fruit.Increment right and keep adding the count of particular fruit in the counter while checking if unique < 2. If unique > 2, then leave left fruit, slide the window by 1 and again recompute the unique fruit count. Keep updating the max length and current length.
Implementation —
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
mlen,currlen,lptr,uniquechr =0,0,0,0
mapCount = Counter()
for rptr in range(len(fruits)):
mapCount[fruits[rptr]] += 1
if mapCount[fruits[rptr]] == 1:
uniquechr += 1
while uniquechr > 2:
mapCount[fruits[lptr]] -= 1
if mapCount[fruits[lptr]] == 0:
uniquechr -= 1
lptr += 1
currlen = rptr - lptr + 1
mlen = max(mlen, currlen)
return mlenQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Minimum Number of Flips to Make the Binary String Alternating
Question —
You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:
- Type-1: Remove the character at the start of the string
sand append it to the end of the string. - Type-2: Pick any character in
sand flip its value, i.e., if its value is'0'it becomes'1'and vice-versa.
Return the minimum number of type-2 operations you need to perform such that s becomes alternating.
The string is called alternating if no two adjacent characters are equal.
- For example, the strings
"010"and"1010"are alternating, while the string"0100"is not.
Example 1:
Input: s = "111000"
Output: 2Solution :
Main Logic/Idea —
Take string and extend by its own ( str + str). Then take two alternate string 1 and 2 and add 0 and 1 respective at even and odd positions. Using left and right pointer create a sliding window and check the difference in the orginal string and alternate string. Lastly return the min difference.
Implementation —
class Solution:
def minFlips(self, s: str) -> int:
length, s, astr1,astr2,ans,diff1,diff2,lptr = len(s),s+s,"","", len(s),0,0,0
for i in range(len(s)):
astr1 += "0" if i%2 else "1"
astr2 += "1" if i%2 else "0"
for rptr in range(len(s)):
if s[rptr] != astr1[rptr]:
diff1 += 1
if s[rptr] != astr2[rptr]:
diff2 += 1
window = rptr - lptr + 1
if window > length:
if s[lptr] != astr1[lptr]:
diff1 -= 1
if s[lptr] != astr2[lptr]:
diff2 -= 1
lptr += 1
window = rptr - lptr + 1
if window == length:
ans = min(ans,diff1,diff2)
return ansQuestion Link
Similar Pattern —
Minimum Operations to Make the Array Alternating
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Tips and Techniques to solve Sliding Window Questions Fast —
- Pay attention to that part of the question where you are doing re-computation repeatedly as you slide. Store the sum in variable and keep sliding and iterating.
- Think dynamically ( Dynamic programming practice can help)
- Brute force method will lead to O(n *k) Time, O(1) Space complexity and after applying sliding window the complexity is reduced to O(n) Time & O(n) Space.
- Have a grip on how to move indexes ( like to find next greater element) or store the result.
Most important String Sliding window questions -
That’s it for now. Day 4: Backtracking Technique coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap and Stay Tuned!!
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
