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

LORY
8 min readMar 20, 2022

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 res

Examples .

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 res

No need much more explaination here. count the sum and add into result .

More Presum problems

523. Continuous Subarray Sum

525. Contiguous Array

560. Subarray Sum Equals K

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 .

152. Maximum Product Subarray

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 .

910. Smallest Range II

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 .

55. Jump Game

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

Another one .

948. Bag of Tokens

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 res

1029. Two City Scheduling

Greedy 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 cur

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

Yes 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 :

179. Largest Number

334. Increasing Triplet Subsequence

406. Queue Reconstruction by Height

861. Score After Flipping Matrix

870. Advantage Shuffle

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]

48. Rotate Image

54. Spiral Matrix

59. Spiral Matrix II

73. Set Matrix Zeroes

498. Diagonal Traverse

885. Spiral Matrix III

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)

36. Valid Sudoku

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

More hashmap problems

187. Repeated DNA Sequences

229. Majority Element II

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)

454. 4Sum II

554. Brick Wall

890. Find and Replace Pattern

898. Bitwise ORs of Subarrays

916. Word Subsets

923. 3Sum With Multiplicity

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 .

57. Insert Interval

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

More interval problems.

56. Merge Intervals

435. Non-overlapping Intervals

436. Find Right Interval

Other high rating array related problems

80. Remove Duplicates from Sorted Array II

128. Longest Consecutive Sequence

134. Gas Station

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 !

--

--

LORY

A channel which focusing on developer growth and self improvement