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

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

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

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 :

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 !