After solved 1000 medium leetcode found these patterns — Presum, Greedy, intervals
Following previous patterns : DFS , BFS, DP, Backtracking, Mono-stack .
This article will share array ,max/min and matrix, interval problem patterns. Since they are all small ones, so I put them together in one go .
Presum
Core Pattern .
Count sum while looping through every element in array . store every pre_ssum:count , if any pre_s[sum] >0, add into result .
pre_sum = defaultdict(int)
res = 0
s = 0
for n in nums:
s += n
if s-goal in pre_sum:
res += pre_sum[s-goal]
pre_sum[s] += 1
return resExamples .
930. Binary Subarrays With Sum
Thought process . This is a good usecase of presum. store “sum so far” and counting, as long as sum-goal appears before, it could become a subarray with current value .
from collections import defaultdict
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
"""
Sample :
goal 2
1 0 1 0 1 0 0 1 0 1
0 1 1 2 2 3 3 3 4 4 5 # pre_sum
<----->+pre_sum[0] # index =2
<-------> +pre_sum[0] # index =3
<-----> +pre_sum[1] # index =4
<------->
<---------> +pre_sum[1]# index =5
<------->
<-----------> +pre_sum[1] index=6
<--------->
...
goal 2
1 0 1 0 1 0 0 1 0 1
0 1 1 2 2 3 3 3 4 4 5 # pre_sum = {sum:count}
+pre_sum[0]
+pre_sum[0]
+pre_sum[1]
+pre_sum[1]
+pre_sum[1]
+pre_sum[2]
+pre_sum[2]
+pre_sum[3]
"""
pre_sum = defaultdict(int) # count[current_sum]
pre_sum[0]=1
res = 0
s = 0
for n in nums:
s += n
if s-goal in pre_sum:
res += pre_sum[s-goal]
pre_sum[s] += 1
return resNo need much more explaination here. count the sum and add into result .
More Presum problems
974. Subarray Sums Divisible by K
Max min problem
Core Pattern
_min = 1
_max = 1
res = None
for n in nums:
m1, m2 = _min, _max
_min = min(calculate(m1), calculate(m2), caculate(n))
_max = max(calculate(m1), calculate(m2), caculate(n))
res = max(_max, res)The trick here is to track both min and max values, because they could be max or min in next calculation .
Sample problems .
Thought process . Track both min and max and update result . explained with sample in code comments .
def maxProduct(self, nums: List[int]) -> int:
"""
Track the minimum and maximum while looping each number
either minimum or maximum * n could become maximum
Sample :
2 3 0 -2 4 -3 4 -5 4
min 2 3 0 -2 -8 -12 -48 -480 -1920
max 2 6 0 0 4 24 96 240 960
res 2 6 6 6 6 24 96 240 960
"""
_min = 1
_max = 1
res = None
for n in nums:
m1, m2 = _min, _max
_min = min(m1 *n, m2*n, n)
_max = max(m1 *n, m2*n, n)
if not res:
res = _max
else:
res = max(_max, res)return res
More max-min problems .
918. Maximum Sum Circular Subarray
Greedy
Classic algorithm . but this is more about the way to approach the problem ,greedy could means minimum steps, or max length or as less as possible etc. Lets see one example .
Thought process . stand at last position, try jump back as far as possible .
def canJump(self, nums: List[int]) -> bool:
"""
stand at the last position try to jump back, as far as possible.
update position and repeat the same .
"""
pos=len(nums)-1
for i in range(len(nums)-1,-1,-1):
if i+nums[i]>=pos:
pos=i
return pos==0Another one .
Greedy thinking : try play as much as possible using existing power , if not ,make most use of score.
which is : as long as still have remaining power, play the token which cost lowest , If not, reduce 1 score to play the highest token so that can recharge maximum power.
def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
"""
Greedy thinking :
as long as have power, play the token cost lowest
If not, use score to play the highest token to charge with max power
"""
tokens.sort()
score = 0
res = 0
while tokens and (power or score):
if power < tokens[0]:
if not score:
return res
score -= 1
power += tokens.pop()
else:
power -= tokens.pop(0)
score += 1
res = max(res, score)
return resGreedy thinking : try minimum cost see if possible to make schedule ,if not change the city with minimum “lose” .
class Cost:
def __init__(self, c):
self.city = 'a' if c[0] < c[1] else 'b'
self.a = c[0]
self.b = c[1]
self.diff = abs(c[0]-c[1])
def cheaper(self):
return min(self.a, self.b), self.city, self.diff
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
"""
Greedy thinking :
take the min value and see if possible to make a schedule
if not possible, convert the minimal lose to another city one by one
until make a schedule
"""
best = [Cost(c).cheaper() for c in costs]
print(best)
cur = sum([b[0] for b in best])
a_count = len([b[1] for b in best if b[1] == 'a'])
b_count = len(costs) - a_count
if a_count == b_count:
return cur
half = len(costs)//2
need_convert = half-min(a_count,b_count)
need_convert_city = 'a' if a_count > b_count else 'b'
while need_convert > 0:
idx = -1
v = float('inf')
for i in range(0, len(best)):
if best[i][1] == need_convert_city and (idx < 0 or best[i][2] < v):
v = best[i][2]
idx = i
cur += best.pop(idx)[2]
need_convert -= 1
return cur452. Minimum Number of Arrows to Burst Balloons
Greedy thinking. track the bottom and top position, make it as “narrow” as possible, then shoot at the bottom to finish most balloons.
def findMinArrowShots(self, points: List[List[int]]) -> int:
"""
Sort the array with (bottom, top) and
looping through the balloons: As long as next's bottom <= current top
if not, need another shot and start with new balloon
e.g.
[2,5], [0,7], [3,4]
Shoot at 3 can finish all
8
7 ---top
6
5 ---top
4 ---top
3 ---bottom j+1
2 ---bottom j
1
0 ---bottom i
bottom=0 bottom=2 bottom=3
top=7 top=5 top=4 ...
"""
points.sort(key=lambda x:(x[0],x[1]))
i=0
res=1
bottom, top = points[0]
while i < len(points):
j = i+1
# find all next balloons bottom <= top
while j< len(points) and points[j][0] <= top:
top = min(points[j][1], top)
j+=1
# start with next balloon
if j < len(points):
res+=1
i = j
bottom, top = points[i]
j = i+1
else:
break
return resYes you got it . instead of algorithm , greedy is more like a way of thinking or strategy, to get more score, reach as far as possible, use minimum cost , make fully use of something etc .
More greedy problems :
334. Increasing Triplet Subsequence
406. Queue Reconstruction by Height
861. Score After Flipping Matrix
Here are more problem patterns. they should be simple enough, i will only share the list of high rating problems (except the LRU cache) . however, these ones unlikely appears in interview . you can skip them if you are preparing an interview .
Matrix spiral and rotation
Strightforward . traverse the matrix, clockwise or from center then layer by layer . it’s all about simutation and play with the matrix[row][column]
Hashmap
This is more about data structuring than algorithm .
Use hashmap or dict to store the information and solve the problem in O(N) or O(N²). some problem may need to use use nested hashmap like dict<key, dict> .
Problems List .
15. 3Sum (Classic, try 2 pointer as well)
18. 4Sum (Same as above, 2 pointer also applicable)
49. Group Anagrams (could also solved by “a-z” array)
146. LRU Cache (double list + hashmap is the standard way)
but with pthon , you could use OrderedDict to popitem() and move_key_to end .which is also clean and simple.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()def get(self, key: int) -> int:
if key not in self.cache:
return -1
val = self.cache[key]
self.cache.move_to_end(key)
return valdef put(self, key: int, value: int) -> None:
if key in self.cache:
del self.cache[key]
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
More hashmap problems
260. Single Number III (or use bit but code is not very readable)
380. Insert Delete GetRandom O(1)
451. Sort Characters By Frequency (perfect usecase of python counter)
Interval
All about merge interval, sorting, or compare if 2 interval got intersection . The tricky part is about handle different cases . will explain with in below sample problem .
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
"""
For below intervals
|---|<gap>|---|..|---|
Think about the Start position
Case1 |----.. # fall into some interval
Case2 |---.. # smaller than the first interval start
Case3 |--.. # fall into some gap
Case4 |--- # bigger than the last interval endSame 4 cases could happen to end position
Case1 ..--| # fall into some interval.
Case2 -| # smaller than the first interval start.
Case3 ..--| # fall into some gap between elements.
Case4 ---| # bigger than the last end.
Then just based on the 4 Cases get the start and end merge index do merge and insert
"""
if not intervals:
return [newInterval]
new_s, new_e = newInterval
merge_start = merge_end = -1 # start and end index to be merged
merge_start_val = merge_end_val = -1 # start and end val of the new interval
if new_s > intervals[-1][1]: # Start : Case4. just append at end
return intervals+ [newInterval]
if new_e < intervals[0][0]: #End: Case2. just insert at 0
return [newInterval] + intervals
if new_s < intervals[0][0]: #Start : Case2. merge from 0
merge_start = 0
merge_start_val = new_s
if new_e> intervals[-1][1]: #end : Case4. merge until last one
merge_end = len(intervals)-1
merge_end_val = new_e
for i in range(0, len(intervals)):
# Start : Case1.
if new_s >= intervals[i][0] and new_s <= intervals[i][1]:
merge_start = i
merge_start_val = intervals[i][0]
# Start : Case3
if i>0 and new_s> intervals[i-1][1] and new_s < intervals[i][0]:
merge_start = i
merge_start_val = new_s
# End : Case1
if new_e >= intervals[i][0] and new_e <= intervals[i][1]:
merge_end = i
merge_end_val = intervals[i][1]
# End : Case3
if i>0 and new_e> intervals[i-1][1] and new_e < intervals[i][0]:
merge_end = i-1
merge_end_val = new_e
intervals[merge_start:merge_end+1] = [[merge_start_val, merge_end_val]]
return intervals
More interval problems.
435. Non-overlapping Intervals
Other high rating array related problems
80. Remove Duplicates from Sorted Array II
128. Longest Consecutive Sequence
238. Product of Array Except Self
945. Minimum Increment to Make Array Unique
955. Delete Columns to Make Sorted II
Conclusion
This article covered few problem patterns. Presum — count the sum during array looping .
Min-Max problem , use 2 variables to track the value and keep in mind the min could become max and max could become min in each compute.
Greedy — this is more about the way how to think to solve the problem (try to be “greedy” with min xx or max yy (minimum cost, steps, max length, etc). Hashmap is more about data structuring .
Interval and Matrix spiral problem are in its own category, it’s good to know could use it to structure date time or some other range or segment data and do interesection or sorting or merging or insert ,etc; or when building a game, simulating walk from the center to outside layers until reach the border.
Thanks for reading .
Happy leetcoding !
