# Presum

Core Pattern .

`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`
`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       # index =2           <-------> +pre_sum    # index =3               <-----> +pre_sum  # index =4             <------->             <---------> +pre_sum# index =5                <------->             <-----------> +pre_sum 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                   +pre_sum                     +pre_sum                       +pre_sum                         +pre_sum                           +pre_sum                             +pre_sum                               +pre_sum        """        pre_sum = defaultdict(int) # count[current_sum]        pre_sum=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 = 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)`
`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:            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 < c else 'b'        self.a = c        self.b = c        self.diff = abs(c-c)    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 for b in best])        a_count = len([b for b in best if b == '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] == need_convert_city and (idx < 0 or best[i] < v):                    v = best[i]                    idx = i            cur += best.pop(idx)            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,x))    i=0    res=1    bottom, top = points    while i < len(points):        j = i+1        # find all next balloons bottom <= top        while j< len(points) and points[j] <= top:            top = min(points[j], 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 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)`

# 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 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]: # Start : Case4. just append at end        return intervals+ [newInterval]    if new_e < intervals: #End: Case2. just insert at 0        return [newInterval] + intervals        if new_s < intervals: #Start : Case2. merge from 0        merge_start = 0        merge_start_val = new_s    if new_e> intervals[-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] and new_s <= intervals[i]:            merge_start = i            merge_start_val = intervals[i]        # Start : Case3        if i>0 and new_s> intervals[i-1] and new_s < intervals[i]:            merge_start = i            merge_start_val = new_s        # End : Case1        if new_e >= intervals[i] and new_e <= intervals[i]:            merge_end = i            merge_end_val = intervals[i]        # End : Case3        if i>0 and new_e> intervals[i-1] and new_e < intervals[i]:            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 .

--

-- ## LORY

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