# 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 = 0s = 0for n in nums:    s += n    if s-goal in pre_sum:        res += pre_sum[s-goal]    pre_sum[s] += 1return 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 defaultdictclass 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 = 1res = Nonefor 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.diffclass 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

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

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 positionCase1     |----..                   # fall into some intervalCase2 |---..                        # smaller than the first interval startCase3         |--..                 # fall into some gapCase4                          |--- # bigger than the last interval endSame 4 cases could happen to end positionCase1  ..--|                        # 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.