After solved 1000 medium leetcode found these patterns — Sliding Window, 2 Pointer, String
Following previous posted patterns : DFS , BFS, DP, Backtracking, Monostack ,Presum, Greedy .I will continue share what I have learned from leetcoding . with high rating problems .
This article will be Sliding Window , 2 Pointers , string(not a pattern just a category)
Lets start .
Sliding Window
Core Pattern
start, end = 0, 0
res=0
while end < length(arr or string):
do_something(end)
while decreasing_window_size(start):
dosomething(start)
start +=1
res = max(res, endstart+1) # or min
end+=1
return res
The idea is control a window<start, end> size dynamically . the goal usually is to find the max or min window size . during loop every time move the end to next position while trying keep the start ,if not then decreasing window by keep moving start position to next . track and update the window size .
Sample problems
3. Longest Substring Without Repeating Characters
Thought process . goal : #1 find longest , #2 without duplicate . for #1 need sliding window #2 need hashmap (dict) .so use start, end track window left and right . as long as no duplicate , keep moving the end to next, if there is dup, move start to right until no dup . update the result .
def lengthOfLongestSubstring(self, s: str) > int:
start, end = 0, 0
arr = defaultdict(int)
res=0
while end < len(s):
arr[s[end]]+=1
while start < end and arr.get(s[end], 0) > 1:
arr[s[start]]=1
start +=1
res = max(res, endstart+1)
end+=1
return res
Another one . 209. Minimum Size Subarray Sum
Thought process. goal is to find the minimum window size when sum(<numbers in window>) ≥ target .use start and end to track window left and right ,keep adding nums[end] into sum, try to reduce the window (start+1) if possible (snums[start]≥ target) ,update result if window size < current result .
def minSubArrayLen(self, target: int, nums: List[int]) > int:
start, end=0, 0
res=float('inf')
s=0
while end < len(nums):
s += nums[end]
while s>= target+nums[start]:
s = nums[start]
start += 1
if s >= target:
res = min(res, endstart+1)
end += 1
return 0 if res == float('inf') else res
Usually when the problem about max or min length or count .could give sliding window a try. ask yourself what information need to keep track except the start and end index, then find out the condition of “decreasing window size” .
Btw, I have been asked 2 times sliding window problems in interview, both 1st round . maybe because these problems lines of code is short and good for interview. but to be honest in real life project, i have not used it to solve problem yet .
More sliding window problems
424. Longest Repeating Character Replacement
438. Find All Anagrams in a String
1004. Max Consecutive Ones III
2 Pointer
Idea
Problem 1
xxxxxyyyyyzzzzzzzzzz
 
left> < right
Problem2
ssstrrrrrinng1

pointer1>ssttrrringggg2

pointer2>
Problem3
sssssstttrrrrring
 
slow 
fast
3 cases.
#1 use left and right pointers start from 2 side of array or string , check when need to move left or right ;
#2 use 2 pointers to track 2 different array or string, decide when to move which pointer to next position;
#3 use slow and fast pointer ,each time move more steps on fast pointer than slow , see when they will meet . the classic sample is detect if there is cycle in linked list .
Sample problems
Thought process . 2 pointer case with a bit greedy thinking here. use 2 pointers start from left and right, when value[left] > value[right] move right (it does not help when move left) ; other wise ,move left .
def maxArea(self, height: List[int]) > int:
"""
maintein left and right index
when height[left] > height[right]: right1. else left + 1
"""
l,r = 0, len(height)1
res =0
while l<r:
res = max(res, min(height[l], height[r]) * (rl))
if height[l]> height[r] :
r = 1
else:
l += 1
return res
Another one . 16. 3Sum Closest (3 color flag also similar)
Sort the array . use 3 pointers left, mid, right to track the sum (left+mid+right) . based on target > sum, target<=sum, move the mid, or right (explained in comments )
def threeSumClosest(self, nums: List[int], target: int) > int:
"""
Explaination :
<sorted(array)>

left mid right
3 sum = left+mid+right
when 3sum > target:
right1 (left+1 or mid+1 will make it even bigger)
else :will try mid+1 (left+1 case is covered in outside loop)
"""
nums = sorted(nums)
l,m,r = 0, 1, len(nums)1
res = nums[l]+nums[m]+nums[r]
while l < len(nums)1:
m = l+1
r = len(nums)1
t = nums[l]+nums[m]+nums[r]
while m < r:
three_sum = nums[l]+ nums[m] +nums[r]
if abs(three_sumtarget) < abs(restarget):
res = three_sum
if three_sum > target:
r = 1
else:
m += 1
l += 1
return res
More 2 pointer problem
524. Longest Word in Dictionary through Deleting
986. Interval List Intersections
String problems
String problems usually about regex matching and searching, or use hashmap or counter.
but in case you may be asked the same, which i had been asked to solve in an interview .
When you see this problem . looks like it is stack ,but it’s not (it’s going to be slow if use stack) . could be using pure string manipulation . however it is actually a matching and replace problem, so regex usally the best option .
I list down all 3 solutions. i did #2 solution . then i found another solution in leetcode answers #3 which is even cleaner .
So when you be asked string problem, remember to give regex a try. sometimes it is a fast and clean.
1. when ']' parse previous string
def decodeString(self, s: str) > str:
i = 0
while i<len(s):
if s[i] == ']':
j = i
while s[j] != '[':
j=1
s1 = s[j+1:i]
times = ''
k=j1
while k>=0 and s[k].isdigit():
times=f'{s[k]}{times}'
k=1
s2=int(times)*s1
s=s[:k+1]+s2+s[i+1:]
i=len(s2)+k
i+=1
return s2. Use regex search (much cleaner)
def decodeString(self, s: str) > str:
pattern = '(\d+)\[([az]+)\]'
while True:
res = re.search(pattern, s)
if not res:
return s
times, s1 = int(res[1]), res[2]
s = s.replace(f'{times}[{s1}]', times*s1)
return s3. Use regex sub ( bit slower, but clearer)
def decodeString(self, s: str) > str:
pattern = '(\d+)\[([az]+)\]'
while '[' in s:
s = re.sub(pattern, lambda m: int(m.group(1))*m.group(2), s)
return s
More string problems
318. Maximum Product of Word Lengths
Conclusion
All 3 patterns i shared in this article have been asked in interviews (Sliding window : FANG, 2 Pointers : banking, String : Banking ) , 2 pointers is more like an idea instead of pattern ; for the string problems, keep regex in mind, the solution usually could be clean and fast in many cases.
Thanks for reading and happy leetcoding !