After solved 1000 medium leetcode found these patterns — Presum, Greedy, intervals

Presum

Core Pattern .

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 res
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 res

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)
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

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 .

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==0
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 res
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 cur
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 res

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 .

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 val
def 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)

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 end
Same 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

Other high rating array related problems

80. Remove Duplicates from Sorted Array II

Conclusion

This article covered few problem patterns. Presum — count the sum during array looping .

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
LORY

LORY

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy