(Python) LeetCode Summary

Template:

>

Run time: $O()$, space: $O()$

1

Binary Search, Sorting

>

Run time: $O()$, space: $O()$

1

1283. Find the Smallest Divisor Given a Threshold

Binary search the result.
If the sum > threshold, the divisor is too small.
If the sum <= threshold, the divisor is big enough.

Run time: $O(n\log m)$, space: $O(1)$, where $m=\max(A)$.

1
2
3
4
5
6
7
8
9
def smallestDivisor(self, A, threshold):
    l, r = 1, max(A)
    while l < r:
        m = (l + r) / 2
        if sum((i + m - 1) / m for i in A) > threshold:
            l = m + 1
        else:
            r = m
    return l
729. My Calendar I

https://leetcode.com/problems/my-calendar-i/discuss/109476/Binary-Search-Tree-python

Run time: $O(\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MyCalendar:

    def __init__(self):
        self.ends = []
        self.schedule = []

    def book(self, start: int, end: int) -> bool:
        index = bisect.bisect(self.ends, start)
        if index == len(self.ends): 
            self.ends.append(end)
            self.schedule.append((start, end))
            return True
        if self.schedule[index][0] < end: return False
        self.ends = self.ends[:index] + [end] + self.ends[index:]
        self.schedule = self.schedule[:index] + [(start, end)] + self.schedule[index:]
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MyCalendar:

    def __init__(self):
        self.arr = []

    def book(self, start: int, end: int) -> bool:
        index = self.bise(start)
        if index == len(self.arr): 
            self.arr.append((start, end))
            return True
        if end > self.arr[index][0]: 
            return False
        self.arr = self.arr[:index] + [(start, end)] + self.arr[index:]
        return True
    
    #bisect_right self-implementation search by key= lambda x: x[1]
    def bise(self, val):
        if not self.arr: return 0
        if val >= self.arr[-1][1]: 
            return len(self.arr)
        l, r = 0, len(self.arr)-1
        while l < r:
            m = (l + r) // 2
            if self.arr[m][1] <= val: 
                l = m+1
            else: 
                r = m
        return l

# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
302. Smallest Rectangle Enclosing Black Pixels

top = search row [0…x], find first row contain 1,
bottom = search row[x+1, row], find first row contian all 0
left = search col[0…y], find first col contain 1,
right = search col[y+1, col], find first col contain all 0

Run time: $O(n\log m+m\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
    rows, cols = len(image), len(image[0])
    
    has_pixel_in_row = lambda i : any(image[i][j] == '1' for j in range(cols))
    has_pixel_in_col = lambda j : any(image[i][j] == '1' for i in range(rows))
    
    def bsearch(left, right, condition):
        while left < right:
            mid = (left + right) // 2
            if condition(mid):
                right = mid
            else:
                left = mid + 1
        return left
    
    left = bsearch(0, x+1, lambda m : has_pixel_in_row(m))
    right = bsearch(x, rows, lambda m : not has_pixel_in_row(m))
    bottom = bsearch(0, y+1, lambda m : has_pixel_in_col(m))
    up = bsearch(y, cols, lambda m : not has_pixel_in_col(m))
    
    return (right-left) * (up-bottom)
658. Find K Closest Elements

For those who are finding it hard to understand x - A[mid] > A[mid + k] - x think in terms of midpoint of the two values x > (A[mid + k] + A[mid])/2.
https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC%2B%2BPython-Binary-Search-O(log(N-K)-%2B-K)

Run time: $O(n\log(n-k))$, space: $O(k)$

1
2
3
4
5
6
7
8
9
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
    lo, hi = 0, len(arr) - k
    while lo < hi:
        mid = lo + (hi-lo)//2
        if x - arr[mid] > arr[mid + k] - x:
            lo = mid + 1
        else:
            hi = mid
    return arr[lo:lo + k]
354. Russian Doll Envelopes

*calculate the longest increasing subsequence (LIS). We first sort the envelopes by width, and we also make sure that when the width is the same, the envelope with greater height comes first. We could calculate the LISS using the standard DP algorithm (quadratic runtime), but we can just use the tails array method with a twist: we store the index of the tail, and we do leftmost insertion point as usual to find the right index in nlogn time. Why not rightmost? Think about the case [1, 1], [1, 1], [1, 1].
https://leetcode.com/problems/russian-doll-envelopes/discuss/82761/Python-O(nlogn)-O(n)-solution-beats-97-with-explanation

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
    if not envelopes:
        return 0
    n = len(envelopes)
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    dp = [0] * n
    ans = 0
    
    for _, h in envelopes:
        lo, hi = 0, ans-1
        while lo <= hi:
            mid = lo + (hi-lo)//2
            if dp[mid] >= h:
                hi = mid-1
            else:
                lo = mid+1
        dp[lo] = h
        ans = max(ans, lo+1)
    return ans
1011. Capacity To Ship Packages Within D Days

Set lo to be the max weight, set height to be the total weight. Use binary search to find the minimum capacity so that all packages could be shipped in time, and we need to return lo in the end as the lower bound.

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def shipWithinDays(self, weights: List[int], days: int) -> int:
    def doable(cap):
        num_day = 1
        curr_w = 0
        for w in weights:
            curr_w += w
            if curr_w > cap:
                curr_w = w
                num_day += 1
                if num_day > days:
                    return False
        return True
    
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi-lo) // 2
        if doable(mid):
            hi = mid
        else:
            lo = mid+1
    return lo
410. Split Array Largest Sum

Set lo to be the max element, hi. to be the sum of all elements. Find the minimum target sum that the array could be split into m parts.
https://leetcode.com/problems/split-array-largest-sum/discuss/769701/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def splitArray(self, nums: List[int], m: int) -> int:
    def feasible(threshold) -> bool:
        count = 1
        total = 0
        for num in nums:
            total += num
            if total > threshold:
                total = num
                count += 1
                if count > m:
                    return False
        return True

    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2 # target sum
        if feasible(mid):
            right = mid     
        else:
            left = mid + 1
    return left

(TLE) Let dp(i, m) denote the minimum the largest sum among subarrays when dividing nums[i…n-1] into m subarrays.

Run time: $O(mn^2)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def splitArray(self, nums: List[int], m: int) -> int:
    n = len(nums)
    cum_sum = [0]*n
    dp = [[float('inf')]*n for _ in range(m+1)]
    cum_sum[0] = nums[0]
    
    for i in range(1, n):
        cum_sum[i] = cum_sum[i-1]+nums[i]
    
    for i in range(n):
        dp[1][i] = cum_sum[i]

    for i in range(2, m+1):
        for j in range(i-1, n):
            for k in range(j):
                dp[i][j] = min(dp[i][j], max(dp[i-1][k], cum_sum[j] - cum_sum[k]))
    return dp[m][n-1]
1539. Kth Missing Positive Number

the indices can help us to get all the positive numbers in sorted order (i + 1 if i denotes the index)
Hence, A[i] - (i + 1) will be # of missing positives at index i, and this will be our 3rd sorted sequences
https://leetcode.com/problems/kth-missing-positive-number/discuss/779999/JavaC%2B%2BPython-O(logN)

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def findKthPositive(self, arr: List[int], k: int) -> int:
    l, r = 0, len(arr)
    while l < r:
        m = l + (r - l)//2
        if arr[m] - (m+1) < k: # get the correct index
            l = m + 1
        else:
            r = m
    return l + k
792. Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/discuss/1289527/Number-of-Matching-Subsequences-or-Easy-Solution-w-Explanation-or-Binary-Search

Run time: $O(L + mnlogL)$, space: $O(L)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
    ans = 0
    mappings = defaultdict(list)
    for index, char in enumerate(s):
        mappings[char].append(index)

    for word in words:
        prev = -1
        found = True
        for c in word:
            tmp = bisect.bisect(mappings[c], prev)
            if tmp == len(mappings[c]): # not found, returned last index
                found = False
                break
            else: 
                prev = mappings[c][tmp]
        if found:
            ans += 1
    return ans
162. Find Peak Element

Check if nums[m] < nums[m+1]. If so, it means the possible answer might not be on the left side, so set lo=mid+1.

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def findPeakElement(self, nums: List[int]) -> int:
    lo, hi = 0, len(nums)-1
    while lo < hi:
        m = lo + (hi-lo)//2
        if nums[m] < nums[m+1]: # here m is low mid so here is nerver a case m+1 = h while l<h
            lo = m+1 # possible answer right side without the mid            
        if nums[m] > nums[m+1]:
            hi = m # possible answer left side the mid
    return lo
1
2
3
4
5
6
7
8
9
10
def findPeakElement(self, nums: List[int]) -> int:
    def helper(nums, lo, hi):
        if lo == hi:
            return lo
        mid = lo + (hi-lo) //2
        if nums[mid] > nums[mid+1]:
            return helper(nums, lo, mid)
        return helper(nums, mid+1, hi)
    
    return helper(nums, 0, len(nums)-1)

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
def findPeakElement(self, nums: List[int]) -> int:
    for i in range(len(nums)-1):
        if nums[i] > nums[i+1]:
            return i
    return nums[len(nums)-1]
240. Search a 2D Matrix II > Search from bottom left corner. Move up if target is smaller, move right if target is greater.

Run time: $O(m+n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    if not len(matrix) or not len(matrix[0]):
        return False
    
    h, w = len(matrix), len(matrix[0])
    i, j = h-1, 0 # bottom left corner
    
    while True:
        if i < 0 or j >= w:
            break
        
        current = matrix[i][j]
        if target < current: # target is smaller, then go up
            i -= 1
        elif target > current: # target is larger, then go right
            j += 1
        
        else:# hit target
            return True
        
    return False

Recursion.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    def helper(matrix, target, i, j, s):
        if i >= m or j >= n or i < 0 or j < 0 or (i,j) in s:
            return False
        s.add((i,j))
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] < target:
            return helper(matrix, target, i+1, j, s) or \
                   helper(matrix, target, i, j+1, s)
        else:
            return helper(matrix, target, i-1, j, s) or \
                   helper(matrix, target, i, j-1, s)
            
    if target > matrix[-1][-1]:
        return False
    m,n = len(matrix), len(matrix[0])
    return helper(matrix, target, 0,0, set())
81. Search in Rotated Sorted Array II > Three cases: if `nums[mid] == target`, return True. If `nums[mid]` is equal to `nums[lo]`, we could not determine which part of the array is rotated, therefore we increment `lo` by 1. If `nums[mid]`is smaller than or equal to `nums[hi]`, then we know the right part may be monotone increasing. We check if the target falls into this interval and update the index. The last case is whether the target falls into the intervals of `lo` and `mid`.

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def search(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: bool
    """
    if not nums:
        return False
    
    lo = 0
    hi = len(nums)-1
    while lo <= hi:
        mid = lo + (hi-lo)//2
        if nums[mid] == target:
            return True
        if nums[lo] == nums[mid]:
            lo += 1
        elif nums[mid] <= nums[hi]:
            if nums[mid] < target <= nums[hi]:
                lo = mid+1
            else:
                hi = mid-1
        else:
            if nums[lo] <= target < nums[mid]:
                hi = mid-1
            else:
                lo = mid+1
    
    return False
34. Find First and Last Position of Element in Sorted Array > If the while condition has equal sign, then every case needs to increment or decrement by 1.

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def searchRange(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    def lower_bound():
        lo = 0
        hi = len(nums)
        while lo <= hi:
            mid = lo + (hi-lo)//2
            if nums[mid] >= target:
                hi = mid-1
            else:
                lo = mid+1
        return lo
    
    def upper_bound():
        lo = 0
        hi = len(nums)
        while lo <= hi:
            mid = lo + (hi-lo)//2
            if nums[mid] <= target:
                lo = mid+1
            else:
                hi = mid-1
        return hi
    
    if not nums:
        return [-1,-1]
    first = lower_bound()
    last = upper_bound()
    if first >= last:
        return [-1,-1]
    return [first, last]

Sorting

>

Run time: $O()$, space: $O()$

1

853. Car Fleet

Pair [position, speed] and sort by position in descending order, then calculate the time it takes to get to the target. Loop through each time, if the current car takes less time than previous car to get to target, then it implies it could catch up with the car in front of it, so they can form a fleet. If it takes more time than the previous car, then it needs to form a new fleet itself.
https://leetcode.com/problems/car-fleet/discuss/139850/C%2B%2BJavaPython-Straight-Forward

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    sorted_position = sorted(zip(position, speed), reverse = True)
    time_to_dest = [float((target-pos)/sp) for pos, sp in sorted_position]
    
    ans, cur = 0,0
    for t in time_to_dest:
        if t > cur:
            ans += 1
            cur = t
    return ans
378. Kth Smallest Element in a Sorted Matrix

Apply the Binary Search on the number range instead of the index range. As we know that the smallest number of our matrix is at the top left corner and the biggest number is at the bottom lower corner. These two number can represent the range i.e., the start and the end for the Binary Search. This does sound a bit counter-intuitive now, however, it will start to make sense soon. We are all accustomed to the linear array binary search algorithm.

Run time: $O(n\log \min(max-min))$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])  # For general, the matrix need not be a square

    def countLessOrEqual(x):
        cnt = 0
        c = n - 1  # start with the rightmost column
        for r in range(m):
            while c >= 0 and matrix[r][c] > x: c -= 1  # decrease column until matrix[r][c] <= x
            cnt += (c + 1)
        return cnt

    left, right = matrix[0][0], matrix[-1][-1]
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if countLessOrEqual(mid) >= k:
            ans = mid
            right = mid - 1  # try to looking for a smaller value in the left side
        else:
            left = mid + 1  # try to looking for a bigger value in the right side

    return ans

Maintain a min heap with size k.

Run time: $O(mn\log k)$, space: $O(k)$

1
2
3
4
5
6
7
8
9
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])  # For general, matrix doesn't need to be a square
    maxHeap = []
    for r in range(m):
        for c in range(n):
            heapq.heappush(maxHeap, -matrix[r][c])
            if len(maxHeap) > k:
                heapq.heappop(maxHeap)
    return -heapq.heappop(maxHeap)

Flatten the matrix and sort the array.

Run time: $O(mn\log (mn))$, space: $O(mn)$

1
2
3
4
5
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:        
    res = []
    for r in matrix:
        res += r
    return sorted(res)[k-1]

Topological Sort

2115. Find All Possible Recipes from Given Supplies

Put the <ingredient, list of what recipes need> in a dictionary, and another dict <recipe, number of ingredients>. Put all supplies to deque, pull from it and update the number of ingredients of the recipe it could make. If the recipe could be made, put it to queue. In the end, for each recipe if their number of ingredients needed is less than 0, put it in output array.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
    numIngredients = Counter()
    parentOf = defaultdict(list)
    
    for rec, ing in zip(recipes, ingredients):
        for i in ing:
            parentOf[i].append(rec)
            numIngredients[rec] += 1
    
    q = deque([i for i in supplies])
    ans = []
    
    while q:
        s = q.popleft()
        for canMake in parentOf[s]:
            numIngredients[canMake] -= 1
            if numIngredients[canMake] == 0:
                q.append(canMake)
    for recipe in recipes:
        if numIngredients[recipe] <= 0: 
            ans.append(recipe)
    return ans
631. Design Excel Sum Formula

https://leetcode.com/problems/design-excel-sum-formula/discuss/1092604/Python-1-O(1)-query-using-topological-sort-update

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Excel:

    def __init__(self, height: int, width: str):
        # (r, "c") -> val
        self.grid = defaultdict(int)
        
        # sum dependency graphs
        self.g = defaultdict(list)
        self.inv = defaultdict(list)

    def set(self, row: int, column: str, val: int) -> None:
        u = (row,column)
        self.unset(u)
        self.grid[u] = val
        self.propagate(u)
        
    def get(self, row: int, column: str) -> int:
        return self.grid[row,column]

    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        u = (row,column)
        self.unset(u)
        self.g[u] = self.itemize(numbers)
        
        for v in self.g[u]:
            self.inv[v].append(u)
        
        self.grid[u] = sum(self.grid[v] for v in self.g[u])

        self.propagate(u)
        
        return self.grid[u]
    
    # unsets sum dependencies of u
    def unset(self, u):        
        if u in self.g:
            for v in self.g[u]:
                self.inv[v].remove(u)
            
            del self.g[u]
        
    # propagates updates to all direct and indirect dependents of root
    def propagate(self, root):        
        indegree = Counter()
        
        @cache
        def recurse(u):
            for v in self.inv[u]:
                indegree[v] += 1
                recurse(v)
        
        recurse(root)
        q = [root]
        
        for u in q:
            if u != root:
                self.grid[u] = sum(self.grid[v] for v in self.g[u])
            
            for v in self.inv[u]:
                indegree[v] -= 1
                
                if indegree[v] == 0:
                    q.append(v)
    
    # returns (r,c) cells
    def itemize(self, strs):
        ret = []
        for s in strs:
            
            if ":" in s:
                start,end = s.split(":")
                
                sr,sc = int(start[1:]), start[0]
                er,ec = int(end[1:]), end[0]
                
                for r in range(sr, er+1):
                    for c in map(chr, range(ord(sc), ord(ec)+1)):
                        ret.append((r,c))
                
            else:
                r,c = int(s[1:]), s[0]
                ret.append((r,c))
        
        return ret
# Your Excel object will be instantiated and called as such:
# obj = Excel(height, width)
# obj.set(row,column,val)
# param_2 = obj.get(row,column)
# param_3 = obj.sum(row,column,numbers)

Use dictionary to store each letter’s value, and occurrences.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Excel:

    def __init__(self, height: int, width: str):
        self.cells = [{letter: {"value": 0, "sum": None} for letter in string.ascii_uppercase} for h in range(height + 1)]

    def set(self, row: int, column: str, val: int) -> None:
        self.cells[row][column] = {"value": val, "sum": None}

    def get(self, row: int, column: str) -> int:
        cell = self.cells[row][column]
        addrs = cell.get("sum")
        if not addrs:
            return cell["value"]
        return sum(self.get(*addr) * count for addr, count in addrs.items())


    def sum(self, row: int, column: str, numbers: List[str]) -> int:
        self.cells[row][column]["sum"] = self._parse(numbers)
        return self.get(row, column)
    
    def _parse(self, strs: List[str]):
        counter = Counter()
        for s in strs:
            
            if ":" in s:
                start, end = s.split(":")[0], s.split(":")[1]
            else:
                start = end = s
            for r in range(int(start[1:]), int(end[1:]) + 1):
                for ci in range(ord(start[0]), ord(end[0]) + 1):
                    counter[(r, chr(ci))] += 1
        return counter


# Your Excel object will be instantiated and called as such:
# obj = Excel(height, width)
# obj.set(row,column,val)
# param_2 = obj.get(row,column)
# param_3 = obj.sum(row,column,numbers)
329. Longest Increasing Path in a Matrix

We can model this problem as a graph in which each cell is a vertex. An edge exists only from node u to node v if u and v are adjacent up/down/left/right neighbors in matrix and if matrix[u] < matrix[v] - this is because we are looking to model only increasing paths per problem statement.
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/332696/Python-Topological-Sort-with-explanation

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
    M, N = len(matrix), len(matrix[0])
    outdegree = { (i, j): 0 for i in range(M) for j in range(N)}
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    adj = defaultdict(list)
    
    for i in range(M):
        for j in range(N):
            for x, y in dirs:
                dx = i + x 
                dy = j + y
                if (dx, dy) in outdegree and \
                matrix[i][j] < matrix[dx][dy]:
                    outdegree[i,j] += 1
                    adj[dx, dy].append((i, j))

    stack = []
    for key in outdegree:
        if outdegree[key] == 0:
            stack.append(key)

    h = 0
    while stack:
        h += 1
        newstack = []
        for x, y in stack:
            for next_x, next_y in adj[x, y]:
                outdegree[next_x, next_y] -= 1
                if outdegree[next_x, next_y] == 0:
                    newstack.append((next_x, next_y))
        stack = newstack
    return h

We can find longest decreasing path instead, the result will be the same. Use dp to record previous results and choose the max dp value of smaller neighbors.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
    # corner case
    if not matrix or not matrix[0]:
        return 0

    # initilization
    M, N = len(matrix), len(matrix[0]) # length, width
    dp = [[0]*N for i in range(M)] # 2-D matrix for store the number of steps

    # dfs function
    def dfs(i, j):
        if not dp[i][j]: # if this position is not visited
            val = matrix[i][j]
            # search four directions to find out the decreasing path
            # up
            if i > 0 and val > matrix[i-1][j]:
                up = dfs(i-1, j)
            else:
                up = 0
            # down
            if i < M-1 and val > matrix[i+1][j]:
                down = dfs(i+1, j)
            else:
                down = 0
            # left
            if j > 0 and val > matrix[i][j-1]:
                left = dfs(i, j-1)
            else:
                left = 0
            # right
            if j < N-1 and val > matrix[i][j+1]:
                right = dfs(i, j+1)
            else:
                right = 0
            # "walk" to the target neighbor and accumulate the number of steps
            dp[i][j] = 1 + max(up, down, left, right)
        return dp[i][j]

    res_path = []
    for x in range(M): # search the grid by dfs
        for y in range(N):
            res_path.append(dfs(x, y))

    return max(res_path)
269. Alien Dictionary

https://leetcode.com/problems/alien-dictionary/discuss/1150590/Beginner-Friendly-%2B-beats-98.7

Run time: $O©$, where $c$ be the total length of all the words in the input list, added together, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def alienOrder(self, words: List[str]) -> str:
    def build_graph(words):
        graph, degree = {}, {}
        # initialize
        for w in words:
            for ch in w:
                if ch in graph: continue
                graph[ch] = []
                if ch in degree: continue
                degree[ch] = 0
        
        # build graph
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
        
            found = False
            for i in range(min_len):
                if w1[i] != w2[i]:
                    # w1[i] < w2[i]
                    if w2[i] not in graph[w1[i]]:
                        graph[w1[i]].append(w2[i])
                        degree[w2[i]] += 1
                    found = True
                    break

            # a flag to prevent cases like "abc", "ab"
            # while "ab", "abc" is okay
            if found == False and len(w1) > len(w2):
                return "", ""
        return graph, degree


    graph, degree = build_graph(words)
    source = deque()
    for key in degree:
        if degree[key] == 0:
            source.append(key)
    
    res = []
    while source:
        char = source.popleft()
        res.append(char)
        
        for child in graph[char]:
            degree[child] -= 1
            if degree[child] == 0:
                source.append(child)
    
    if len(res) < len(degree):
        return ""
    
    return ''.join(res)
210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/discuss/762346/Python-BFS-beats-98-with-Detailed-Explanation-and-Comments!

Run time: $O(v+e)$, space: $O(v+e)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def findOrder(self, numCourses, prerequisiites: List[List[int]]) -> List[int]:
	n = numCourses
    src, dst = collections.Counter(), [set() for _ in range(n)]
    for d, s in prerequisites:
        src[d] += 1
		dst[s].add(d)
    ans = [x for x in range(n) if not src[x]]
    for s in ans:
        for d in dst[s]:
            src[d] -= 1
            if not src[d]: 
                ans.append(d)
    return ans if len(ans) == n else []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
  def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
      # Create a prerequisite dict. (containing courses (nodes) that need to be taken (visited)
# before we can visit the key.
      preq = {i:set() for i in range(numCourses)}
# Create a graph for adjacency and traversing.
      graph = collections.defaultdict(set)
      for i,j in prerequisites:
    # Preqs store requirments as their given.
          preq[i].add(j)
	# Graph stores nodes and neighbors.
          graph[j].add(i)
      
      q = collections.deque([])
# We need to find a starting location, aka courses that have no prereqs.
      for k, v in preq.items():
          if len(v) == 0:
              q.append(k)
# Keep track of which courses have been taken.
      taken = []
      while q:
          course = q.popleft()
          taken.append(course)
	# If we have visited the numCourses we're done.
          if len(taken) == numCourses:
              return taken
	# For neighboring courses.
          for cor in graph[course]:
	    # If the course we've just taken was a prereq for the next course, remove it from its prereqs.
              preq[cor].remove(course)
		# If we've taken all of the preqs for the new course, we'll visit it.
              if not preq[cor]:
                  q.append(cor)
# If we didn't hit numCourses in our search we know we can't take all of the courses.
      return []

https://leetcode.com/problems/course-schedule-ii/discuss/266867/Python-Topological-Sort-BFS-and-DFS-(reserve-order)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    n = numCourses
    G = [set() for _ in range(n)]
    for d, s in prerequisites:
        G[s].add(d)
    vis, orders = [0] * n, []

    def dfs_circle(x):
        vis[x] = -1
        for y in G[x]:
            if vis[y] < 0 or (not vis[y] and dfs_circle(y)):
                return True
        vis[x] = 1
        orders.append(x)
        return False

    for x in range(numCourses):
        if not vis[x] and dfs_circle(x):
            return []
    return orders[::-1]

Other

>

Run time: $O()$, space: $O()$

1

850. Rectangle Area II

Actually, we can do our interval merge in O(n) time instead of O(n^2). First, let us create all unique y coordinates: set ys, then we create correspondences between indexes and these y coordinates: this is y_i dictionary. Finally, count will be count: how many times each segment is covered. We again create sides like in previous approach.

Next, we again iterate through our sides and update area, but now when we meet new segment, we update count} for range: +1 for start of rectangle and -1 for end of rectangle. Finally, we update our cur_y_sum: we check if count is 0 and if it is more than 0, we add length of this segment to cur_y_sum.

Run time: $O(n^2)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def rectangleArea(self, rectangles):
    ys = sorted(set([y for x1, y1, x2, y2 in rectangles for y in [y1, y2]]))
    y_i = {v: i for i, v in enumerate(ys)}
    count = [0] * len(y_i)
    
    sides_lft = [(x1,-1,y1,y2) for x1,y1,x2,y2 in rectangles]
    sides_rgh = [(x2,1,y1,y2) for x1,y1,x2,y2 in rectangles]
    sides = sorted(sides_lft + sides_rgh)
     
    cur_x = cur_y_sum = area = 0
    for x, op_cl, y1, y2 in sides:
        area += (x - cur_x) * cur_y_sum
        cur_x = x
        for i in range(y_i[y1], y_i[y2]):
            count[i] += op_cl
        cur_y_sum = sum(y2 - y1 if c else 0 for y1, y2, c in zip(ys, ys[1:], count))
    return area % (10 ** 9 + 7)

https://leetcode.com/problems/rectangle-area-ii/discuss/1419181/Python-4-solutions-n3-greater-n2-log-n-greater-n2-greater-n-log-n-explained

Run time: $O(n^2\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def rectangleArea(self, rectangles: List[List[int]]) -> int:
    def merge(intervals):
        ans = []
        for beg, end in sorted(intervals):
            if not ans or ans[-1][1] < beg:
                ans += [[beg, end]]
            else:
                ans[-1][1] = max(ans[-1][1], end)
        return sum(j-i for i,j in ans)
    
    sides_lft = [(x1,0,y1,y2) for x1,y1,x2,y2 in rectangles]
    sides_rgh = [(x2,1,y1,y2) for x1,y1,x2,y2 in rectangles]
    sides = sorted(sides_lft + sides_rgh)
    
    intervals, ans, prev_x = [], 0, sides[0][0]

    for x, op_cl, y1, y2 in sides:
        ans += merge(intervals) * (x - prev_x)
        
        if op_cl == 0:
            intervals.append((y1,y2))
        else:
            intervals.remove((y1,y2))     
        prev_x = x
        
    return ans % (10**9 + 7)
253. Meeting Rooms II

Use a min heap to put the end time of each meeting. Sort the array by the start time, and for each interval, if start time is smaller than or equal to the end time of the current meeting in the heap that’s ending soonest, pop from the heap.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    h = []
    intervals.sort(key= lambda x: x[0])

    heapq.heappush(h, intervals[0][1])
    for i in intervals[1:]:
        if h and i[0] >= h[0]: 
            heapq.heappop(h)
        # a new room is allocated
        heapq.heappush(h, i[1])
    return len(h)
56. Merge Intervals

Question: How do you add intervals and merge them for a large stream of intervals? (Facebook Follow-up Question)

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    heapify(intervals)
    merged = []
    for i in range(len(intervals)):
        root = heappop(intervals)
        if merged and merged[-1][1]>=root[0]:
            merged[-1][1] = max(merged[-1][1], root[1])
        else:
            merged.append(root)
    return merged
1
2
3
4
5
6
7
8
9
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged
169. Majority Element

Boyer-Moore Voting Algorithm
If we had some way of counting instances of the majority element as +1+1 and instances of any other element as -1−1, summing them would make it obvious that the majority element is indeed the majority element.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def majorityElement(self, nums: List[int]) -> int:
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1

    return candidate

In-place sort, and the one in the middle would be the mode.

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
def majorityElement(self, nums: List[int]) -> int:
    nums.sort()
    return nums[len(nums)//2]

Put into a dictionary, and find the one with max value.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def majorityElement(self, nums: List[int]) -> int:
    count = Counter(nums).items()
    max_count, maj = 0, -1
    for k, v in count:
        if v > max_count:
            max_count = v
            maj = k
    return maj
347. Top K Frequent Elements

bucket sort. Create a list of list of length len(nums)+1, where index serves as frequency. Use a dictionary or Counter to get the frequencies of each number, and loop through each key value pair, and put the key to the corresponding buckets. Loop through the buckets reversely, if it is not empty, append the number.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
buckets = [[] for _ in range(len(nums) + 1)]
number_count = collections.defaultdict(int)
for num in nums:
    number_count[num] += 1
    
for num, freq in number_count.items():
    buckets[freq].append(num)

# buckets is a double array
flat_list = []
# traverse from right to left so number with higher frequency come first
for i in range(len(buckets) - 1, -1, -1):
    bucket = buckets[i]
    if bucket:
        for num in bucket:
            flat_list.append(num)
return flat_list[:k]

Use Counter to calculate the count for each number, which returns a dict. Then put the keys into a heap, sort by values, key=count.get, use heapq.nlargest.

Run time: $O(n\log k)$, space: $O(n+k)$

1
2
3
4
5
6
7
8
9
10
def topKFrequent(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    if k == len(nums):
        return nums
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)
215. Kth Largest Element in an Array

Quick Select.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findKthLargest(self, nums, k):
    if not nums: return
    pivot = random.choice(nums)
    left =  [x for x in nums if x > pivot]
    mid  =  [x for x in nums if x == pivot]
    right = [x for x in nums if x < pivot]
    
    L, M = len(left), len(mid)
    
    if k <= L:
        return self.findKthLargest(left, k)
    elif k > L + M:
        return self.findKthLargest(right, k - L - M)
    else:
        return mid[0]

Use heapq.nlargest(k, nums) and get the last element in the return array.

Run time: $O(n\log k)$, space: $O(k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findKthLargest(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    # heap = []
    # for n in nums:
    #     if len(heap) == k:
    #         if heap[0] < n:
    #             heappop(heap)
    #             heappush(heap, n)
    #     else:
    #         heappush(heap, n)
    # return heap[-k]
    return heapq.nlargest(k, nums)[-1]
528. Random Pick with Weight

Use binary search to find the target index

Run time: $O(n)$, $O(\log n)$, space: $O(n)$, $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def __init__(self, w):
        """
        :type w: List[int]
        """
        self.prefix_sums = []
        total = 0
        for weight in w:
            total += weight
            self.prefix_sums.append(total)
        self.total_sum = total
            
    def pickIndex(self):
        """
        :rtype: int
        """
        rand = random.random() * self.total_sum
        lo, hi = 0, len(self.prefix_sums)
        while lo < hi:
            mid = lo + (hi-lo)//2
            if rand > self.prefix_sums[mid]:
                lo = mid + 1
            else:
                hi = mid
        return lo

Keep track of cumulative sum and put it in an array, also get the total sum. Generate a number from 0 to 1, and scale with the total sum. If it is smaller than current cumulative sum, return the index.

Run time: $O(n)$, $O(n)$, space: $O(n)$, $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def __init__(self, w):
        """
        :type w: List[int]
        """
        d = sum(w)
        print(d)
        self.weighted = [float(a)/d for a in w]
            
    def pickIndex(self):
        """
        :rtype: int
        """
        rand = random.random()
        for i, w in enumerate(self.weighted):
            if rand < w:
                return i
973. K Closest Points to Origin

QuickSelect

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
    def kClosest(self, points, k):
        return self.quick_select(points, k)
    
    def quick_select(self, points, k):
        """Perform the QuickSelect algorithm on the list"""
        left, right = 0, len(points) - 1
        pivot_index = len(points)
        while pivot_index != k:
            # Repeatedly partition the list
            # while narrowing in on the kth element
            pivot_index = self.partition(points, left, right)
            if pivot_index < k:
                left = pivot_index
            else:
                right = pivot_index - 1
        
        # Return the first k elements of the partially sorted list
        return points[:k]
    
    def partition(self, points, left, right):
        """Partition the list around the pivot value"""
        pivot = self.choose_pivot(points, left, right)
        pivot_dist = self.squared_distance(pivot)
        while left < right:
            # Iterate through the range and swap elements to make sure
            # that all points closer than the pivot are to the left
            if self.squared_distance(points[left]) >= pivot_dist:
                points[left], points[right] = points[right], points[left]
                right -= 1
            else:
                left += 1
        
        # Ensure the left pointer is just past the end of
        # the left range then return it as the new pivotIndex
        if self.squared_distance(points[left]) < pivot_dist:
            left += 1
        return left
    
    def choose_pivot(self, points, left, right):
        """Choose a pivot element of the list"""
        return points[left + (right - left) // 2]
        
def squared_distance(self, point):
        """Calculate and return the squared Euclidean distance."""
        return point[0] ** 2 + point[1] ** 2

Binary Search: set the lo and hi to be the min (0) and max euclidean distance in the list of points. Then perform binary search to loop through all points in this range and classify them into two lists: distance smaller than mid, and distance greater than mid. If the length of closer list is equal to or less than k, then all of them would be included in the final result and we will skip them in the next search and update the k.
Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def kClosest(self, points, k):
    # Precompute the Euclidean distance for each point
    distances = [self.euclidean_distance(point) for point in points]
    # Create a reference list of point indices
    remaining = [i for i in range(len(points))]
    # Define the initial binary search range
    low, high = 0, max(distances)
    
    # Perform a binary search of the distances
    # to find the k closest points
    closest = []
    while k:
        mid = low + (high - low) / 2
        closer, farther = self.split_distances(remaining, distances, mid)
        if len(closer) > k:
            # If more than k points are in the closer distances
            # then discard the farther points and continue
            remaining = closer
            high = mid
        else:
            # Add the closer points to the answer array and keep
            # searching the farther distances for the remaining points
            k -= len(closer)
            closest.extend(closer)
            remaining = farther
            low = mid
            
    # Return the k closest points using the reference indices
    return [points[i] for i in closest]

def split_distances(self, remaining, distances, mid):
    """Split the distances around the midpoint
    and return them in separate lists."""
    closer, farther = [], []
    for index in remaining:
        if distances[index] <= mid:
            closer.append(index)
        else:
            farther.append(index)
    return [closer, farther]

def euclidean_distance(self, point):
    """Calculate and return the Euclidean distance."""
    return sqrt(point[0] ** 2 + point[1] ** 2)

Maintain a max heap with size $k$ that stores the negative value of the squares of coordinates. Once heap size exceeds $k$, pop the element.

Run time: $O(n\log k)$, space: $O(k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def kClosest(self, points, k):
    """
    :type points: List[List[int]]
    :type k: int
    :rtype: List[List[int]]
    """
    heap = []
    for point in points:
        dist = point[0] * point[0] + point[1] * point[1]
        heapq.heappush(heap, (-dist, point))
        if len(heap) > k:
            heapq.heappop(heap)

    return [tuple[1] for tuple in heap]

Sweep Line, Deque, Advanced BS

>

Run time: $O()$, space: $O()$

1

BFS

>

Run time: $O()$, space: $O()$

1

752. Open the Lock

https://leetcode.com/problems/open-the-lock/discuss/110232/Accepted-PythonJava-BFS-%2B-how-to-avoid-TLE

Run time: $O(n)$, space: $O(n)$, , where N is the number of strings in deadends and O(N) is required to insert all the strings into the hashset.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def openLock(self, deadends: List[str], target: str) -> int:
    marker, depth = 'x', -1
    visited, q = set(deadends), deque(['0000'])

    while q:
        size = len(q)
        depth += 1
        for _ in range(size):
            node = q.popleft()
            if node == target: return depth
            if node in visited: continue
            visited.add(node)
            q.extend(self.successors(node))
    return -1

def successors(self, src):
    res = []
    for i, ch in enumerate(src):
        num = int(ch)
        res.append(src[:i] + str((num - 1) % 10) + src[i+1:])
        res.append(src[:i] + str((num + 1) % 10) + src[i+1:])
    return res
1091. Shortest Path in Binary Matrix

Use a queue and a set to keep track of visited position and current length of path. The first time we see the lower right corner in the queue would be the shortest path.

Run time: $O(n^2)$, space: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    if not grid or not grid[0]:
        return -1
    n = len(grid)

    if grid[0][0] or grid[n-1][n-1]:
        return -1

    dirs = [[-1,0],[1,0],[0,-1],[0,1],[1,1],[1,-1],[-1,-1],[-1,1]]
    visited = set()
    q = deque()
    
    visited.add((0,0))
    q.append((0,0,1))
    while q:
        x,y,path = q.popleft()
        if x == n-1 and y == n-1:
            return path
        for d1, d2 in dirs:
            x1, y1 = x+d1, y+d2
            if 0 <= x1 < n and 0 <= y1 < n \
            and grid[x1][y1] == 0 \
            and (x1,y1) not in visited:
                q.append((x1,y1,path+1))
                visited.add((x1,y1))
    return -1
126. Word Ladder II > bi-directional search 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
    if endWord not in wordList:
        return []

    wordList = set(wordList)
    n = len(beginWord)

    found, swapped = False, False
    start_q, end_q= {beginWord}, {endWord}
    paths, res = collections.defaultdict(set), []

    while start_q and not found:
        next_q = set()
        wordList -= set(start_q)
        for word in start_q:
            for i in range(n):
                first, second = word[:i], word[i+1:]
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = first+c+second
                    if new_word in wordList:
                        if new_word in end_q:
                            found = True
                        else:
                            next_q.add(new_word)

                        paths[new_word].add(word) if swapped else paths[word].add(new_word)

        start_q = next_q
        
        if len(start_q) > len(end_q):
            start_q, end_q = end_q, start_q
            swapped = not swapped
    
    res = []
    
    def bfs(word, cur_path):
        if word == endWord:
            cur_path.append(word)
            res.append(cur_path[::])
            return
        else:
            for parent in paths[word]:
                bfs(parent, cur_path+[word])
    bfs(beginWord, [])
    return res

Create a set that contains wordList, and a dictionary layer that contains <endWord, all possible sequences> pairs. While layer is not empty, we loop through all keys, and see if the endWord is in it. Then, we loop through each character in the word, trying to replace it with every alphabet. If this new word is valid, we create an entry in the new dictionary, and the values are formed by the values of the old word. Outside of this for loop, we remove the keys in the new dictionary so that they will not be reused, and we assign the new dictionary to the old one.

Run time: $O(nk^2)$, space: $O(nk)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
    if endWord not in wordList:
        return []
    
    wordSet = set(wordList)
    layer = {}
    layer[beginWord] = [[beginWord]]
    
    while layer:
        new_l = collections.defaultdict(list)
        for word in layer:
            if word == endWord:
                return layer[word]
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in wordSet:
                        # add new word to all sequences and form new layer element
                        new_l[new_word] += [j + [new_word] for j in layer[word]]
        wordSet -= set(new_l.keys())
        layer = new_l
    
    return []
934. Shortest Bridge

First use DFS find one island, change all cells to 2 in order to differentiate from the other island, and also add the position to the stack. Get the size of the stack, while it is not empty, pop one position from the stack and explore in four directions, if it is not valid or still the same island (==2), continue. If it is 1, then it means we found the island, return the number of steps. Otherwise, we set this empty land to be 2, and append the position to the level. When we run out of current possible movements, we increment the steps by 1, and assign level to the stack.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def shortestBridge(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    def dfs(grid, i, j, stack):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
            return
        grid[i][j] = 2
        stack.append((i, j))
        
        for k in range(4):
            dfs(grid, i+dirs[k], j+dirs[k+1], stack)
    
    
    if not grid:
        return False
    
    dirs = [0, 1, 0, -1, 0]
    stack = []
    m,n = len(grid), len(grid[0])
    found = False
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dfs(grid,i, j, stack)
                found = True
                break
        if found:
            break
    
    steps = 0
    while stack:
        size = len(stack)
        level = []
        while (size):
            x,y = stack.pop()
            size -= 1
            for i in range(4):
                x1 = x + dirs[i]
                y1 = y + dirs[i+1]
                if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n or grid[x1][y1] == 2:
                    continue
                if grid[x1][y1] == 1: # found
                    return steps
                grid[x1][y1] = 2
                level.append((x1, y1))
        steps += 1
        stack = level
    return -1
317. Shortest Distance from All Buildings

https://leetcode.com/problems/shortest-distance-from-all-buildings/discuss/963506/Python-BFS-code-with-comments

Run time: $O(N^2M^2)$, space: $O(NM)$, where $N$, $M$ are the number of rows and columns in grid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def shortestDistance(self, grid: List[List[int]]) -> int:
    if not grid:
        return -1
    # create a list of buildings and a set of empty lands for easy search later
    build, land = [], set()
    for x,y in itertools.product(range(len(grid)), range(len(grid[0]))):
        if grid[x][y] == 0:
            land.add((x,y))
        elif grid[x][y] == 1:
            build.append((x,y))
    # if there is no empty land available, we can't proceed further
    if not land:
        return -1
    
    # create a dictionary where each land's position tuple is a key and its value
    # is a list of length equal to the number of buildings we found above. 
    # This list is populated with Inf, to start with, that will be updated by the
    # shortest distance between the land and building pair, found by BFS routine below.
    d = {x: [float('inf')]*len(build) for x in land}
    
    # BFS for a given building's location
    def BFS(loc):
        x, y = build[loc]
        # (x,y) is building's location on the grid and 0 is the starting distance
        q = collections.deque([(x,y,0)]) 
        while q:
            x, y, dist = q.popleft()
            for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                # we are interested in only traversing lands whose recorded distance from
                # current building is more than dist+1. We update their distance and include
                # these lands in our queue for the next layer, if that's the case
                if (i,j) in land and d[(i,j)][loc] > dist + 1:
                    d[(i,j)][loc] = dist + 1
                    q.append((i,j,dist+1))
    
    # run BFS routine for all buildings
    for loc in range(len(build)):
        BFS(loc)
        
    # compute the shortest distance to all buildings for each empty land
    min_dist = min(sum(d[x]) for x in land)
    return -1 if min_dist == float('inf') else min_dist
1293. Shortest Path in a Grid with Obstacles Elimination

Use BFS like a sonar to explore all possible next steps, and once target is in the explored area, meaning we find a solution. Use a queue to store candidates and a set to store visited positions. Keep track of total steps taken, current position, and quota. If quota is still valid and position is not visited, add it to visited set and the queue.

Run time: $O(nk)$, where n is the number of cells in the grid, k is the quota, space: $O(nk)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def shortestPath(self, grid, k):
    """
    :type grid: List[List[int]]
    :type k: int
    :rtype: int
    """
    r, c = len(grid), len(grid[0])
    target = (r-1, c-1)
    if k >= r+c-2: # if quota is greater than min # steps
        return r+c-2
    
    state = (0, 0, k) # position, and quota
    queue = deque([(0, state)]) # steps taken, position, and quota
    visited = set([state])
    
    while queue:
        steps, (row, col, k) = queue.popleft()
        
        if (row, col) == target: # reach the end
            return steps
        
        # explore next steps
        for new_r, new_c in [(row, col+1), (row+1, col), (row, col-1), (row-1, col)]:
            if 0 <= new_r < r and 0 <= new_c < c:
                new_k = k - grid[new_r][new_c] # unchange if no block here
                new_state = (new_r, new_c, new_k)
                if new_k >= 0 and new_state not in visited:
                    visited.add(new_state)
                    queue.append((steps+1, new_state))
    return -1

DFS

>

Run time: $O()$, space: $O()$

1

286. Walls and Gates

https://leetcode.com/problems/walls-and-gates/discuss/387339/Python-BFS-and-DFS

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def wallsAndGates(self, rooms: List[List[int]]) -> None:
    """
    Do not return anything, modify rooms in-place instead.
    """
    def dfs(rooms, r, c, d):
        for x, y in [(-1,0), (1,0), (0,-1), (0,1)]:
            if 0 <= r+x < len(rooms) and 0 <= c+y < len(rooms[0]) and rooms[r+x][c+y] > rooms[r][c]:
                rooms[r+x][c+y] = d + 1
                dfs(rooms, r+x, c+y, d+1)
    
    if not rooms:
        return []
    for r in range(len(rooms)):
        for c in range(len(rooms[0])):
            if rooms[r][c] == 0:
                dfs(rooms, r, c, 0)

BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def wallsAndGates(self, rooms: List[List[int]]) -> None:
    """
    Do not return anything, modify rooms in-place instead.
    """
    if not rooms:
        return []
    # Initialize the queue with all 0s
    R, C = len(rooms), len(rooms[0])
    q = collections.deque()
    for r in range(R):
        for c in range(C):
            if rooms[r][c] == 0:
                q.append((r, c))

    while q:
        r, c = q.popleft()
        for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= r+x < R and 0 <= c+y < C and rooms[r+x][c+y] > rooms[r][c]:
                rooms[r+x][c+y] = rooms[r][c] + 1
                q.append((r+x, c+y))
1368. Minimum Cost to Make at Least One Valid Path in a Grid

First, we start from (0,0) and explore other nodes based on direction. We set the corresponding position in the dp matrix to be 0 if it is not visited, and we also add this node to a queue.
Next, we iterate the queue, for each node, we try changing it to all three other directions, and call helper function recursively so that unvisited position are added to queue.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def minCost(self, grid: List[List[int]]) -> int:
    m,n = len(grid), len(grid[0])
    queue = deque()
    dp = [[float('inf')]*n for _ in range(m)]
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    k = 0
    
    def dfs(i, j):
        if not (0 <= i < m and 0 <= j < n) or dp[i][j] != float('inf'):
            return
        dp[i][j] = k
        queue.append((i, j))
        
        next_dir = grid[i][j] - 1
        x, y = dirs[next_dir]
        di, dj = i+x, j+y
        
        dfs(di, dj)
    
    dfs(0, 0)
    
    while queue:
        k += 1
        size = len(queue)
        for _ in range(size):
            i, j = queue.popleft()
            for x, y in dirs:
                di, dj = i+x, j+y
                dfs(di, dj)
    return dp[-1][-1]
834. Sum of Distances in Tree

Key idea: Once we get a node as a base and get the sum of distances, when we move the root/base to another node, nodes that are closer to the previous base will have less distance, nodes that are far from the previous base will have more distance.
formula = parent_sum - #closer nodes + #further nodes
Create a dictionary that stores the edges in undirected graph. Maintain one array that tracks the number of closer nodes, and one answer array, and one set that tracks visited nodes.
In the first dfs, we set 0 as the base node, to find out the number of total distances between each node. For each unvisited child, we call function recursively to get the number of child nodes, then update the number of closer nodes and the first entry of the answer array. After the for loop ends, we update the closer_nodes_count to be the number of closer nodes, and return it. This way we could fill in the closer_nodes_count array so that next dfs would help get the total distances for each node as root.
Second dfs implement the formula and call it recursively.
https://www.youtube.com/watch?v=dkPYrvq5EmY

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
    # formula = parent_sum - #closer nodes + #further nodes
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    closer_nodes_count = [0] * n
    ans = [0] * n

    def dfs(cur):
        num_closer_nodes = 1
        for child in graph[cur]:
            if child not in seen:
                seen.add(child)
                child_nodes_count = dfs(child)
                num_closer_nodes += child_nodes_count
                ans[0] += child_nodes_count
                
        closer_nodes_count[cur] = num_closer_nodes
        return num_closer_nodes
    
    seen = set()
    seen.add(0)
    dfs(0) # populating closer_nodes_count and asn[0]
    
    def dfs2(cur):
        for child in graph[cur]:
            # use parent to calculate the answer for child nodes
            if child not in seen:
                seen.add(child)
                ans[child] = ans[cur] - closer_nodes_count[child] + (n-closer_nodes_count[child])
                dfs2(child)
    
    seen = set()
    seen.add(0)
    dfs2(0) # use ans[0] as base to populate all other nodes' answer
    
    return ans
133. Clone Graph

Create a dictionary to store <original node, duplicate node>, then call helper function to loop through all neighbors. If it exists in the dictionary, we just add it to the neighbor list. Otherwise, we duplicate it, add it to the dictionary, append it to neighbor list, call function recursively.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        def dfs(node, dic):
            for neighbor in node.neighbors:
                if neighbor in dic:
                    dic[node].neighbors.append(dic[neighbor])
                else:
                    neighborCopy = Node(neighbor.val, [])
                    dic[neighbor] = neighborCopy
                    dic[node].neighbors.append(neighborCopy)
                    dfs(neighbor, dic)         
                
        if not node:
            return 
        nodeCopy = Node(node.val, [])
        dic = {node: nodeCopy}
        dfs(node, dic)
        return nodeCopy
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/discuss/819269/python-dfsbacktracking-with-no-memo

Run time: $O(2^{mn}mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def minFlips(self, mat: List[List[int]]) -> int:
    def flip(i,j):
        dirs = [(i,j),(i,j+1),(i,j-1),(i+1,j),(i-1,j)]
        for x,y in dirs:
            if 0 <= x < m and 0 <= y < n:
                mat[x][y] ^= 1
                
    def allZeros():
        return sum(sum(row) for row in mat) == 0
    
    def helper(pos, moves):
        if allZeros():
            self.res=min(self.res,moves)
            return
        if not pos:
            return
        for i in range(len(pos)):
            x,y = pos[i]
            flip(x,y)
            helper(pos[i+1:], moves+1)
            flip(x,y)
            
            
    m,n = len(mat), len(mat[0])
    self.res = float('inf')
    pos = [(x,y) for x in range(len(mat)) for y in range(len(mat[0]))]
    helper(pos, 0)
    
    if self.res != float('+inf'):
        return self.res 
    else:
        return -1
785. Is Graph Bipartite?

We’ll keep an array (or hashmap) to lookup the color of each node: color[node]. The colors could be 0, 1, or uncolored (-1 or null).
We should be careful to consider disconnected components of the graph, by searching each node. For each uncolored node, we’ll start the coloring process by doing a depth-first-search on that node. Every neighbor gets colored the opposite color from the current node. If we find a neighbor colored the same color as the current node, then our coloring was impossible.

Run time: $O(n+e)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isBipartite(self, graph: List[List[int]]) -> bool:
    color = {}
    for node in range(len(graph)):
        if node not in color:
            stack = [node]
            color[node] = 0
            while stack:
                node = stack.pop()
                for neighbor in graph[node]:
                    if neighbor not in color:
                        stack.append(neighbor)
                        color[neighbor] = color[node] ^ 1
                    elif color[neighbor] == color[node]:
                        return False
        return True
417. Pacific Atlantic Water Flow > Use two matrices of the same size to determine whether one position is reachable from the top left and bottom right corner. If the cell from both matrices are true, then it is reachable to both corners. In the helper function, if this position is already marked true, then return. Otherwise, marked it as true, and explore the four neighbors.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def pacificAtlantic(self, heights):
    """
    :type heights: List[List[int]]
    :rtype: List[List[int]]
    """
    dirs = [0, 1, 0, -1, 0]
    m, n = len(heights), len(heights[0])
    
    def dfs(heights, reach, x, y):
        if reach[x][y]:
            return
        reach[x][y] = True
        for i in range(4):
            next_x, next_y = x+dirs[i], y+dirs[i+1]
            if 0 <= next_x < m and 0 <= next_y < n and heights[x][y] <= heights[next_x][next_y]:
                dfs(heights, reach, next_x, next_y)
    
    if not heights or len(heights[0]) == 0:
        return []
    
    reachable_p = [[False for _ in range(m)] for _ in range(n)]
    reachable_a = [[False for _ in range(m)] for _ in range(n)]
    ans = []
    for i in range(m):
        dfs(heights, reachable_p, i, 0)
        dfs(heights, reachable_a, i, n-1)
    
    for i in range(len(heights[0])):
        dfs(heights, reachable_p, 0, i)
        dfs(heights, reachable_a, m-1, i)
    
    for i in range(m):
        for j in range(n):
            if reachable_p[i][j] and reachable_a[i][j]:
                ans.append([i,j])
    
    return ans
547. Number of Provinces

In order to find the number of connected components in an undirected graph, one of the simplest methods is to make use of Depth First Search starting from every node. We make use of visitedvisited array of size N(M is of size NxN).

Run time: $O(n^2)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findCircleNum(self, isConnected):
    """
    :type isConnected: List[List[int]]
    :rtype: int
    """
    def dfs(isConnected, i, visited):
        visited.add(i)
        for j in range(len(isConnected)):
            if isConnected[i][j] == 1 and j not in visited:
                dfs(isConnected, j, visited)
    
    
    if not isConnected:
        return 0
    
    visited = set()
    count = 0
    for i in range(len(isConnected)):
        if i not in visited:
            dfs(isConnected, i, visited)
            count += 1
    return count
695. Max Area of Island > in the helper function, change the grid value from 1 to 0, then call the function again for the four directions plus 1.

Run time: $O(n^2)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxAreaOfIsland(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    def dfs(grid, i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
            return 0
        grid[i][j] = 0
        return 1+dfs(grid,i+1,j)+dfs(grid,i-1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1)
    
    if not grid or len(grid) == 0 or len(grid[0]) == 0:
        return 0
    
    max_area = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            max_area = max(max_area, dfs(grid, i, j))
    return max_area
366. Find Leaves of Binary Tree > Create helper function that gets the height of a node. In the function, use post-order traversal to get the height of the left and right child, then set the max of them + 1 as the height of given node. Put in a dictionary.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
def findLeaves(self, root: 'TreeNode') -> 'List[List[int]]':
    res = []
    def dfs(root):
        if not root:
            return -1
        height = max(dfs(root.left), dfs(root.right)) + 1
        if height >= len(res):
            res.append([])
        res[height].append(root.val)
        return height
    dfs(root)
    return res
my implementation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def findLeaves(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    d = {}
    def getHeight(node):
        if node is None:
            return -1
        leftH = getHeight(node.left)
        rightH = getHeight(node.right)
        currH = max(leftH, rightH)+1
        if currH in d:
            d[currH].append(node.val)
        else:
            d[currH] = [node.val]
        return currH
    
    ans = []
    getHeight(root)
    for k, v in d.items():
        ans.append(v)
        
    return ans

Backtracking

>

Run time: $O()$, space: $O()$

1

465. Optimal Account Balancing

Store non-zero balance to a list, then use backtracking to loop through all unvisited balances (look forward), and if their balance has different sign, update the candidate’s balance, minimize ans by calling backtracking function recursively plus 1.
https://www.youtube.com/watch?v=B8pPWgLa2lQ

Run time: $O(n^2)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def minTransfers(self, transactions: List[List[int]]) -> int:
    debts = defaultdict(int)
    for f, t, amt in transactions:
        debts[f] -= amt
        debts[t] += amt
    
    debts_list = [debts[id] for id in debts if debts[id] != 0]
    
    n = len(debts_list)
    
    def backtrack(ind):
        while ind < n and debts_list[ind] == 0:
            ind += 1
        if ind == n:
            return 0
        
        ans = float('inf')
        for i in range(ind+1, n):
            if debts_list[ind] * debts_list[i] < 0:
                debts_list[i] += debts_list[ind]
                ans = min(ans, backtrack(ind+1)+1)
                debts_list[i] -= debts_list[ind]
        return ans
    
    return backtrack(0)
489. Robot Room Cleaner

This solution is based on the same idea as maze solving algorithm called right-hand rule. Go forward, cleaning and marking all the cells on the way as visited. At the obstacle turn right, again go forward, etc. Always turn right at the obstacles and then go forward. Consider already visited cells as virtual obstacles.

Run time: $O(N−M)$, space: $O(N−M)$, where $N$ is a number of cells in the room and $M$ is a number of obstacles.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def cleanRoom(self, robot):
    """
    :type robot: Robot
    :rtype: None
    """
    def go_back():
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnLeft()
        robot.turnLeft()
        
    def backtrack(cell = (0, 0), d = 0):
        visited.add(cell)
        robot.clean()
        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
        for i in range(4):
            new_d = (d + i) % 4
            new_cell = (cell[0] + directions[new_d][0], \
                        cell[1] + directions[new_d][1])
            
            if new_cell not in visited and robot.move():
                backtrack(new_cell, new_d)
                go_back()
            # turn the robot following chosen direction : clockwise
            robot.turnRight()

    # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = set()
    backtrack()
301. Remove Invalid Parentheses

BFS.

Run time: $O(2^n)$, space: $O(2^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def removeInvalidParentheses(self, s: str) -> List[str]:
    # initialize a set with one element
    # set is used here in order to avoid duplicate element
    level = {s}
    while True:
        valid = []
        for elem in level:
            if self.isValid(elem):
                valid.append(elem)
        if valid:
            return valid
        # initialize an empty set
        new_level = set()
        # BFS
        for elem in level:
            for i in range(len(elem)):
                new_level.add(elem[:i] + elem[i + 1:])
        level = new_level

def isValid(self,s):
    count = 0
    for c in s:
        if c == '(':
            count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

Backtracking, DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def removeInvalidParentheses(self, s: str) -> List[str]:
    def isValid(s):
        stack = []
        for i in range(len(s)):
            if( s[i] == '(' ):
                stack.append( (i,'(') )
            elif( s[i] == ')' ):
                if(stack and stack[-1][1] == '('):
                    stack.pop()
                else:
                    stack.append( (i,')') )         # pushing invalid close braces also
        return len(stack) == 0, stack
    
    
    def dfs( s, left, right):
        visited.add(s)
        if left == 0 and right == 0 and isValid(s)[0]:  res.append(s)
        for i, ch in enumerate(s):
            if ch != '(' and ch != ')': continue                                    # if it is any other char ignore.
            if (ch == '(' and left == 0) or (ch == ')' and right == 0): continue    # if left == 0 then removing '(' will only cause imbalance. Hence, skip.
            if s[:i] + s[i+1:] not in visited:
                dfs( s[:i] + s[i+1:], left - (ch == '('), right - (ch == ')') )
    
    stack = isValid(s)[1]
    lc = sum([1 for val in stack if val[1] == "("]) # num of left braces
    rc = len(stack) - lc
    
    res, visited = [], set()
    dfs(s, lc, rc)
    return res
79. Word Search

Go through each entry, and in the helper function, check edge cases. If word length is zero, then it means this word has been found. Set the current entry to be #, call functions in four directions recursively, then reverse the change, return the result.

Run time: $O(n\cdot 3^L)$, space: $O(L)$, where $n$ is the number of cells in the board, $L$ is the length of the word to be matched, 3 is the number of further choices in the next step

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def exist(self, board, word):
    """
    :type board: List[List[str]]
    :type word: str
    :rtype: bool
    """
    # check whether can find word, start at (i,j) position    
    def dfs(board, i, j, word):
        if len(word) == 0: # all the characters are checked
            return True
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:
            return False
        tmp = board[i][j]  # first character is found, check the remaining part
        board[i][j] = "#"  # avoid visit agian 
        # check whether can find "word" along one direction
        res = dfs(board, i+1, j, word[1:]) or dfs(board, i-1, j, word[1:]) \
        or dfs(board, i, j+1, word[1:]) or dfs(board, i, j-1, word[1:])
        board[i][j] = tmp
        return res

    if not board:
        return False
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, i, j, word):
                return True
    return False
77. Combinations

in the helper function, check whether current combination length equals to k, then append to the answer list. In the for loop, pass the array that skips the current element, the path that combines this element.

Run time: $O(k {n \choose k})$, space: $O({n \choose k})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combine(self, n, k):
    """
    :type n: int
    :type k: int
    :rtype: List[List[int]]
    """
    def dfs(nums, k, path, ans):
        if len(path) == k:
            ans.append(path)
            return
        for i in range(len(nums)):
            dfs(nums[i+1:], k, path+[nums[i]], ans)
            
    ans = []
    dfs(list(range(1, n+1)), k, [], ans)
    return ans
46. Permutations > `[:]` makes a deep copy of the list. If you passed back the original list, it would be modified by future swaps. Otherwise the reference to the array is appended rather than the actual list.

Run time: $O(\sum_{k=1}^n P(n, k))$, space: $O(n!)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    def backtracking(nums, level, ans):
        if level == len(nums)-1:
            ans.append(nums[:])
            return
        for i in range(level, len(nums)):
            nums[i], nums[level] = nums[level], nums[i]
            backtracking(nums, level+1, ans)
            nums[i], nums[level] = nums[level], nums[i]
            
            
    ans = []
    backtracking(nums, 0, ans)
    return ans
1
2
3
4
5
6
7
8
9
10
def permute(self, nums):
    if len(nums) == 1:
        return [nums]
    result = []
    for i in range(len(nums)):
        others = nums[:i] + nums[i+1:]
        other_permutations = self.permute(others)
        for permutation in other_permutations:
            result.append([nums[i]] + permutation)
    return result
282. Expression Add Operators

https://leetcode.com/problems/expression-add-operators/discuss/71968/Clean-Python-DFS-with-comments

Run time: $O(n\cdot 4^n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def addOperators(self, num, target):
    """
    :type num: str
    :type target: int
    :rtype: List[str]
    """
    def backtracking(idx=0, path='', value=0, prev=None):
        if idx == len(num) and value == target:
            rtn.append(path)
            return
    
        for i in range(idx+1, len(num)+1):
            temp = int(num[idx:i])
            if i == idx+1 or (i > idx+1 and num[idx] != '0'):
                if not prev:
                    backtracking(i, num[idx:i], temp, temp)
                else:
                    backtracking(i, path+'+'+num[idx:i], value+temp, temp)
                    backtracking(i, path+'-'+num[idx:i], value-temp, -temp)
                    backtracking(i, path+'*'+num[idx:i], value-prev+prev*temp, prev*temp)
                    
    rtn = []
    backtracking()
    return rtn

Linked List & Array

>

Run time: $O()$, space: $O()$

1

54. Spiral Matrix

Maintain four variables - top, bottom, left, right, while they are valid, run four for loops and update them. In the end, if the output length is less than actual cells, run a nested for loop for the rest of the bounds.

Run time: $O(mn)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    height = len(matrix)
    width = len(matrix[0])
    
    top = 0
    bottom = height - 1
    left = 0
    right = width - 1
    
    ans = []
    while top < bottom and left < right:
        for col in range(left, right):
            ans.append(matrix[top][col])
        
        for row in range(top, bottom):
            ans.append(matrix[row][right])
        
        for col in range(right, left, -1):
            ans.append(matrix[bottom][col])
        
        for row in range(bottom, top, -1):
            ans.append(matrix[row][left])
        
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    
    # If a matrix remain inside it is either a 1xn or a mx1
    # a linear scan will return the same order as spiral for these
    if len(ans) < height*width:
        for row in range(top, bottom+1):
            for col in range(left, right+1):
                ans.append(matrix[row][col])
    
    return ans
284. Peeking Iterator

Store the next value outside the iterator. When next is called return the stored value and populate with next value from iterator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iter = iterator
        self.temp = None
        if self.iter.hasNext():
            self.temp = self.iter.next()
        

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self.temp

    def next(self):
        """
        :rtype: int
        """
        ret = self.temp
        self.temp = None
        if self.iter.hasNext():
            self.temp = self.iter.next()
        return ret

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.temp is not None

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].
900. RLE Iterator

Keep track of the index, and increment 2 at a time once the number has been used up.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class RLEIterator:
    
    def __init__(self, A: List[int]):
        self.A = A
        self.index = 0
        
    def next(self, n: int) -> int:
        while self.index < len(self.A):
            if n <= self.A[self.index]:
                self.A[self.index] -= n
                return self.A[self.index + 1]
            n -= self.A[self.index]
            self.index += 2
        return -1
23. Merge k Sorted Lists

Put <value, node index in array, node> to a heap, each time pop the smallest element, set the next element to be the next element, then push the next element back to the heap.

Run time: $O(n\log k)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    curr = head = ListNode(0)
    q = []
    for l_id, l in enumerate(lists):
        if l:
            heapq.heappush(q, (l.val, l_id, l))
        
    while q:
        _, l_id, temp = heapq.heappop(q)
        curr.next = temp
        curr = curr.next
        
        if curr.next:
            heapq.heappush(q, (curr.next.val, l_id, curr.next))
    return head.next
1877. Minimize Maximum Pair Sum in Array

Sort the array, then add from start and end, keep track of the max sum.

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def minPairSum(self, nums: List[int]) -> int:
    if not nums or len(nums) % 2 == 1:
        return -1
    nums.sort()
    min_sum = float('-inf')
    for i in range(len(nums)//2):
        temp = nums[i] + nums[len(nums)-1-i]
        min_sum = max(min_sum, temp)
    return min_sum
384. Shuffle an Array

The randrange() method returns a randomly selected element from the specified range.
https://leetcode.com/problems/shuffle-an-array/discuss/85957/easy-python-solution-based-on-generating-random-index-and-swapping

Run time: $O(1)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def __init__(self, nums: List[int]):
    self.nums = nums
  
def reset(self) -> List[int]:
    return self.nums


def shuffle(self) -> List[int]:
    ans = self.nums[:]                     # copy list
    for i in range(len(ans)-1, 0, -1):     # start from end
        j = random.randrange(0, i+1)    # generate random index 
        ans[i], ans[j] = ans[j], ans[i]    # swap
    return ans
1509. Minimum Difference Between Largest and Smallest Value in Three Moves

Only keep track of the largest and smallest 3 elements.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minDifference(self, nums: List[int]) -> int:
    if len(nums) < 5:
        return 0
    
    maxV, minV = [-float('inf')] * 4, [float('inf')] * 4
    for n in nums:
        if n > maxV[0]:
            maxV[0] = n
            for i in range(0, 3):
                if maxV[i] > maxV[i + 1]:
                    maxV[i], maxV[i + 1] = maxV[i + 1], maxV[i]     
        if n < minV[0]:
            minV[0] = n
            for i in range(0, 3):
                if minV[i] < minV[i + 1]:
                    minV[i], minV[i + 1] = minV[i + 1], minV[i]
    
    return min(maxV[i] - minV[3 - i] for i in range(4))

sort the array and compute the minimum over the three pair difference.

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
4
5
6
7
def minDifference(self, nums: List[int]) -> int:
    if len(nums) <= 4: return 0
    nums.sort()
    return min(nums[-1] - nums[3], 
               nums[-2] - nums[2], 
               nums[-3] - nums[1], 
               nums[-4] - nums[0])
1004. Max Consecutive Ones III

Use a pointer to memorize the starting index of the candidate subarray. If we run out of k, we move the pointer until it’s pointing to zero, and then increment by 1 to skip this zero and include the zero at the end index.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
def longestOnes(self, nums: List[int], k: int) -> int:
    n, ans, l = len(nums), 0, 0
    for r in range(n):
        if nums[r] == 0:                       # try to pick current 0
            if k == 0:                         # if window already picked k zeros, pop 1 from left and pick this
                while nums[l] != 0 : 
                    l += 1
                l += 1
            else: 
                k-= 1                       # otherwise pick it and decrement k
        ans = max(ans, r - l + 1)              # update ans as max window size till now
    return ans
977. Squares of a Sorted Array

Fill in the output array backwards. Use two pointers, if the abs value of number at right pointer is greater, then set the variable and reduce right pointer.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sortedSquares(self, nums: List[int]) -> List[int]:
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) < abs(nums[right]):
            square = nums[right]
            right -= 1
        else:
            square = nums[left]
            left += 1
        result[i] = square * square
    return result
896. Monotonic Array

Use two boolean and return if they are both false or not.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
def isMonotonic(self, nums: List[int]) -> bool:
    increasing = decreasing = True

    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            increasing = False
        if nums[i] < nums[i+1]:
            decreasing = False

    return increasing or decreasing
138. Copy List with Random Pointer

Instead of a separate dictionary to keep the old node --> new node mapping, we can tweak the original linked list and keep every cloned node next to its original node. This interleaving of old and new nodes allows us to solve this problem without any extra space.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
        return head

    ptr = head
    while ptr:
        # Cloned node
        new_node = Node(ptr.val, None, None)

        # Inserting the cloned node just next to the original node.
        # If A->B->C is the original linked list,
        # Linked list after weaving cloned nodes would be A->A'->B->B'->C->C'
        new_node.next = ptr.next
        ptr.next = new_node
        ptr = new_node.next

    ptr = head

    # Now link the random pointers of the new nodes created.
    # Iterate the newly created list and use the original nodes random pointers,
    # to assign references to random pointers for cloned nodes.
    while ptr:
        ptr.next.random = ptr.random.next if ptr.random else None
        ptr = ptr.next.next

    # Unweave the linked list to get back the original linked list and the cloned list.
    # i.e. A->A'->B->B'->C->C' would be broken to A->B->C and A'->B'->C'
    ptr_old_list = head # A->B->C
    ptr_new_list = head.next # A'->B'->C'
    head_new = head.next
    while ptr_old_list:
        ptr_old_list.next = ptr_old_list.next.next
        ptr_new_list.next = ptr_new_list.next.next if ptr_new_list.next else None
        ptr_old_list = ptr_old_list.next
        ptr_new_list = ptr_new_list.next
    return head_new

Using dict.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    cache = {}
    new_ptr = dummy = Node(-1)
    
    while head:
        if head in cache: 
            newnode = cache[head]
        else:
            newnode = Node(head.val)
            cache[head] = newnode
        new_ptr.next = newnode
        new_ptr = new_ptr.next
        if head.random:    
            if head.random in cache: 
                new_random = cache[head.random]
            else:
                new_random = Node(head.random.val)
                cache[head.random] = new_random
            new_ptr.random = new_random
        head = head.next
    return dummy.next
339. Nested List Weight Sum

DFS.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def depthSum(self, nestedList: List[NestedInteger]) -> int:
    def helper(l, dep):
        if not l:
            return
        for a in l:
            if not a.isInteger():
                helper(a.getList(), dep+1)
            else:
                self.depth += a.getInteger() * dep
    
    self.depth = 0
    helper(nestedList, 1)
    return self.depth

BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def depthSum(self, nestedList: List[NestedInteger]) -> int:
    queue = deque(nestedList)

    depth = 1
    total = 0

    while len(queue) > 0:
        for i in range(len(queue)):
            nested = queue.pop()
            if nested.isInteger():
                total += nested.getInteger() * depth
            else:
                queue.extendleft(nested.getList())
        depth += 1

    return total
148. Sort List

https://leetcode.com/problems/sort-list/discuss/46711/Python-easy-to-understand-merge-sort-solution

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
     if not head or not head.next:
         return head
     fast, slow = head.next, head
     while fast and fast.next:
         fast = fast.next.next
         slow = slow.next
     start = slow.next
     slow.next = None
     l, r = self.sortList(head), self.sortList(start)
     return self.merge(l, r)
     
     
 def merge(self, l, r):
     if not l or not r:
         return l or r
     if l.val > r.val:
         l, r = r, l
     # get the return node "head"
     head = pre = l
     l = l.next
     while l and r:
         if l.val < r.val:
             pre.next = l
             l = l.next
         else:
             pre.next = r
             r = r.next
         pre = pre.next
     # l and r at least one is None
     pre.next = l or r
     return head

No recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    def getsize(head):
        c = 0
        while head:
            head = head.next
            c += 1
        return c
    
    def split(head, size):
        tail = head
        for _ in range(size-1):
            if not tail:
                return None
            tail = tail.next
            
        if not tail: return None
        next_head, tail.next = tail.next, None
        
        return next_head
    
    def merge(l1, l2, newtail):
        while l1 and l2:
            if l1.val <= l2.val:
                newtail.next = l1
                l1 = l1.next
            else:
                newtail.next = l2
                l2 = l2.next
            newtail = newtail.next
            
        newtail.next = l1 or l2
        while newtail.next:
            newtail = newtail.next
            
        return newtail
    
    length = getsize(head)
    newhead = ListNode(next=head)
    size = 1
    
    while size < length:
        newtail, cur = newhead, newhead.next
        while cur:
            h1 = cur
            h2 = split(h1, size)
            cur = split(h2, size)
            newtail = merge(h1, h2, newtail)
        size *= 2
    
    return newhead.next
19. Remove Nth Node From End of List

One pass. The first pointer advances the list by n+1n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by nn nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the nnth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node’s next next node.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    fast = slow = head
    for _ in range(n):
        fast = fast.next
    if not fast:
        return head.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head

Two pass. First time calculate the length. Second time reduce the count till 0, and remove that node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    ans = ListNode(0)
    ans.next = head
    ptr = head
    count = 0
    while ptr:
        count += 1
        ptr = ptr.next
    
    count -= n
    ptr = ans
    while count > 0:
        count -= 1
        ptr = ptr.next
    ptr.next = ptr.next.next
    return ans.next
83. Remove Duplicates from Sorted List

Recursion. Set the next element to be the function call. Return head.next if it is the same as head, otherwise return head.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head and head.next:
        head.next = self.deleteDuplicates(head.next)
        if head.next.val == head.val:
            return head.next
        else:
            return head
    return head

Iterative. Remember to put moving head in the else statement.

1
2
3
4
5
6
7
8
9
10
11
12
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    
    cur = head
    while cur and cur.next:
        if cur.val == cur.next.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
        
    return head
234. Palindrome Linked List

Recursion. If we iterate the nodes in reverse using recursion, and iterate forward at the same time using a variable outside the recursive function, then we can check whether or not we have a palindrome.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def isPalindrome(self, head: Optional[ListNode]) -> bool:
    self.front_ptr = head
    
    def recursive_check(node):
        if node:
            if not recursive_check(node.next):
                return False
            if self.front_ptr.val != node.val:
                return False
            self.front_ptr = self.front_ptr.next
        return True
    
    return recursive_check(head)

Copy into Array List and then Use Two Pointer Technique.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
def isPalindrome(self, head: Optional[ListNode]) -> bool:
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals == vals[::-1]
160. Intersection of Two Linked Lists

If we say that cc is the shared part, aa is exclusive part of list A and bb is exclusive part of list B, then we can have one pointer that goes over a + c + b and the other that goes over b + c + a. Have a look at the diagram below, and this should be fairly intuitive.

Run time: $O(m+n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    p1, p2 = headA, headB
    while p1 != p2:
        if not p1:
            p1 = headB
        else:
            p1 = p1.next
            
        if not p2:
            p2 = headA
        else:
            p2 = p2.next
    return p1

Use set to put all nodes in B. Then loop through A once and see if a node is already in the set.

Run time: $O(m+n)$, space: $O(m)$

1
2
3
4
5
6
7
8
9
10
11
12
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    s = set()
    while headB:
        s.add(headB)
        headB = headB.next

    while headA:
        if headA in s:
            return headA
        headA = headA.next
        
    return None

Brute force. For each node in A, loop through B and see if two nodes are the same.

Run time: $O(mn)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    while headA:
        p = headB
        while p:
            if headA == p:
                return headA
            p = p.next
        headA = headA.next
    return None
24. Swap Nodes in Pairs

Recursive. In every function call we take out two nodes which would be swapped and the remaining nodes are passed to the next recursive call. The reason we are adopting a recursive approach here is because a sub-list of the original list would still be a linked list and hence, it would adapt to our recursive strategy.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head and head.next:
        temp = head.next
        head.next = self.swapPairs(temp.next)
        temp.next = head
        return temp
    return head

Iterative. We break the linked list into pairs by jumping in steps of two. The only difference is, unlike recursion, we swap the nodes on the go. After swapping a pair of nodes, say A and B, we need to link the node B to the node that was right before A. To establish this linkage we save the previous node of node A in prevNode.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    
    ans = ListNode(0)
    ans.next = head
    ptr = ans
    
    while head and head.next:
        first = head
        second = head.next
        
        ptr.next = second
        first.next = second.next
        second.next = first
        
        ptr = first
        head = first.next
    return ans.next
21. Merge Two Sorted Lists

Iterative.

Run time: $O(m+n)$, space: $O(m+n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    ans = ListNode(0)
    ptr = ans
    while list1 and list2:
        if list1.val < list2.val:
            ans.next = list1
            list1 = list1.next
        else: # list1 > list2
            ans.next = list2
            list2 = list2.next
        ans = ans.next
    ans.next = list1 or list2
    return ptr.next

Recursion. We can recursively define the result of a merge operation on two lists as the following (avoiding the corner case logic surrounding empty lists):

1
2
3
4
5
6
7
8
9
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if not list1 or not list2:
        return list1 or list2
    if list1.val < list2.val:
        list1.next = self.mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2
206. Reverse Linked List > Iterative solution. Use one variable prev and one called curr that points to head. While curr is not None, use another variable to store the next node, set the next node of curr to be prev, set prev to be curr, in the end set curr to be the temp variable.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev, curr = None, head
    while curr:
        temp_next = curr.next
        curr.next = prev
        prev = curr
        curr = temp_next
    return prev

The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n1 → … → nk-1 → nk → nk+1 → … → nm → Ø
Assume from node nk+1 to nm had been reversed and you are at node nk.whilifans.list
n1 → … → nk-1 → nk → nk+1 ← … ← nm
We want nk+1’s next node to point to nk.
So, nk.next.next = nk;
Be very careful that n1’s next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    
    temp_next = self.reverseList(head.next)
    head.next.next = head
    head.next = None
    return temp_next
304. Range Sum Query 2D - Immutable

Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        if not matrix: return 
        m, n = len(matrix), len(matrix[0])
        dp = self.dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] + matrix[i][j] - dp[i][j]
                       
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        dp = self.dp
        return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1]

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
303. Range Sum Query - Immutable

Store the cumulative sum. Return (right+1)-left.

1
2
3
4
5
6
7
8
9
10
class NumArray:

    def __init__(self, nums: List[int]):
        self.cum_sum = [0]*(len(nums)+1)
        self.cum_sum[0] = nums[0]
        for i in range(len(nums)):
            self.cum_sum[i+1] = nums[i]+self.cum_sum[i]
        print(self.cum_sum)
    def sumRange(self, left: int, right: int) -> int:
        return self.cum_sum[right+1] - self.cum_sum[left]
560. Subarray Sum Equals K > Create a dict to store . In the loop, find if cumulative sum - k is in the dict, then add the value to the count.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def subarraySum(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    count = 0
    sums = 0 # cumulative sum
    d = dict()
    d[0] = 1
    
    for i in range(len(nums)):
        sums += nums[i]
        count += d.get(sums-k,0)
        d[sums] = d.get(sums,0) + 1
    
    return(count)
1570. Dot Product of Two Sparse Vectors > Store the index and nonzero values in a dictionary, and check if the keys in another dict is in this dict as well, the compute the product.

Run time: $O(n)$, space: $O(L)$, where $L$ is the number of nonzero values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class SparseVector:
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.d = {}
        for i, num in enumerate(nums):
            self.d[i] = num
        

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec):
        """
        :type vec: 'SparseVector'
        :rtype: int
        """
        ans = 0
        for i, num in self.d.items():
            if i in vec.d:
                ans += vec.d[i] * num
        return ans
        

# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

Stack, Queue

>

Run time: $O()$, space: $O()$

1

1296. Divide Array in Sets of K Consecutive Numbers

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/discuss/470238/JavaC%2B%2BPython-Exactly-Same-as-846.-Hand-of-Straights

Run time: $O(kn\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
    c = collections.Counter(nums)
    for i in sorted(c):
        if c[i] > 0:
            for j in range(k)[::-1]:
                c[i + j] -= c[i]
                if c[i + j] < 0:
                    return False
    return True
1
2
3
4
5
6
7
8
9
10
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
    c = collections.Counter(nums)
    start = collections.deque()
    last_checked, opened = -1, 0
    for i in sorted(c):
        if opened > c[i] or opened > 0 and i > last_checked + 1: return False
        start.append(c[i] - opened)
        last_checked, opened = i, c[i]
        if len(start) == k: opened -= start.popleft()
    return opened == 0
150. Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/discuss/47444/Python-easy-to-understand-solution

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def evalRPN(self, tokens: List[str]) -> int:
    stack = []
    for t in tokens:
        if t not in "+-*/":
            stack.append(int(t))
        else:
            r, l = stack.pop(), stack.pop()
            if t == "+":
                stack.append(l+r)
            elif t == "-":
                stack.append(l-r)
            elif t == "*":
                stack.append(l*r)
            else:
                stack.append(int(float(l)/r))
    return stack.pop()
1209. Remove All Adjacent Duplicates in String II

See 1047 for same idea. Store <char, occurrences> to stack. Increment occurrences if we see it again, and if occurrences equals k, we pop it from stack.
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/discuss/392933/JavaC%2B%2BPython-Two-Pointers-and-Stack-Solution

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def removeDuplicates(self, s: str, k: int) -> str:
    stack = [['#', 0]]
    for c in s:
        if stack[-1][0] == c:
            stack[-1][1] += 1
            if stack[-1][1] == k:
                stack.pop()
        else:
            stack.append([c, 1])
    return ''.join(c * k for c, k in stack)
239. Sliding Window Maximum

Monotonic decreasing queue.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    ans = []
    desc_q = collections.deque()
    
    for i, num in enumerate(nums):
        # pop out-of-bound index
        if i >= k and desc_q[0] == i-k:
            desc_q.popleft()
        # pop index where elements are smaller than current num
        while desc_q and nums[desc_q[-1]] < num:
            desc_q.pop()
            
        desc_q.append(i)
        if i >= k-1:
            ans.append(nums[desc_q[0]])
    return ans

Use max heap (i.e. a min heap that stores <-num, index>). Each time we need to pop the element if the current top element index exceeds the k bound.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    ans = []
    pq = []
    for i, num in enumerate(nums):
        while pq and i >= k and pq[0][1] <= i-k:
            heapq.heappop(pq)
        heapq.heappush(pq, (-num, i))
        if i >= k-1:
            ans.append(-pq[0][0])
    return ans
1499. Max Value of Equation

Monotonic decreasing queue that stores <y-x, x> in descending order. Pop elements that does not satisfy the |x-xj| <= k restriction, i.e., xj >= x-k, then update the max. Then, pop elements that has y-x smaller than or equal to the current y-x, since we are not going to use them.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
    q = collections.deque()
    ans = -float('inf')
    for x, y in points:
        while q and q[0][1] < x - k:
            q.popleft()
        if q: ans = max(ans, q[0][0] + y + x)
        while q and q[-1][0] <= y - x:
            q.pop()
        q.append([y - x, x])
    return ans

Use max heap (in python, create heap and store the negative value) to store y-x for each point. While the x value of current point in the max heap has difference greater than k, we pop it from the heap. Then we get the sum of current x+y, and the y-x from the heap.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
    q = [] # max heap that stores <negative of y-x, x>
    ans = -float('inf')
    for x, y in points:
        while q and x - q[0][1] > k:
            heapq.heappop(q)
        if q:
            ans = max(ans, -q[0][0] + (x+y))
        heapq.heappush(q, (-(y-x), x))
    return ans
394. Decode String

Use one variable to keep track of number and string. If we see [, we add string and num to stack and reset them. If we see ], we poll num and string and update string. If we see a digit, we update num. Otherwise, we append char to string.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def decodeString(self, s: str) -> str:
    stack = []
    num = 0
    string = ""
    
    for c in s:
        if c == '[':
            stack.append(string)
            stack.append(num)
            string = ""
            num = 0
        elif c == ']':
            oldNum = stack.pop()
            oldString = stack.pop()
            string = oldString + oldNum * string
        elif c.isdigit():
            num = num * 10 + int(c)
        else:
            string += c
    return string
1047. Remove All Adjacent Duplicates In String

Current string character is equal to the last element in stack? Pop that last element out of stack.
Current string character is not equal to the last element in stack? Add the current character into stack.

Run time: $O(n)$, space: $O(n-d)$, where $d$ is the number of dup char.

1
2
3
4
5
6
7
8
def removeDuplicates(self, s: str) -> str:
    stack = []
    for ch in s:
        if stack and ch == stack[-1]:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)
716. Max Stack

Create a stack and put [value, current index of the max].

Run time: $O(n)$ for popMax, $O(1)$ for all other calls, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MaxStack:

    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        if self.stack and x >= self.stack[self.stack[-1][1]][0]:
            i = len(self.stack)  # index of max
        else:
            if self.stack:
                i = self.stack[-1][1]
            else: 
                i = 0
        self.stack.append((x, i))

    def pop(self) -> int:
        return self.stack.pop()[0]

    def top(self) -> int:
        return self.stack[-1][0]

    def peekMax(self) -> int:
        return self.stack[self.stack[-1][1]][0]

    def popMax(self) -> int:
        index = self.stack[-1][1]  # index where the max exists
        result = self.stack[index][0]  # max value to return
        if index > 0:
            new_max = self.stack[self.stack[index-1][1]][0]
        else:
            new_max = -float('inf')
        # Scan the stack starting at 'index' to recompute the max values and shift all
        # values to the left by one:
        for i in range(index, len(self.stack)-1):
            if self.stack[i+1][0] >= new_max:
                new_max = self.stack[i+1][0]
                self.stack[i] = (self.stack[i+1][0], i)
            else:
                self.stack[i] = (self.stack[i+1][0], self.stack[i-1][1])
        self.stack.pop()
        return result
772. Basic Calculator III

It is much easier to implement the solution if you build the BNF grammar.
inspired by https://leetcode.com/problems/build-binary-expression-tree-from-infix-expression/discuss/864596/Python-Standard-parser-implementation

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def calculate(self, s: str) -> int:
    def parse_factor(dq):
        if dq[0].isdigit():
            curr = 0
            while dq and dq[0].isdigit():
                curr = curr * 10 + int(dq[0])
                dq.popleft()
            return curr
        else:
            dq.popleft()
            tmp = parse_expr(dq)
            dq.popleft()
            return tmp

        
    def parse_term(dq):
        lhs = parse_factor(dq)
        while dq and dq[0] in "*/":
            op = dq.popleft()
            rhs = parse_factor(dq)
            if op == '*':
                lhs = lhs * rhs 
            else: 
                lhs = int(lhs/rhs) # for this case "(0-3)/4"
        return lhs
        
    def parse_expr(dq):
        lhs = parse_term(dq)
        while dq and dq[0] in ['+', '-']:
            op = dq.popleft()
            rhs = parse_term(dq)
            lhs = lhs + rhs if op == '+' else lhs - rhs
        return lhs
    
    dq = deque(list(s))
    return parse_expr(dq)

Recursion. https://leetcode.com/problems/basic-calculator-iii/discuss/371346/Python-recursive-solution

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def calculate(self, s: str) -> int:
    def getSubExpr(s):
        left = 1
        x = []
        while left != 0:
            x.append(next(s))
            if x[-1] == '(':
                left += 1
            elif x[-1] == ')':
                left -= 1
        # print(x[:-1])
        return ''.join(x[:-1])

    s = iter(re.findall('\d+|\S', s))
    operand, sign = 0, 1
    total = 0
    for token in s:
        # print(token, operand, sign, total)
        if token in '+-':
            total += sign * operand
            sign = [1, -1][token == '-']
        elif token in '/*':
            n = next(s)
            n = self.calculate(getSubExpr(s)) if n == '(' else int(n)
            operand = operand*n if token == '*' else operand/n
        else:
            operand = self.calculate(getSubExpr(s)) if token == '(' else int(token)
    return int(total + sign * operand)
503. Next Greater Element II

This approach makes use of a stack. This stack stores the indices of the appropriate elements from numsnums array. The top of the stack refers to the index of the Next Greater Element found so far. We store the indices instead of the elements since there could be duplicates in the numsnums array. The description of the method will make the above statement clearer.

We start traversing the numsnums array from right towards the left. For an element nums[i] encountered, we pop all the elements stack[top]stack[top] from the stack such that num[stack[top]] ≤ nums[i]. We continue the popping till we encounter a stack[top] satisfying nums[stack[top]]>nums[i]. Now, it is obvious that the current stack[top] only can act as the Next Greater Element for nums[i](right now, considering only the elements lying to the right of nums[i]).

If no element remains on the top of the stack, it means no larger element than nums[i]nums[i] exists to its right. Along with this, we also push the index of the element just encountered(nums[i]), i.e. ii over the top of the stack, so that nums[i](or stack[top]) now acts as the Next Greater Element for the elements lying to its left.

We go through two such passes over the complete nums array. This is done so as to complete a circular traversal over the nums array. The first pass could make some wrong entries in the res array since it considers only the elements lying to the right of nums[i], without a circular traversal. But, these entries are corrected in the second pass.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def nextGreaterElements(self, nums: List[int]) -> List[int]:
    stack, r = [], [-1] * len(nums)
    for i in range(len(nums)):
        while stack and (nums[stack[-1]] < nums[i]):
            r[stack.pop()] = nums[i]
        stack.append(i)
        
    for i in range(len(nums)):
        while stack and (nums[stack[-1]] < nums[i]):
            r[stack.pop()] = nums[i]
        if stack == []:
            break
    return r
739. Daily Temperatures

At each index currDay, check if the current day is the hottest one seen so far. If it is, update hottest and move on. Otherwise, do the following:

  • Initialize a variable days = 1 because the next warmer day must be at least one day in the future.
  • While temperatures[currDay + days] <= temperatures[currDay]:
  • Add answer[currDay + days] to days. This effectively jumps directly to the next warmer day.
  • Set answer[currDay] = days.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    hot = 0
    ans = [0] * n
    for curr_day in range(n-1,-1,-1):
        temp = temperatures[curr_day]
        if temp >= hot:
            hot = temp
            continue
        
        days = 1
        while temperatures[curr_day+days] <= temp:
            days += ans[curr_day+days]
        
        ans[curr_day] = days
    return ans

If the stack is not empty, that means there are previous days for which we have not yet seen a warmer day.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    ans = [0] * n
    stack = []
    for day, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_day = stack.pop()
            ans[prev_day] = day - prev_day
        stack.append(day)
    return ans
20. Valid Parentheses

Pop the last element from the stack only if stack is not empty and the last element matches in the pair. In the end, check if stack is empty or not.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isValid(self, s: str) -> bool:
    stack = []
    if len(s) == 1:
        return False
    
    for c in s:
        if stack and c==']' and stack[-1]=='[':
            stack.pop()
        elif stack and c=='}' and stack[-1]=='{':
            stack.pop()
        elif stack and c==')' and stack[-1]=='(':
            stack.pop()
        else:
            stack.append(c)
    return len(stack)==0
155. Min Stack > Create a list. Keep track of current element, and the min element so far. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val,val))
            return
        min_val = self.stack[-1][-1]
        self.stack.append((val,min(val, min_val)))
    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

two list, one normal list, one containing min element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.min_stack[-1] == self.stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]
227. Basic Calculator II 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def calculate(self, s):
    """
    :type s: str
    :rtype: int
    """
    num, stack, sign = 0, [], "+"
    for i in range(len(s)):
        if s[i].isdigit():
            num = num * 10 + int(s[i])
        if s[i] in "+-*/" or i == len(s) - 1:
            if sign == "+":
                stack.append(num)
            elif sign == "-":
                stack.append(-num)
            elif sign == "*":
                stack.append(stack.pop()*num)
            else:
                stack.append(int(stack.pop()/num))
            num = 0
            sign = s[i]
    return sum(stack)

Stack. Use helper function update to append the operation result.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def calculate(self, s):
    """
    :type s: str
    :rtype: int
    """
    def calc(it):
        def update(op, v):
            if op == "+": stack.append(v)
            if op == "-": stack.append(-v)
            if op == "*": stack.append(stack.pop() * v)
            if op == "/": stack.append(int(stack.pop() / v))
    
        num, stack, sign = 0, [], "+"
        
        while it < len(s):
            if s[it].isdigit():
                num = num * 10 + int(s[it])
            elif s[it] in "+-*/":
                update(sign, num)
                num, sign = 0, s[it]
            elif s[it] == "(":
                num, j = calc(it + 1)
                it = j - 1
            elif s[it] == ")":
                update(sign, num)
                return sum(stack), it + 1
            it += 1
        update(sign, num)
        return sum(stack)

    return calc(0)
my approach 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def calculate(self, s):
    """
    :type s: str
    :rtype: int
    """
    stack = []
    for i in range(len(s)):
        a = s[i]
        if a in "+-*/":
            stack.append(a)
        elif a.isnumeric():
            j = i+1
            while j < len(s) and s[j].isnumeric():
                j += 1
            a = int(s[i:j])
            
            if len(stack) > 1 and stack[-1] in "*/":
                op = stack.pop()
                num = stack.pop()
                if op == '*':
                    num *= a
                elif op == '/':
                    num /= a
                stack.append(num)
            else:
                stack.append(a)
            
    
    while len(stack) > 2:
        num2 = stack.pop()
        op = stack.pop()
        num1 = stack.pop()
        if op == '+':
            num1 += num2
        elif op == '-':
            num1 -= num2
        stack.append(num1)
    return stack.pop()
71. Simplify Path > First split the string by `/` and remove `.` and empty string, then create a stack to append each element, or pop from the nonempty stack if we see `..`.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def simplifyPath(self, path):
    """
    :type path: str
    :rtype: str
    """
    places = [p for p in path.split("/") if p!="." and p!=""]
    stack = []
    
    for p in places:
        if p == "..":
            if len(stack) > 0:
                stack.pop()
        else:
            stack.append(p)
    return "/" + "/".join(stack)
735. Asteroid Collision > Put every positive asteroid to a stack, if the next one is negative, compare if the absolute value is greater, then pop the top element since it will be collapsed. Keep doing this until stack is empty.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def asteroidCollision(self, asteroids):
    """
    :type asteroids: List[int]
    :rtype: List[int]
    """
    ans = []
    for a in asteroids:
        while ans and a < 0 < ans[-1]: # opposite direction
            if ans[-1] < -a: # new asteroid is greater than existing one
                ans.pop()
                continue
            elif ans[-1] == -a:
                ans.pop()
            break
        else:
            ans.append(a)
    return ans
1762. Buildings With an Ocean View > Check from right to left and record the max height.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
def findBuildings(self, heights: List[int]) -> List[int]:
    res = collections.deque([len(heights) - 1])
    for i in range(len(heights) - 2, -1, -1):
        if heights[i] > heights[res[0]]:
            res.appendleft(i)
    return res
my implementation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findBuildings(self, heights):
    """
    :type heights: List[int]
    :rtype: List[int]
    """
    if len(heights) == 1:
        return [heights[0]]

    curr_max = heights[-1]
    ans = [len(heights)-1]
    for i in range(len(heights)-1, -1, -1):
        curr_h = heights[i]
        if curr_h > curr_max:
            ans.append(i)
            curr_max = curr_h
    return ans[::-1]

2 Pointers

>

Run time: $O()$, space: $O()$

1

11. Container With Most Water

Keep track of min height and max area, keep updating left or right pointer if it is the smaller one.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxArea(self, height: List[int]) -> int:
    res = 0
    l, r = 0, len(height) - 1
    
    while l < r:
        h = min(height[l], height[r])
        res = max(res,  h * (r - l))
        if height[l] == h:
            l += 1
        if height[r] == h:
            r -= 1
            
    return res

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/610144/Py-Detailed-Easy-Sol%3A-Explaination-Thinking-Approach-Commented

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
  def longestSubarray(self, nums: List[int], limit: int) -> int:
      if not nums:
          return 0
      if len(nums) == 1:
          return 1
      # left and right index for tracing out current subarray
      l = 0
      r = 1
      # number out of this may only create problem
      cur_mx = nums[0]
      cur_mn = nums[0]
      # atleast max_l = 1, bcoz [8] = 8-8 = 0 <= limit
      max_l = 1
      # since, it is like sliding window ques,
      # use while loop with left, right index
# with for loop it will be complicated
      while l <= r and r < len(nums):
          cur_mx = max(cur_mx, nums[r])
          cur_mn = min(cur_mn, nums[r])

          if cur_mx - cur_mn <= limit:
              max_l = max(max_l, r - l + 1)
          else:
              if nums[l] == cur_mx:
                  # need to update cur_mx
                  cur_mx = max(nums[l + 1:r + 1])  # inclusive r
              # using if & not elif bcoz- nums[l] == cur_mn == cur_mx
              if nums[l] == cur_mn:
                  # need to update cur_mn
                  cur_mn = min(nums[l + 1:r + 1])
              l += 1
          r += 1
      return max_l
986. Interval List Intersections

https://leetcode.com/problems/interval-list-intersections/discuss/1594033/Python-two-pointers-approach-explained

Run time: $O(m+n)$, space: $O(m+n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
    i, j, ans = 0, 0, []
    
    while i < len(firstList) and j < len(secondList):
        curr = [max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])]
        if curr[0] <= curr[1]:
            ans.append(curr)
        if firstList[i][1] <= secondList[j][1]:
            i += 1
        else:
            j += 1

    return ans
1574. Shortest Subarray to be Removed to Make Array Sorted

https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/discuss/830699/Python-Two-Pointers-Approach-with-Explanation

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
    n = len(arr)
    s, e = 0, n-1
    while s+1<n and arr[s]<=arr[s+1]:
        s += 1
    if s == n-1:
        return 0
    while e-1>=0 and arr[e-1]<=arr[e]:
        e-=1
    if e==0:
        return n-1
    result = min(n-1-s,e)
    
    i, j = 0, e
    while i<=s and j<n:
        if arr[i]<=arr[j]:
            result = min(result,j-i-1)  # j- i -1 will be the length we want to delete
            i+=1
        else:
            j+=1
    return result
777. Swap Adjacent in LR String

https://leetcode.com/problems/swap-adjacent-in-lr-string/discuss/217070/Python-using-corresponding-position-

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def canTransform(self, start: str, end: str) -> bool:
    if len(start) != len(end): return False
    
    A = [(s, idx) for idx, s in enumerate(start) if s == 'L' or s == 'R']
    B = [(e, idx) for idx, e in enumerate(end) if e == 'L' or e == 'R']
    if len(A) != len(B): return False
    
    for (s, i), (e, j) in zip(A, B):
        if s != e: return False
        if s == 'L':
            if i < j:
                return False
        if s == 'R':
            if i > j:
                return False
        
    return True
632. Smallest Range Covering Elements from K Lists

Create a heap that stores <first element, index of array, index of upper bound element, default 0> for all arrays. Initialize the right pointer as the max of first elements in all arrays. As long as the priority queue is not empty, we pop the min element, and update the range if the new range is smaller. If the index of upper bound element reaches the end, we just return the current stored bound. Since we have popped one element from pq, we need to put the next element in the same array back, and we also need to update the upper bound.
https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/104904/Python-Heap-based-solution

Run time: $O(n\log n)$, space: $O(k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def smallestRange(self, nums: List[List[int]]) -> List[int]:
    pq = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(pq)
    
    ans = -float('inf'), float('inf')
    right = max(row[0] for row in nums) # min possible element 
    while pq:
        left, i, j = heapq.heappop(pq)
        if right - left < ans[1] - ans[0]: # smaller bound
            ans = left, right
        if j == len(nums[i])-1: # reach the end of an array
            return ans
        v = nums[i][j+1] # next number in the array
        right = max(right, v) # update upper bound
        heapq.heappush(pq, (v, i, j+1)) # put new number to pq
    
    return ans
1423. Maximum Points You Can Obtain from Cards

Since the sum of k choices are consecutive, we could find the sum of first k elements, then add last element from right, and remove last element from previous sum, keep doing until we get the sum of last k elements. During this process we could get the max sum.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
def maxScore(self, cardPoints: List[int], k: int) -> int:
    s = sum(cardPoints[:k])
    ans = s
    for i in range(1, k+1):
        s += cardPoints[-i] - cardPoints[k-i]
        ans = max(ans, s)
    return ans
1610. Maximum Number of Visible Points

Helper function that find the angle given location and point. First, include points that are the same as location. Then create a list that contains all angles and sort it, then extend it by adding 360 for each element. Sliding window: as long as the right pointer is valid and the angle difference between left and right is valid, move right pointer. Then update the max points. Next, as long as the left pointer is smaller than the right, and the angle difference between left and right is not valid, move left pointer to the right.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
    def angle_from_location(point):
        dx = point[0] - location[0]
        dy = point[1] - location[1]
        alpha = math.atan2(dy, dx) * (180 / math.pi) # artan
        if alpha >= 0:
            return alpha
        return alpha + 360
    
    # remove pts that are same as location
    n = len(points)
    pts = [p for p in points if p != location]
    if not pts:
        return n
    same_loc = n - len(pts)
    
    # Sort the angles in ascending order, and extend by adding 360
    angles = sorted((angle_from_location(pt) for pt in pts))
    angles += [a+360 for a in angles]
    
    max_pts = 0
    i,j = 0,0
    while j < len(angles):
        while j < len(angles) and angles[j] - angles[i] <= angle:
            j += 1
        max_pts = max(max_pts, j-i)
        while j < len(angles) and i < j and angles[j] - angles[i] > angle:
            i += 1
    return same_loc + max_pts
125. Valid Palindrome

two pointers.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isPalindrome(self, s: str) -> bool:
    i, j = 0, len(s) - 1
    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1
        if s[i].lower() != s[j].lower():
            return False

        i += 1
        j -= 1

    return True

Copy updated string to another variable and reverse.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
def isPalindrome(self, s: str) -> bool:
    string = ""
    for c in s:
        if c.isalnum():
            string += c.lower()
    return string == string[::-1]
202. Happy Number

Floyd’s Cycle-Finding Algorithm
Regardless of where the tortoise and hare start in the cycle, they are guaranteed to eventually meet. This is because the hare moves one node closer to the tortoise (in their direction of movement) each step.

Instead of keeping track of just one value in the chain, we keep track of 2, called the slow runner and the fast runner. At each step of the algorithm, the slow runner goes forward by 1 number in the chain, and the fast runner goes forward by 2 numbers (nested calls to the getNext(n) function).

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isHappy(self, n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum

    slow_runner = n
    fast_runner = get_next(n)
    while fast_runner != 1 and slow_runner != fast_runner:
        slow_runner = get_next(slow_runner)
        fast_runner = get_next(get_next(fast_runner))
    return fast_runner == 1

Helper function that find the next number, keep calling this until the number is in the set or it equals 1.
Run time: $O(\log n)$, space: $O(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isHappy(self, n: int) -> bool:
    if n == 1:
        return True
    s = set()
    while n not in s:
        s.add(n)
        temp_sum = 0
        while n > 0:
            temp_sum += (n % 10)**2
            n //= 10
        if temp_sum == 1:
            return True
        n = temp_sum
        
    return False
31. Next Permutation > First find the point where the descending sub-array starts, and then find the last ascending position, swap them, and swap the elements from the start descending position to the end.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def nextPermutation(self, nums):
    """
    :type nums: List[int]
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    i = len(nums)-1
    while i > 0 and nums[i-1] >= nums[i]:
        i -= 1
    if i == 0:
        nums.reverse()
        return
    
    # find the last ascending position
    i, j = i-1, len(nums)-1
    while nums[j] <= nums[i]:
        j -= 1

    # reverse
    nums[i], nums[j] = nums[j], nums[i]
    l = i+1
    r = len(nums)-1
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l, r = l+1, r-1
680. Valid Palindrome II > Use 2 pointers to walk through the string, if not match, then check if removing either start or end character might be palindrome. Then update the pointers.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def validPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    def isPalindrome(s):
        return s == s[::-1]

    start, end = 0, len(s)-1
    while start < end:
        if s[start] != s[end]:
            op_1 = s[start+1:end+1] # remove start
            op_2 = s[start:end] # remove end
            return isPalindrome(op_1) or isPalindrome(op_2)
        start += 1
        end -= 1
    return True

Hash & Heap

>

Run time: $O()$, space: $O()$

1

336. Palindrome Pairs

https://leetcode.com/problems/palindrome-pairs/discuss/79209/Accepted-Python-Solution-With-Explanation

Run time: $O(n * w^2)$, space: $O(n)$, being length of the list, w being the average word length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def palindromePairs(self, words: List[str]) -> List[List[int]]:
    def is_palindrome(check):
        return check == check[::-1]

    words = {word: i for i, word in enumerate(words)}
    valid_pals = []
    for word, k in words.items():
        n = len(word)
        for j in range(n+1):
            pref = word[:j]
            suf = word[j:]
            if is_palindrome(pref):
                back = suf[::-1]
                if back != word and back in words:
                    valid_pals.append([words[back],  k])
            if j != n and is_palindrome(suf):
                back = pref[::-1]
                if back != word and back in words:
                    valid_pals.append([k, words[back]])
    return valid_pals
745. Prefix and Suffix Search

store apple=apple in the list, then concatenate all words using space. When finding a word using given prefix and suffix, search for suffix=prefix, and return the index-1 to exclude the equal sign.
https://leetcode.com/problems/prefix-and-suffix-search/discuss/483341/Short-Python

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
class WordFilter:
    def __init__(self, words):        
        self.magic = []
        for word in reversed(words):
            self.magic.append(word+'='+word) 
        self.magic = ' '.join(self.magic)
    
    def f(self, prefix, suffix):
        return self.magic.count('=', self.magic.find(suffix+'='+prefix))-1

Store all possible start and end combinations to the dictionary. Use # to separate the prefix and suffix.

Run time: $O(n^2)$, space: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class WordFilter:

    def __init__(self, words: List[str]):
        self.dic = {}
        for weight, word in enumerate(words):
            for i in range(len(word)+1):
                for j in range(len(word)+1):
                    self.dic[word[:i]+"#"+word[j:]] = weight

    def f(self, prefix: str, suffix: str) -> int:
        return self.dic.get(prefix+'#'+suffix, -1)


# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)
659. Split Array into Consecutive Subsequences

Use one dictionary to count each number’s occurrences, and use one dictionary to count the number of valid subsequence ending at certain number. For each number, first decrement its occurrence if any, then check if there exists a valid sequence ending at n-1 already, if so, just decrement that sequence’s occurrence and put the new number in. Otherwise, check if there are two more numbers that could form a new subsequence, if so, decrement the other two numbers’ occurrences and add the ending number of the dictionary. Other than these two cases, we have to return False.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isPossible(self, nums: List[int]) -> bool:
    left = collections.Counter(nums)
    end = collections.Counter()
    for n in nums:
        if left[n] == 0:
            continue
        left[n] -= 1
        
        if end[n-1] > 0: # there is already a valid subsequence
            end[n-1] -= 1
            end[n] += 1
        elif left[n+1] and left[n+2]: # it could form a valid subsequence with unvisited elements
            left[n+1] -= 1
            left[n+2] -= 1
            end[n+2] += 1
        else:
            return False
    return True
299. Bulls and Cows

Use two dictionary to keep track of unmatched chars. After one loop, check for each key in original string, get the min of two occurrences.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getHint(self, secret: str, guess: str) -> str:
    s,g = defaultdict(int), defaultdict(int)
    match,occurred = 0,0
    for i in range(len(guess)):
        if secret[i] == guess[i]:
            match += 1
        else:
            s[secret[i]] += 1
            g[guess[i]] += 1
    
    for k in s.keys():
        if k in g:
            occurred += min(s[k], g[k])
    return f"{match}A{occurred}B"
2034. Stock Price Fluctuation

https://leetcode.com/problems/stock-price-fluctuation/discuss/1513293/Python-Clean-2-Heaps-Commented-Code

Run time: $O(\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class StockPrice:

    def __init__(self):
        self.timestamps = {}
        self.latestTimestamp = 0
        self.minHeap = []
        self.maxHeap = []

    def update(self, timestamp: int, price: int) -> None:
        #Keep track of current prices
        self.timestamps[timestamp] = price
        self.latestTimestamp = max(self.latestTimestamp, timestamp)
        
		#For maximum/minimum
        heappush(self.minHeap, (price, timestamp))
        heappush(self.maxHeap, (-price, timestamp))

    def current(self) -> int:
        return self.timestamps[self.latestTimestamp]

    def maximum(self) -> int:
        currPrice, timestamp = heapq.heappop(self.maxHeap)
		
		#If the price from the heap doesn't match the price the timestamp indicates, keep popping from the heap
        while -currPrice != self.timestamps[timestamp]:
            currPrice, timestamp = heapq.heappop(self.maxHeap)
            
        heapq.heappush(self.maxHeap, (currPrice, timestamp))
        return -currPrice

    def minimum(self) -> int:
        currPrice, timestamp = heapq.heappop(self.minHeap)
		
		#If the price from the heap doesn't match the price the timestamp indicates, keep popping from the heap
        while currPrice != self.timestamps[timestamp]:
            currPrice, timestamp = heapq.heappop(self.minHeap)
            
        heapq.heappush(self.minHeap, (currPrice, timestamp))
        return currPrice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from sortedcontainers import SortedDict
class StockPrice:

    def __init__(self):
        self.time_to_prices = SortedDict() # <timestamp, price>
        self.rec = SortedDict() # <price, set of timestamps>

    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.time_to_prices:
            prev_price = self.time_to_prices[timestamp]
            self.rec[prev_price].remove(timestamp)
            if len(self.rec[prev_price]) == 0:
                self.rec.pop(prev_price)
        if not price in self.rec:
            self.rec[price] = set()
            
        self.rec[price].add(timestamp)
        self.time_to_prices[timestamp] = price

    def current(self) -> int:
        return self.time_to_prices.peekitem(-1)[1]

    def maximum(self) -> int:
        return self.rec.peekitem(-1)[0]

    def minimum(self) -> int:
        return self.rec.peekitem(0)[0]


# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()
981. Time Based Key-Value Store

Maintain two dictionary that store <key, timestamp> and <key, value>. Get the index of the asked timestamp and then use it to retrieve value.

Run time: $O(\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class TimeMap:

    def __init__(self):
        self.times = collections.defaultdict(list)
        self.values = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        i = bisect.bisect(self.times[key], timestamp)
        return self.values[key][i - 1] if i else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class TimeMap:

    def __init__(self):
        self.dic = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dic[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        arr = self.dic[key]
        n = len(arr)
        
        left = 0
        right = n
        
        while left < right:
            mid = (left + right) // 2
            if arr[mid][0] <= timestamp:
                left = mid + 1
            elif arr[mid][0] > timestamp:
                right = mid
        
        return "" if right == 0 else arr[right - 1][1]
2013. Detect Squares

First find the diagonal point, and then get the count of the other two points.
https://www.youtube.com/watch?v=bahebearrDc

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class DetectSquares:

    def __init__(self):
        self.pts = defaultdict(int)
        self.pts_list = []
    def add(self, point: List[int]) -> None:
        self.pts[tuple(point)] += 1
        self.pts_list.append(point)
        
    def count(self, point: List[int]) -> int:
        count = 0
        x1,y1 = point[0], point[1]
        for x2, y2 in self.pts_list:
            if abs(x2-x1) != abs(y2-y1) or x1 == x2 or y1 == y2:
                continue
            count += self.pts[(x1, y2)] * self.pts[(x2, y1)]
        return count


# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)
954. Array of Doubled Pairs

Count the frequencies for each element, then sort it by absolute value. If the occurrence of current number is greater than its double, return False, otherwise subtract the occurrence of current number from its double.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def canReorderDoubled(self, arr: List[int]) -> bool:
    count = Counter(arr)
    for x in sorted(count, key=abs):
        if count[x] > count[2*x]:
            return False
        count[2*x] -= count[x]
    
    return True
1834. Single-Threaded CPU

https://leetcode.com/problems/single-threaded-cpu/discuss/1654840/Fastest-Python-Submission-Code-%2B-Steps

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  def getOrder(self, tasks: List[List[int]]) -> List[int]:
      tasks = sorted([t + [i] for i, t in enumerate(tasks)])
      heap, ans = [], []
      last_enq = 0
#Process Tasks
      for time, pro, idx in tasks:
          while heap and last_enq < time:
              p, i, e = heapq.heappop(heap)
              last_enq = max(e, last_enq) + p
              ans.append(i)
          heapq.heappush(heap, (pro, idx, time))
      #Empty heap
      while heap:
          _, i, _ = heapq.heappop(heap)
          ans.append(i)
      return ans
690. Employee Importance

Put <id, Employee> in a map, then call helper function to add the importance and call recursively.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        def dfs(emp):
            imp = emps[emp].importance            
            for s in emps[emp].subordinates:
                imp += dfs(s)
            return imp
        
        emps= {emp.id: emp for emp in employees}
        return dfs(id)
359. Logger Rate Limiter

Use a dictionary to store <message, most recent logged time>.

Run time: $O(1)$, space: $O(m)$, where $m$ is the number of unique messages.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Logger:

    def __init__(self):
        self.msg_dict = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.msg_dict:
            self.msg_dict[message] = timestamp
            return True
        if timestamp - self.msg_dict[message] >= 10:
            self.msg_dict[message] = timestamp
            return True
        return False


# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)
1146. Snapshot Array

Take individual snap shot when set is called, increment snap id (self.i), when snap is called
This is fast to set & snap but relatively slow when you do an get. Even if it’s binary search, make keys indexable take time.
https://leetcode.com/problems/snapshot-array/discuss/850249/Python-3-or-Three-Methods-or-Explanations

Run time: $O(1)$ and $O(\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class SnapshotArray:

    def __init__(self, length: int):
        self.cache = defaultdict(lambda: OrderedDict())
        self.s = 0

    def set(self, index: int, val: int) -> None:
        self.cache[index][self.s] = val

    def snap(self) -> int:
        self.s += 1
        return self.s-1

    def get(self, index: int, snap_id: int) -> int:
        if index not in self.cache:
            return 0
        else:
            snaps = self.cache[index]
            if snap_id in snaps:
                return snaps[snap_id]
            keys = list(snaps.keys())
            if snap_id > keys[-1]:
                return snaps[keys[-1]]

            ind = bisect.bisect(keys, snap_id)
            if ind == 0:
                return 0
            return snaps[keys[ind-1]]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)
2007. Find Original Array From Doubled Array

Put everything to Counter, and loop through each key. Handle the case when key is zero, and all other cases, first find the smallest number if its half is also in the counter, then append the occurrences to the output, and remove this key and reduce the doubled number occurrences.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def findOriginalArray(self, changed: List[int]) -> List[int]:
    counter = collections.Counter(changed)
    res = []
    for k in counter.keys():
        if k == 0:
            # handle zero as special case
            if counter[k] % 2 != 0: # only one zero
                return []
            res += [0] * (counter[k] // 2)
            
        elif counter[k] > 0:
            x = k
            # walk down the chain
            while x % 2 == 0 and x // 2 in counter:
                x = x // 2
                
            # walk up and process all numbers within the chain. mark the counts as 0
            while x in counter:
                if counter[x] > 0:
                    if counter[x+x] < counter[x]:
                        return []
                    res += [x] * counter[x]
                    counter[x+x] -= counter[x]
                    counter[x] = 0
                x += x
    return res
295. Find Median from Data Stream

The idea is to keep two heaps: one for the top half of our data and another is for down half of our data.
If we have even size 2n, then we will keep two heaps with size n
If we have odd size 2n+1, then we will keep size of the small heap n+1 ans the size of large heap n.
When we have new element num, we always put it to small heap, and then normalize our heaps: remove biggest element from the small heap and put it to the large heap. After this operation we can be sure that we have the property that the largest element in small heap is smaller than smaller elements in large heap.
However after this step if we had n, n elements, we will have n, n+1 elements, so we need to put one element from large heap to small heap.
https://leetcode.com/problems/find-median-from-data-stream/discuss/1330808/Python-2-heaps-solution-explained

Run time: $O(\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MedianFinder:

    def __init__(self):
        self.small, self.large = [], [] 

    def addNum(self, num: int) -> None:
        heappush(self.small, -num)           
        heappush(self.large, -heappop(self.small))
        
        if len(self.small) < len(self.large):
            heappush(self.small, -heappop(self.large))
            
    def findMedian(self) -> float:
        if len(self.large) != len(self.small):
            return -self.small[0]                  
        else:
            return (self.large[0] - self.small[0]) / 2 
        
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
498. Diagonal Traverse

Create a dictionary, and use the sum of indices as key, and list of values as values. Reverse the list and append to output array if the key is odd.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
d = defaultdict(list)
for i in range(len(mat)):
    for j in range(len(mat[0])):
        d[i+j].append(mat[i][j])

ans = []
for k,v in d.items():
    if k % 2 == 0:
        ans += v[::-1]
    else:
        ans += v
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
      d={}
#loop through matrix
      for i in range(len(matrix)):
          for j in range(len(matrix[i])):
		#if no entry in dictionary for sum of indices aka the diagonal, create one
              if i + j not in d:
                  d[i+j] = [matrix[i][j]]
              else:
		#If you've already passed over this diagonal, keep adding elements to it!
                  d[i+j].append(matrix[i][j])
# we're done with the pass, let's build our answer array
      ans= []
#look at the diagonal and each diagonal's elements
      for entry in d.items():
	#each entry looks like (diagonal level (sum of indices), [elem1, elem2, elem3, ...])
	#snake time, look at the diagonal level
          if entry[0] % 2 == 0:
		#Here we append in reverse order because its an even numbered level/diagonal. 
              [ans.append(x) for x in entry[1][::-1]]
          else:
              [ans.append(x) for x in entry[1]]
      return ans
523. Continuous Subarray Sum

Same as Subarray sum equals K with modification. Basic idea is that, If you get the same remainder again, it means that you’ve encountered some sum which is a multiple of K.
why {0:-1}? In the case the sum of the array a multiple of k, we should store {0:-1} so a modulus of two is noted as already existing.

Run time: $O(n)$, space: $O(k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    prefix_sum = 0
    # Dictionary of prefix sums and their indices(0 is seen before the array)
    prefix_sum_indices = {0: -1}
    
    for index, num in enumerate(nums):
        # Compute the remainder when dividing the new sum by k
        prefix_sum = (prefix_sum + num) % k
        
        # Check if this remainder has been encountered before and of length 2
        if prefix_sum in prefix_sum_indices and index - prefix_sum_indices[prefix_sum] > 1:
            return True
        
        # Add this index if it is hasn't been encountered before
        if prefix_sum not in prefix_sum_indices:
            prefix_sum_indices[prefix_sum] = index
    
    return False
249. Group Shifted Strings

Put the difference between each character as key, and the original string as value in the dictionary.

Run time: $O(nk)$, space: $O(nk)$, where $n$ is the length of input strings array, $k$ is the max length of the string in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
def groupStrings(self, strings: List[str]) -> List[List[str]]:
    d = defaultdict(list)
    for s in strings:
        key = []
        for i in range(len(s) - 1):
            # Throw in 26 so that we can normalzie below
            difference = 26 + ord(s[i+1]) - ord(s[i])
            # Wrap around
            # z + 1 = a
            key.append(str(difference % 26))
        d[','.join(key)].append(s)
    
    return d.values()
380. Insert Delete GetRandom O(1) > Use a dictionary and a list to keep track of the inserted elements. Use dictionary to check whether the element exists, and when we need to remove element, we find the index and put the last element in the original position of the list, and update the dictionary. Delete: Retrieve an index of element to delete from the hashmap. Move the last element to the place of the element to delete, \mathcal{O}(1)O(1) time. Pop the last element out, \mathcal{O}(1)O(1) time.

Run time: $O(1)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class RandomizedSet:

    def __init__(self):
        self.d = {}
        self.l = []

    def insert(self, val: int) -> bool:
        if val not in self.d:
            self.d[val] = len(self.l)
            self.l.append(val)
            return True
        return False

    def remove(self, val: int) -> bool:
        if val not in self.d:
            return False
        last_element = self.l[-1]
        idx = self.d[val]
        
        self.l[idx] = last_element # rearrange
        del self.d[val]
        
        return True

    def getRandom(self) -> int:
        return random.choice(self.l)
242. Valid Anagram > Use one or two dictionary to check whether all values are zero in the end, or compare if they are the same.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isAnagram1(self, s, t):
    dic1, dic2 = {}, {}
    for item in s:
        dic1[item] = dic1.get(item, 0) + 1
    for item in t:
        dic2[item] = dic2.get(item, 0) + 1
    return dic1 == dic2
    
def isAnagram2(self, s, t):
    dic1, dic2 = [0]*26, [0]*26
    for item in s:
        dic1[ord(item)-ord('a')] += 1
    for item in t:
        dic2[ord(item)-ord('a')] += 1
    return dic1 == dic2
    
def isAnagram3(self, s, t):
    return sorted(s) == sorted(t)
287. Find the Duplicate Number

Floyd’s Tortoise and Hare (Cycle Detection)
hare = nums[nums[hare]] is twice as fast as tortoise = nums[tortoise]. Since the hare goes fast, it would be the first to enter the cycle and run around the cycle. At some point, the tortoise enters the cycle as well, and since it’s moving slower the hare catches up to the tortoise at some intersection point. Now phase 1 is over, and the tortoise has lost.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findDuplicate(self, nums):
    # Find the intersection point of the two runners.
    tortoise = hare = nums[0]
    while True:
        tortoise = nums[tortoise]
        hare = nums[nums[hare]]
        if tortoise == hare:
            break
    
    # Find the "entrance" to the cycle.
    tortoise = nums[0]
    while tortoise != hare:
        tortoise = nums[tortoise]
        hare = nums[hare]
    
    return hare

Binary search. If the count of the numbers that are smaller than or equal to the mid, update right pointer.

In the binary search approach, instead of doing a linear scan from 1 to n, we can apply a binary search with a goal of finding the smallest number that satisfies the aforementioned property. We start with a search space of [1,n] that has a midpoint midmid. If midmid satisfies the property, we narrow our search space to the left half [1, mid - 1] and continue searching, otherwise, we narrow our search space to the right half [mid + 1, n].

Run time: $O(n\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def findDuplicate(self, nums: List[int]) -> int:
    left, right = 1, len(nums)-1
    while left < right:
        mid = (right + left)//2
        if sum(i <= mid for i in nums) > mid:
            right = mid
        else:
            left = mid+1
    return right

Put every element in a set, if it already exists, return it.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
def findDuplicate(self, nums: List[int]) -> int:
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)
217. Contains Duplicate

Build a set using input array. If every element is distinct, then their length should be equal.

Run time: $O(n)$, space: $O(n)$

1
2
3
def containsDuplicate(self, nums: List[int]) -> bool:
    s = set(nums)
    return len(s) != len(nums)
448. Find All Numbers Disappeared in an Array

Negate the number that is in this index. In the end, if the number is still positive, put the corresponding index+1 to the output array.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    ans = []
    for i in range(len(nums)):
        temp = abs(nums[i])-1
        if nums[temp] > 0:
            nums[temp] *= -1

    for i in range(len(nums)):
        if nums[i] > 0:
            ans.append(i+1)
    return ans

Hashset.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    s = set(nums)
    n = len(nums)
    ans = []
    for i in range(1, n+1):
        if i not in s:
            ans.append(i)
    return ans

Advanced Hash/Heap

>

Run time: $O()$, space: $O()$

1

460. LFU Cache

https://leetcode.com/problems/lfu-cache/discuss/1083490/Python-Solution-using-DefaultDict-and-a-Dict%3A-faster%3A77.45-Memory-usageless-88.00

Run time: $O(\log n)$ for put if key not present, $O(1)$ for other calls, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class LFUCache:
    import collections

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        # cache will contain key:[value, frequency]
        # default dict will contain all the keys having the same frequency of occurrence.
        # {frequency:[key1, key2, key3]}
        self.cache = {}
        self.freqCache = collections.defaultdict(list)

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        val = self.cache.get(key, -1)
        if val == -1: 
            return val
        
        value,freq = val
        # if key is found, increase the frequency in frequency cache and data cache
        self.freqCache[freq].remove(key)
        if not self.freqCache[freq]: 
            del self.freqCache[freq]
        self.freqCache[freq+1].append(key)

        self.cache[key] = [value, freq+1]  
        
        return value
        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if self.capacity <=0:
            return
        val = self.cache.get(key, -1)
        initfreq=1
        
        if  val == -1:
            
            if len(self.cache) == self.capacity:
                #print self.freqCache.items()
                minFreq, delList = min(self.freqCache.items(), key=lambda x:x[0])
                #print delList
                delkey = delList[0]
                del self.cache[delkey]
                self.freqCache[minFreq].remove(delkey)
                
                #insert in cache
                self.cache.update({key:[value,initfreq]})
                self.freqCache[initfreq].append(key)
            else:
                self.cache.update({key:[value,initfreq]})
                self.freqCache[initfreq].append(key)
        else:
            oldval,freq = val
            
            self.freqCache[freq].remove(key)
            if not self.freqCache[freq]: del self.freqCache[freq]
            self.freqCache[freq+1].append(key)
            
            self.cache[key] = [value,freq+1]


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
146. LRU Cache > Use OrderedDict. pop key: d.pop(key). Remove least used key: d.popitem(last=False).

Run time: $O(1)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.d = collections.OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        val = self.d.pop(key)
        self.d[key] = val
        return val

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self.d.pop(key)
        else:
            if self.cap > 0:
                self.cap -= 1
            else:
                self.d.popitem(last=False)
        self.d[key] = value

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Use dictionary + doubly linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Node:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.prev = None
        self.next = None
        
class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.dic = dict()
        self.prev = self.next = self

    def get(self, key: int) -> int:
        if key in self.dic:
            n = self.dic[key]
            self._remove(n)
            self._add(n)
            return n.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            self._remove(self.dic[key])
        n = Node(key, value)
        self._add(n)
        self.dic[key] = n
        if len(self.dic) > self.cap:
            n = self.next
            self._remove(n)
            del self.dic[n.key]
            
    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p

    def _add(self, node):
        p = self.prev
        p.next = node
        self.prev = node
        node.prev = p
        node.next = self

Union Find

>

Run time: $O()$, space: $O()$

1

200. Number of Islands

DFS.
https://leetcode.com/problems/number-of-islands/discuss/583745/Python-3-solutions%3A-DFS-BFS-Union-Find-Concise-and-Clean

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def numIslands(self, grid: List[List[str]]) -> int:
    m, n = len(grid), len(grid[0])
    dirs = [0, 1, 0, -1, 0]
    
    def dfs(r, c):
        if not (0 <= r < m and 0 <= c < n) or grid[r][c] == "0": return 0
        grid[r][c] = "0"  # Mark as visited
        for i in range(4):
            dfs(r + dirs[i], c + dirs[i+1])
        return 1
    
    ans = 0
    for r in range(m):
        for c in range(n):
            ans += dfs(r, c)
    return ans

https://leetcode.com/problems/number-of-islands/discuss/56519/Union-Find-in-Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def numIslands(self, grid: List[List[str]]) -> int:
    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x: int, y: int) -> None:
        xroot = find(x)
        yroot = find(y)
        if xroot == yroot: return 
        if rank[xroot] < rank[yroot]:
            xroot, yroot = yroot, xroot
        parent[yroot] = xroot
        rank[xroot] = max(rank[xroot], rank[yroot]+1)
        self.count -= 1
        
    if len(grid) == 0: 
        return 0
    m, n = len(grid), len(grid[0])
    self.count = sum(grid[i][j]=='1' for i in range(m) for j in range(n))
    parent = [i for i in range(m*n)]
    rank = [0] * m * n

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '0':
                continue
            index = i*n + j
            if j < n-1 and grid[i][j+1] == '1':
                union(index, index+1)
            if i < m-1 and grid[i+1][j] == '1':
                union(index, index+n)
    return self.count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    def numIslands(self, grid: List[List[str]]) -> int:
        DIR = [0, 1, 0, -1, 0]
        m, n = len(grid), len(grid[0])
        uf = UnionFind(m*n)
        
        component = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == "0": continue
                component += 1
                curId = r * n + c
                for i in range(4):
                    nr, nc = r + DIR[i], c + DIR[i+1]
                    if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] == "0": continue
                    neiId = nr * n + nc
                    if uf.union(curId, neiId):
                        component -= 1
        return component

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n
        
    def find(self, u):
        if u != self.parent[u]:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]
    
    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv: return False
        if self.size[pu] < self.size[pv]:  # Merge pu to pv
            self.size[pv] += self.size[pu]
            self.parent[pu] = pv
        else:
            self.size[pu] += self.size[pv]
            self.parent[pv] = pu
        return True

BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def numIslands(self, grid: List[List[str]]) -> int:
    m, n = len(grid), len(grid[0])
    DIR = [0, 1, 0, -1, 0]

    def bfs(r, c):
        if grid[r][c] == "0": return 0
        q = deque([(r, c)])
        while q:
            r, c = q.popleft()
            for i in range(4):
                nr, nc = r + DIR[i], c + DIR[i+1]
                if nr < 0 or nr == m or nc < 0 or nc == n or grid[nr][nc] == "0": continue
                grid[nr][nc] = "0"  # Mark as visited
                q.append([nr, nc])
        return 1

    ans = 0
    for r in range(m):
        for c in range(n):
            ans += bfs(r, c)
    return ans
721. Accounts Merge

Use one map that stores email to id, one map for id to email, one map for email to name.
First for each user, gets their name, then loop through each email, and add <email, name> to the last dict. If this email is not in the email-to-id dict, add <email, id> to it, and put <id, email> to the id-to-email dict. Remember to increment the id for the next user. Then, union the first email with every email including itself.
Next, create a dictionary that stores <id, set of emails>. For each id, find its root, create an entry for its root and add the emails retrieved using current id from id-to-email dictionary.
For the final output, look at all <id, email set> pair, get the name from the email-to-name map using the id-to-email map. Then, get the name, and concatenate with the sorted list of emails.

Run time: $O(SlogS)$, space: $O(S)$, where S is sum of all emails of accounts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UnionFind(10000)
        
        map_email_id = {}
        map_id_email = {}
        map_email_name = {}
        id = 0
        for acc in accounts:
            name = acc[0]
            for email in acc[1:]:
                map_email_name[email] = name
                if email not in map_email_id:
                    map_email_id[email] = id
                    map_id_email[id] = email
                    id += 1
                uf.union(map_email_id[acc[1]], map_email_id[email]) # union 1st email and ith emails -> union emails in same account together
        
        merged_emails = defaultdict(set)
        for _id in range(id):
            merged_emails[uf.find(_id)].add(map_id_email[_id])
            
        ans = []
        for (_id, emails) in merged_emails.items():
            name = map_email_name[map_id_email[_id]]
            ans.append([name] + list(sorted(emails)))
        return ans

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n
        
    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x]) # Path compression
        return self.parent[x]
    
    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv: return False  # Return False if u and v are already union
        if self.size[pu] > self.size[pv]: # Union by larger size
            self.size[pu] += self.size[pv]
            self.parent[pv] = pu
        else:
            self.size[pv] += self.size[pu]
            self.parent[pu] = pv
        return True
803. Bricks Falling When Hit

First initialize the rank and parent to store (-1,-1). The num_child dictionary stores the (x,y) position and the number of children connected to it. The set hits stores each hit to have easier access. First we initialize all 1 positions as nodes, if it is on the first row (connected to the ceiling), then union it with (-1,-1). Otherwise, connect it to its four neighbors if any.
Once this step is complete, we go through each hit in reversed order, if the hit position is empty, append 0 and continue. If the area is 1, we first get the children of (-1,-1), i.e., the number of bricks connected to ceiling. Then we initialize the node in the hit position. If the row is 0, we connect the node with (-1,-1), and connect its four neighbors. Now, we get the number of children of position (-1,-1), and the curr-prev-1 would be the number of falling bricks, as if the hit brick is added, we may be able to connect more bricks to the ceiling, and they would fall when this brick is hit.
https://leetcode.com/problems/bricks-falling-when-hit/discuss/1695192/Python-UF-Template

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        if not grid:
            return []
        
        def union(node1, node2):
            root1 = find(node1)
            root2 = find(node2)
            
            if root1 != root2:
                if rank[root1] > rank[root2]:
                    parent[root2] = root1
                    num_child[root1] += num_child[root2]
                elif rank[root2] > rank[root1]:
                    parent[root1] = root2
                    num_child[root2] += num_child[root1]
                else: # rank[root1] == rank[root2]
                    parent[root2] = root1
                    num_child[root1] += num_child[root2]
                    rank[root1] += 1
        
        def find(node):
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]
        
        def init_node(node):
            parent[node] = node
            num_child[node] = 1
            rank[node] = 1
        
        def connect_neighbors(node):
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                x,y = node[0]+dx, node[1]+dy
                if (x,y) in parent:
                    union(node, (x,y))
        
        m,n = len(grid), len(grid[0])
        # add virtual parent (-1, -1) for all of first row points
        rank = {(-1, -1): m * n}
        parent = {(-1, -1): (-1, -1)}
        num_child = collections.defaultdict(int)
        hits_cache = {(x,y) for [x,y] in hits}

        for row in range(m):
            for col in range(n):
                if (row, col) in hits_cache:
                    continue
                if grid[row][col] == 1:
                    init_node((row, col))
                    if row == 0:
                        union((-1,-1), (row, col))
                    else:
                        connect_neighbors((row, col))
        res = []
        for row, col in hits[::-1]:
            if grid[row][col] != 1:
                res.append(0)
                continue
            pre = num_child[(-1,-1)]
            init_node((row, col))
            if row == 0:
                union((-1,-1), (row, col))
                
            connect_neighbors((row, col))
            cur = num_child[(-1,-1)]
            res.append(max(0, cur-pre-1))
        
        return res[::-1]
827. Making A Large Island

Union Find. First initialize the dictionary for parents and size. Then For each 1 island, explore its down and right neighbors that are 1 and try to union them. For each cell, explore its all four neighbors and if it is 0, find its parent and add to a set. In the end, get the max size for all parents. If there is no zero in the matrix, return max size.

https://leetcode.com/problems/making-a-large-island/discuss/1150779/Python-Union-Find-Solution

Run time: $O(n^2)$, space: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def largestIsland(self, grid: List[List[int]]) -> int:
    N = len(grid)
    
    # union find and size of components
    uf = {
        (r, c): (r, c)
        for r in range(N)
        for c in range(N)
        if grid[r][c]
    }
    
    size = {
        (r, c): 1
        for r in range(N)
        for c in range(N)
        if grid[r][c]
    }
    
    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]
    
    def union(x, y):
        rootx = find(x)
        rooty = find(y)
        if rootx != rooty:
            uf[rootx] = rooty
            size[rooty] += size[rootx]
        
    # union adjacant 1s
    for r in range(N):
        for c in range(N):
            if grid[r][c]:
                for nr, nc in [[r+1, c], [r, c+1]]:
                    if 0 <= nr < N and 0 <= nc < N and grid[nr][nc]:
                        union((r,c), (nr,nc))
    
    # iterate all 0s to find the max area
    max_area = 0
    has_zero = False
    for r in range(N):
        for c in range(N):
            if grid[r][c] == 0:
                has_zero = True
                adj_islands = set()
                for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
                    if 0 <= nr < N and 0 <= nc < N and grid[nr][nc]:
                        adj_islands.add(find((nr, nc)))
                area = 1 + sum(size[adj_island] for adj_island in adj_islands)
                max_area = max(max_area, area)
                
    return max_area if has_zero else N * N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def largestIsland(self, grid: List[List[int]]) -> int:
    DIR = [0, 1, 0, -1, 0]
    m, n, nextColor = len(grid), len(grid[0]), 2
    componentSize = defaultdict(int)

    def paint(r, c, color):
        if r < 0 or r == m or c < 0 or c == n or grid[r][c] != 1: return
        grid[r][c] = color
        componentSize[color] += 1
        for i in range(4):
            paint(r + DIR[i], c + DIR[i + 1], color)

    for r in range(m):
        for c in range(n):
            if grid[r][c] != 1: continue  # Only paint when it's an island cell
            paint(r, c, nextColor)
            nextColor += 1

    ans = max(componentSize.values() or [0])
    for r in range(m):
        for c in range(n):
            if grid[r][c] != 0: continue
            neiColors = set()
            for i in range(4):
                nr, nc = r + DIR[i], c + DIR[i + 1]
                if nr < 0 or nr == m or nc < 0 or nc == n or grid[nr][nc] == 0: continue
                neiColors.add(grid[nr][nc])
            sizeFormed = 1  # Start with 1, which is matrix[r][c] when turning from 0 into 1
            for color in neiColors:
                sizeFormed += componentSize[color]
            ans = max(ans, sizeFormed)

    return ans

DP

>

Run time: $O()$, space: $O()$

1

1235. Maximum Profit in Job Scheduling > If we don't do this job, nothing will be changed. If we do this job, binary search in the dp to find the largest profit we can make before start time s. So we also know the maximum current profit that we can make doing this job. Compare with last element in the dp, we make more money, it worth doing this job, then we add the pair of [e, cur] to the back of dp. Otherwise, we'd like not to do this job.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def jobScheduling(self, startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
    dp = [[0, 0]]
    for s, e, p in jobs:
        i = bisect.bisect(dp, [s + 1]) - 1
        if dp[i][1] + p > dp[-1][1]:
            dp.append([e, dp[i][1] + p])
    return dp[-1][1]
122. Best Time to Buy and Sell Stock II

Since we can buy/sell anytime, we can use a greedy approach.
Just track the sum of profit, add to it whenever the previous day’s price is lower than the current.

Run time: $O(n)$, space: $O(1)$ or $O(n)$

1
2
3
4
5
6
7
8
def maxProfit(self, prices: List[int]) -> int:
    if not prices or len(prices) < 2:
        return 0
    
    profit = 0
    for x in range(1,len(prices)):
        profit += max(0, prices[x]-prices[x-1])
    return profit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxProfit(self, prices: List[int]) -> int:
    if not prices or len(prices) < 2:
        return 0
    
    n = len(prices)
    min_price = prices[0]
    max_price = prices[0]
    dp = [0] * n
    for i in range(1, n):
        min_price = min(min_price, prices[i])
        tentative_profit = prices[i]-min_price
        if tentative_profit > 0:
            dp[i] = tentative_profit
            min_price = prices[i]
            max_price = prices[i] 
    return sum(dp)
10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/discuss/5723/My-DP-approach-in-Python-with-comments-and-unittest

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def isMatch(self, s: str, p: str) -> bool:
    # The DP table and the string s and p use the same indexes i and j, but
    # table[i][j] means the match status between p[:i] and s[:j], i.e.
    # table[0][0] means the match status of two empty strings, and
    # table[1][1] means the match status of p[0] and s[0]. Therefore, when
    # refering to the i-th and the j-th characters of p and s for updating
    # table[i][j], we use p[i - 1] and s[j - 1].

    # Initialize the table with False. The first row is satisfied.
    table = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]

    # Update the corner case of matching two empty strings.
    table[0][0] = True

    # Update the corner case of when s is an empty string but p is not.
    # Since each '*' can eliminate the charter before it, the table is
    # vertically updated by the one before previous. [test_symbol_0]
    for i in range(2, len(p) + 1):
        table[i][0] = table[i - 2][0] and p[i - 1] == '*'

    for i in range(1, len(p) + 1):
        for j in range(1, len(s) + 1):
            if p[i - 1] != "*":
                # Update the table by referring the diagonal element.
                table[i][j] = table[i - 1][j - 1] and \
                              (p[i - 1] == s[j - 1] or p[i - 1] == '.')
            else:
                # Eliminations (referring to the vertical element)
                # Either refer to the one before previous or the previous.
                # I.e. * eliminate the previous or count the previous.
                # [test_symbol_1]
                table[i][j] = table[i - 2][j] or table[i - 1][j]

                # Propagations (referring to the horizontal element)
                # If p's previous one is equal to the current s, with
                # helps of *, the status can be propagated from the left.
                # [test_symbol_2]
                if p[i - 2] == s[j - 1] or p[i - 2] == '.':
                    table[i][j] |= table[i][j - 1]

    return table[-1][-1]
322. Coin Change

Assume dp[i] is the fewest number of coins making up amount i, then for every coin in coins, dp[i] = min(dp[i - coin] + 1).

Run time: $O(mn)$, space: $O(m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [float('inf')] * (amount+1)
    dp[0] = 0
    coins.sort()
    for i in range(1,amount+1):
        temp = [float('inf')]
        for c in coins:
            if i - c < 0:
                break
            temp.append(dp[i-c])
        dp[i] = min(temp)+1

    return dp[amount] if dp[amount] != float('inf') else -1
403. Frog Jump

Use a dictionary dic which maps the position of a stone in stones to the set of stepsizes that can jump onto the stone. We initialize dic = {0:{0}}, meaning that we start with the stone at position 0. Next, we iterate i over range(len(stones)), and check if stones[i] is in dic, if it is, it means that there are previous jumps that land on this stone, and we can continue jumping ahead, in which case we iterate over all val in dic[stones[i]], and for each val, we can continue jumping ahead with three stepsizes (val-1, val, and val+1). Therefore, we add val-1 to dic[stones[i]+val-1], val to dic[stones[i]+val], and val+1 to dic[stones[i]+val+1]. Finally, we check if stones[-1] is in dic, if it is, we return True; Else we return False.

Run time: $O(n^2)$, space: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
def canCross(self, stones: List[int]) -> bool:
    dic = collections.defaultdict(set) # <steps, possible next steps>
    dic[0].add(0)
    for i in range(len(stones)):
        if stones[i] in dic:
            for val in dic[stones[i]]:
                if val > 0:
                    dic[stones[i]+val].add(val)
                if val > 1:
                    dic[stones[i]+val-1].add(val-1)
                dic[stones[i]+val+1].add(val+1)
    return stones[-1] in dic
1406. Stone Game III

dp[i] means, if we ignore before A[i],
what’s the highest score that Alex can win over the Bob？
There are three option for Alice to choose.
Take A[i], win take - dp[i+1]
Take A[i] + A[i+1], win take - dp[i+2]
Take A[i] + A[i+1] + A[i+2], win take - dp[i+3]
dp[i] equals the best outcome of these three solutions.
https://leetcode.com/problems/stone-game-iii/discuss/564260/JavaC%2B%2BPython-DP-O(1)-Space

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def stoneGameIII(self, stoneValue: List[int]) -> str:
    dp = [0] * 4
    for i in range(len(stoneValue)-1, -1, -1):
        dp[i % 4] = -float('inf')
        take = 0
        for k in range(3):
            if i+k < len(stoneValue):
                take += stoneValue[i+k]
                dp[i % 4] = max(dp[i % 4], take - dp[(i+k+1) % 4])
    if dp[0] > 0:
        return "Alice"
    if dp[0] < 0:
        return "Bob"
    return "Tie"

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def stoneGameIII(self, stoneValue: List[int]) -> str:
    n = len(stoneValue)
    dp = [0] * (n+1)
    
    for i in range(n-1, -1, -1):
        k = 0
        take = 0
        dp[i] = -float('inf')
        while k < 3 and i + k < n:
            take += stoneValue[i+k]
            dp[i] = max(dp[i], take - dp[i+k+1])
            k += 1
    if dp[0] > 0:
        return "Alice"
    if dp[0] < 0:
        return "Bob"
    return "Tie"
562. Longest Line of Consecutive One in Matrix

Use a 3D matrix to keep track of the max length in four directions.
https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/discuss/195405/Python3-DP-Solution

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def longestLine(self, mat: List[List[int]]) -> int:
    if not mat or not mat[0]:
        return 0
    m,n = len(mat), len(mat[0])
    dp = [[[0]*4 for __ in range(n)] for _ in range(m)]
    max_len = 0
    
    for row in range(m):
        for col in range(n):
            if mat[row][col] == 1:
                if col-1 >= 0:
                    dp[row][col][0] = dp[row][col-1][0]+1
                else:
                    dp[row][col][0] = 1
                
                if row-1 >= 0:
                    dp[row][col][1] = dp[row-1][col][1]+1
                else:
                    dp[row][col][1] = 1
                
                if row-1 >= 0 and col-1 >= 0:
                    dp[row][col][2] = dp[row-1][col-1][2]+1
                else:
                    dp[row][col][2] = 1
                
                if row-1 >= 0 and col+1 < n:
                    dp[row][col][3] = dp[row-1][col+1][3]+1
                else:
                    dp[row][col][3] = 1
            max_len = max(max_len, dp[row][col][0],
                                 dp[row][col][1],
                                 dp[row][col][2],
                                 dp[row][col][3])
    return max_len
1691. Maximum Height by Stacking Cuboids

Sort items by its three side lengths, then sort all items in descending order. Then keep one array of longest side for each box. For each box, we look at all possible larger boxes and see if its all three sides are smaller, then update the max height to be the longest side plus the max height at index of the larger box. In the end return the max of max height array.

Run time: $O(n^2)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxHeight(self, cuboids: List[List[int]]) -> int:
    Info = []
    for cube in cuboids:
        Info.append(sorted(cube))

    Info.sort(reverse = True)
    max_height = [Info[i][2] for i in range(len(Info))]

    # add boxes from bottom to top (i sits on top of j)
    for i in range(len(Info)):
        for j in range(i):
            if Info[i][0] <= Info[j][0] and \
               Info[i][1] <= Info[j][1] and \
               Info[i][2] <= Info[j][2]:
                max_height[i] = max(max_height[i], 
                                    max_height[j] + Info[i][2]) # assume height is the last dimension

    return max(max_height)
1987. Number of Unique Good Subsequences

We count the number of subsequence that ends with 0 and ends with 1. If we see a 0, we add the sum of the array. If we see a 1, we add the sum of the array and a 1, since itself and form a valid substring later.
https://leetcode.com/problems/number-of-unique-good-subsequences/discuss/1431819/JavaC%2B%2BPython-DP-4-lines-O(N)-Time-O(1)-Space

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
    mod = 10**9 + 7
    dp = [0, 0]
    for c in binary:
        dp[int(c)] = (sum(dp) + int(c)) % mod
        
    if '0' in binary:
        return (sum(dp)+1) % mod
    return sum(dp) % mod
940. Distinct Subsequences II

https://www.jianshu.com/p/02501f516437

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
def distinctSubseqII(self, s: str) -> int:
    dp = [0] * 26
    mod = 10**9+7
    for ss in s:
        dp[ord(ss)-ord('a')] = sum(dp) + 1
    return sum(dp) % mod
727. Minimum Window Subsequence

https://anshika-bhargava0202.medium.com/leetcode-727-minimum-window-subsequence-21c40baff689

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def minWindow(self, S: str, T: str) -> str:
	m,n = len(S), len(T)
	dp = [[0]*(n+1) for _ in range(m+1)]
	for j in range(1, n+1):
		dp[0][j] = sys.maxsize // 2
	
	for i in range(1, m+1):
		for j in range(1, n+1):
			if S[i] == T[j]:
				dp[i][j] = dp[i-1][j-1] + 1
			else:
				dp[i][j] = dp[i-1][j] + 1
	
	min_len = sys.maxsize // 2
	end_pos = -1
	
	for i in range(1, m+1):
		if dp[i][n] < min_len:
			min_len = dp[i][n]
			end_pos = i-1
	if min_len == sys.maxsize // 2:
		return ""
	return S[end_pos-min_len+1: end_pos+1]

42. Trapping Rain Water

https://www.youtube.com/watch?v=StH5vntauyQ

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def trap(self, height: List[int]) -> int:
    if not height:
        return 0
    n = len(height)
    l, r = 0, n-1
    max_l = height[l]
    max_r = height[r]
    ans = 0
    
    while l < r:
        if max_l < max_r:
            ans += max_l - height[l]
            l += 1
            max_l = max(max_l, height[l])
        else:
            ans += max_r - height[r]
            r -= 1
            max_r = max(max_r, height[r])
    return ans

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
def trap(self, height: List[int]) -> int:
    waterLevel = []
    left = 0
    for h in height:
        left = max(left, h) 
        waterLevel += [left] # over-fill it to left max height
    right = 0
    for i, h in reversed(list(enumerate(height))):
        right = max(right, h)
        waterLevel[i] = min(waterLevel[i], right) - h # drain to the right height
    return sum(waterLevel)
664. Strange Printer

Let dp(i, j) be the number of turns needed to print S[i:j+1].Then, when trying to complete the printing of interval [i, k] (with S[i] == S[k]), the job will take the same number of turns as painting [i, k-1]. This is because it is always at least as good to print [i, k] first in one turn rather than separately.
Also, we would need to complete [k+1, j]. So in total, our candidate answer is dp(i, k-1) + dp(k+1, j). Of course, when k == i, our candidate is 1 + dp(i+1, j): we paint S[i] in one turn, then paint the rest in dp(i+1, j) turns.
https://leetcode.com/problems/strange-printer/discuss/106795/Python-Straightforward-DP-with-Explanation

Run time: $O(n^3)$, space: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def strangePrinter(self, s: str) -> int:
    memo = {}
    def dp(i, j):
        if i > j: return 0
        if (i, j) not in memo:
            ans = dp(i+1, j) + 1
            for k in range(i+1, j+1):
                if s[k] == s[i]:
                    ans = min(ans, dp(i, k-1) + dp(k+1, j))
            memo[i, j] = ans
        return memo[i, j]

    return dp(0, len(s) - 1)
1218. Longest Arithmetic Subsequence of Given Difference

Use a dictionary to store <last number, length of subsequence>, return 0 if not found, then add 1.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
def longestSubsequence(self, arr: List[int], difference: int) -> int:
    res = {}
    for a in arr:
        res[a] = res.get(a-difference, 0) + 1
    return max(res.values())
552. Student Attendance Record II

https://leetcode.com/problems/student-attendance-record-ii/discuss/101634/Python-DP-with-explanation

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def checkRecord(self, n: int) -> int:
    """
    i=0, possible =1
    i=1, possible =2 (P,L)
    i=2, possible =4 (PP,PL,LP,LL)
    """
    if n==1:return 3
    if n==0: return 0
    mod=1000000007
    dp=[0 for i in range(n+1)]
    dp[0],dp[1],dp[2]=1,2,4
    for i in range(3,n+1):
        dp[i]=(dp[i-1]+dp[i-2]+dp[i-3] )% mod
    res=dp[n] 
    for i in range(1,n+1):
        res+=dp[i-1]*dp[n -i]%mod
    res=res%mod
    return res
1277. Count Square Submatrices with All Ones

Get the min of the three neighbors, then add value in the current cell.

Run time: $O(mn)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def countSquares(self, matrix: List[List[int]]) -> int:
    if not matrix or len(matrix) == 0:
        return 0
    m,n = len(matrix), len(matrix[0])
    count = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                if i == 0 or j == 0:
                    count += 1
                else:
                    temp = min(matrix[i-1][j-1], 
                                       matrix[i-1][j], 
                                       matrix[i][j-1]) + matrix[i][j]
                    count += temp
                    matrix[i][j] = temp
    return count
1937. Maximum Number of Points with Cost

We traverse current_points left to right and store the maximum possible score that the next row can get, taking into account only the elements with indexes [0, col], then do this reversely.

Run time: $O(mn)$, space: $O(m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def maxPoints(self, points: List[List[int]]) -> int:
    current_points = points[0][:]
    for row in range(1, len(points)):
        max_col_points = -float("inf")
        for col in range(len(current_points)):
            max_col_points = max(max_col_points - 1, current_points[col])
            current_points[col] = max_col_points
            
        max_col_points = -float("inf")
        for col in range(len(current_points)-1, -1, -1):
            max_col_points = max(max_col_points - 1, current_points[col])
            current_points[col] = max_col_points
            
        for col in range(len(current_points)):
            current_points[col] = points[row][col] + current_points[col]
    
    return max(current_points)
140. Word Break II

For any word (denoted as \text{w}w) in the dictionary, if it matches with a prefix of the input string, we then can divide the string into two parts: the word and the postfix, i.e. s = \text{w} + \text{postfix}s=w+postfix.

Run time: $ \mathcal{O}(N^2 + 2 ^ N + W)$, space: $ \mathcal{O}(2^N \cdot N + N^2 + W)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
    memo = {}
    def dfs(s):
        if s in memo:
            return memo[s]
        
        res = []
        for x in wordDict:
            if s.startswith(x):
                if s == x:
                    res += [x]
                else:
                    for y in dfs(s[len(x):]):
                        res += [x + ' ' + y]
        memo[s] = res
        return res
                    
    return dfs(s)

Recursion

Run time: $ \mathcal{O}(N^2 + 2 ^ N + W)$, space: $ \mathcal{O}(2^N \cdot N + N^2 + W)$

1
2
3
4
5
6
7
8
9
10
11
12
def helper(s, string, ans):
    if s == "":
        ans.append(string.strip())
        return
    for i in range(len(s)+1):
        if s[:i] in wordDict:
            temp = string + " "+ s[:i]
            helper(s[i:], temp, ans)

ans = []
helper(s, "", ans)
return ans
53. Maximum Subarray > One variable to keep track of current subarray, one variable to track max subarray.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
def maxSubArray(self, nums: List[int]) -> int:
    current_subarray = max_subarray = nums[0]

    for num in nums[1:]:
        current_subarray = max(num, current_subarray + num)
        max_subarray = max(max_subarray, current_subarray)

    return max_subarray
121. Best Time to Buy and Sell Stock > Keep track of lowest price, and update max profit.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
def maxProfit(self, prices: List[int]) -> int:
    buy = float('inf')
    profit = 0
    
    for p in prices:
        buy = min(buy, p)
        profit = max(profit, p-buy)
    return profit
10. Regular Expression Matching

dp[i][j] represents whether the string s ending at index i could be expressed by string p ending at index j.

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isMatch(self, s: str, p: str) -> bool:
    m,n = len(s), len(p)
    dp = [[False]*(n+1) for _ in range(m+1)]
    dp[0][0] = True
    
    for i in range(1, n+1):
        if p[i-1] == '*':
            dp[0][i] = dp[0][i-2] # same as the char before *
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if p[j-1] == '.': # skip current one
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] != '*': # normal char must match
                dp[i][j] = dp[i-1][j-1] and p[j-1] == s[i-1]
            elif p[j-2] != '.' and p[j-2] != s[i-1]: # ended at *
                dp[i][j] = dp[i][j-2]
            else: # all other cases
                dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i][j-2]
    
    return dp[-1][-1]
416. Partition Equal Subset Sum

We could further optimize Approach 3. We must understand that for any array element ii, we need results of the previous iteration (i-1) only. Hence, we could achieve the same using a one-dimensional array as well.

Run time: $O(mn)$, space: $O(m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def canPartition(self, nums: List[int]) -> bool:
    sum_ = sum(nums)
    if sum_ % 2 != 0:
        return False
    
    half = sum_ // 2
    n = len(nums)
    
    dp = [False]*(sum_+1)
    dp[0] = True
    
    for i in range(1, n+1):
        curr = nums[i-1]
        for j in range(sum_, curr-1, -1):
            dp[j] = dp[j] or dp[j-curr]
    return dp[sum_]

We maintain a 2D array ,dp[n][subSetSum] For an array element ii and sum jj in array nums,

dp[i][j]=true if the sum jj can be formed by array elements in subset nums[0]…nums[i],otherwise dp[i][j]=false

Run time: $O(mn)$, space: $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def canPartition(self, nums: List[int]) -> bool:
    sum_ = sum(nums)
    if sum_ % 2 != 0:
        return False
    
    half = sum_ // 2
    n = len(nums)
    
    dp = [[False]*(sum_+1) for _ in range(n+1)]
    dp[0][0] = True
    
    for i in range(1, n+1):
        curr = nums[i-1]
        for j in range(sum_ + 1):
            if j < curr:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-curr]
    return dp[n][sum_]
300. Longest Increasing Subsequence

Use finary search bisect_left

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lengthOfLIS(self, nums: List[int]) -> int:
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        lo, hi = 0, size
        while lo != hi:
            mid = (lo + hi) // 2
            if tails[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        tails[lo] = x
        size = max(lo + 1, size)
    return size

Double for loop and update max if the inner value is smaller than current value.

Run time: $O(n^2)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
def lengthOfLIS(self, nums: List[int]) -> int:
    n = len(nums)
    dp = [1] * (n+1)
    max_len = 0
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[j]+1, dp[i])
        max_len = max(dp[i], max_len)
    return max_len
139. Word Break

First put list into a set for easier access. Initialize an array of size n+1 and set the first entry to be True. Loop from 1 to n, and loop from 0 to i-1, check if dp[j] is True and the substring between j and i is valid. If so, set this entry of the dp array to be true.

Run time: $O(n^3)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    dp = [False for _ in range(n+1)]
    dp[0] = True

    for i in range(1, n+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]
279. Perfect Squares > To calculate the value of numSquares(n), first we need to calculate all the values before n.

Run time: $O(n\sqrt{n})$ or $O(\frac{\sqrt{n}^{h+1}-1}{\sqrt{n}-1})=O(n^{\frac{h}{2}})$, space: $O(n)$ or $O((\sqrt{n})^h)$, where h is the height of the N-ary tree.

Again, first of all, we prepare a list of square numbers (named square_nums) that are less than the given number n.
We then create a queue variable which would keep all the remainders to enumerate at each level.
In the main loop, we iterate over the queue variable. At each iteration, we check if the remainder is one of the square numbers. If the remainder is not a square number, we subtract it with one of the square numbers to obtain a new remainder and then add the new remainder to the next_queue for the iteration of the next level. We break out of the loop once we encounter a remainder that is of a square number, which also means that we find the solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numSquares(self, n: int) -> int:
        queue = deque([(n, 0)])
        visited = {n}
        while queue:
            curr, step = queue.popleft()
            
            if int(curr ** 0.5) == curr ** 0.5:
                return step + 1
            
            for i in range(int(curr ** 0.5) + 1):
                if curr - (i ** 2) not in visited:
                    queue.append((curr - (i ** 2), step + 1))
                    visited.add(curr - (i ** 2))
1
2
3
4
5
6
7
8
9
def numSquares(self, n: int) -> int:
    dp = [i for i in range(n+1)]
    
    for i in range(3, n+1):
        j = 1
        while j**2 <= i:
            dp[i] = min(dp[i], dp[i-j**2]+1)
            j += 1
    return dp[-1]
221. Maximal Square

Find squares whose bottom right corner is formed by the current cell. If we can modify the input, the space complexity can be further reduced to $O(1)$.

Run time: $O(mn)$, space: $O(mn)$ or $O(n)$ or $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def maximalSquare(self, matrix: List[List[str]]) -> int:
    m, n, ans = len(matrix), len(matrix[0]), 0
    for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):
        if i == m-1 or j == n-1:
            matrix[i][j] = int(matrix[i][j])
            ans = max(ans, matrix[i][j])
        else:
            if matrix[i][j] == '1':
                matrix[i][j] = 1 + min(matrix[i+1][j], matrix[i][j+1], matrix[i+1][j+1])
            else:
                matrix[i][j] = 0
            ans = max(ans, matrix[i][j])
    return ans * ans
1
2
3
4
5
6
7
8
9
10
11
def maximalSquare(self, matrix: List[List[str]]) -> int:
    m, n, ans = len(matrix), len(matrix[0]), 0
    dp = [[0]*(n+1) for i in range(m+1)]
    
    for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):
        if matrix[i][j] == '1':
            dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
        else:
            dp[i][j] = 0
        ans = max(ans, dp[i][j])
    return ans * ans
542. 01 Matrix

Two for loops, one goes from top left to bottom right, one goes from bottom right to top left. In this way we could find the minimum distance over all four directions.

Run time: $O(n^2)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])

    for r in range(m):
        for c in range(n):
            if mat[r][c] > 0:
                top = mat[r - 1][c] if r > 0 else math.inf
                left = mat[r][c - 1] if c > 0 else math.inf
                mat[r][c] = min(top, left) + 1

    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            if mat[r][c] > 0:
                bottom = mat[r + 1][c] if r < m - 1 else math.inf
                right = mat[r][c + 1] if c < n - 1 else math.inf
                mat[r][c] = min(mat[r][c], bottom + 1, right + 1)

    return mat
64. Minimum Path Sum

Instead of using a 2D matrix for dp, we can do the same work using a dp array of the row size, since for making the current entry all we need is the dp entry for the bottom and the right element. Thus, we start by initializing only the last element of the array as the last element of the given matrix. The last entry is the bottom rightmost element of the given matrix.

Run time: $O(n^2)$, space: $O(n^2)$ or $O(n)$ or $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minPathSum(self, grid: List[List[int]]) -> int:
    m,n = len(grid), len(grid[0])
    dp = [0 for _ in range(n)]
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if i == m-1 and j != n-1:
                dp[j] = grid[i][j] + dp[j+1]
            elif j == n-1 and i != m-1:
                dp[j] = grid[i][j] + dp[j]
            elif i != m-1 and j != n-1:
                dp[j] = grid[i][j] + min(dp[j], dp[j+1])
            else:
                dp[j] = grid[i][j]
    return dp[0]
1
2
3
4
5
6
7
8
9
10
11
12
def minPathSum(self, grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    
    for i in range(1, n):
        grid[0][i] += grid[0][i-1]
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[-1][-1]
413. Arithmetic Slices

we only require the element dp[i−1] to determine the value to be entered at dp[i]. Thus, instead of making use of a 1-D array to store the required data, we can simply keep a track of just the last element.

Run time: $O(n)$, space: $O(n)$ or $O(1)$

1
2
3
4
5
6
7
8
9
10
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    dp = 0
    total = 0
    for i in range(2, len(nums)):
        if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
            dp += 1
            total += dp
        else:
            dp = 0
    return total
1
2
3
4
5
6
7
8
9
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    if len(nums) < 3: 
        return 0
    dp = [0 for _ in range(len(nums))]
    for i in range(2, len(nums)):
        if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
            dp[i] = dp[i-1]+1
    
    return sum(dp)
198. House Robber > Either steal this house and the n-2 ones, or not steal this one. We could just use two variables and keep shifting them.

Run time: $O(n)$, space: $O(n)$ or $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
            
    rob_prev_two = 0
    rob_prev_one = nums[0]
    
    # DP table calculations.
    for i in range(1, len(nums)):
        current = max(rob_prev_one, rob_prev_two + nums[i])
        
        # Update the variables
        rob_prev_two = rob_prev_one
        rob_prev_one = current
        
    return rob_prev_one
1
2
3
4
5
6
7
8
def rob(self, nums: List[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    
    ans = [nums[0], max(nums[0], nums[1])]
    for i in range(2, len(nums)):
        ans.append(max(nums[i] + ans[i-2], ans[i-1]))
    return ans[-1]
70. Climbing Stairs > Since the `i`th stairs can be reached either from the `i-1`th stair or `i-2`th stair, so the number of ways is the sum of ways at `i-1`th stair and `i-2`th stair.

Run time: $O(n)$, space: $O(n)$ or $O(1)$

1
2
3
4
5
def climbStairs(self, n: int) -> int:
    a, b = 1, 1
    for i in range(n):
        a, b = b, a + b
    return a
1
2
3
4
5
6
7
8
9
10
11
def climbStairs(self, n: int) -> int:
    if n <= 0:
        return 0
    if n == 1:
        return 1
        
    ans = [1 for _ in range(n+1)]

    for i in range(2, n+1):
        ans[i] = ans[i-1] + ans[i-2]
    return ans[n]
1048. Longest String Chain

Store the word and the length of longest chain in a dictionary. For each word in the sorted list by length, first initialize the length to be 1, then loop through each char and form substring by removing it. If this substring is in the dictionary, update the key of this word, and update the final result.

Run time: $O(n\log n)+O(NSS)$, where word length $S\leq 16$, space: $O(NS)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestStrChain(self, words: List[str]) -> int:
    dp = {}
    result = 1

    for word in sorted(words, key=len):
        dp[word] = 1

        for i in range(len(word)):
            prev = word[:i] + word[i + 1:]

            if prev in dp:
                dp[word] = max(dp[prev] + 1, dp[word])
                result = max(result, dp[word])

    return result

DP coord + connected

DP interval + backpack

Tree

>

Run time: $O()$, space: $O()$

1

>

Run time: $O()$, space: $O()$

1

102. Binary Tree Level Order Traversal

BFS

1
2
3
4
5
6
7
8
9
10
11
def levelOrder4(self, root):
    res, queue = [], [(root, 0)]
    while queue:
        curr, level = queue.pop(0)
        if curr:
            if len(res) < level+1:
                res.append([])
            res[level].append(curr.val)
            queue.append((curr.left, level+1))
            queue.append((curr.right, level+1))
    return res

https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33731/Python-short-recursive-and-iterative-solutions

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def levelOrder1(self, root):
    res = []
    self.dfs(root, 0, res)
    return res
    
def dfs(self, root, level, res):
    if not root:
        return 
    if len(res) < level+1:
        res.append([])
    res[level].append(root.val)
    self.dfs(root.left, level+1, res)
    self.dfs(root.right, level+1, res)
[Recursively delete leave nodes in a multi-tree](https://leetcode.com/discuss/interview-question/1693416/google-onsite-recursively-delete-leave-nodes-in-a-multi-tree)

Did you consider Topological sort kind of solution? i.e. Kahn’s algo?
I think, from a first glance, that you could construct another adj list that shows the parents per node, not the children (that is O(n)).
such list will be something like this:
1:[]
2:[1]
5:[1]
3:[1]
7:[2]
4:[2]
8:[4]
9:[5]

You also save a dict with the number of children each node has. Something like this
1:3
2:2
3:0
4:1
5:1
7:0
8:0
9:0

You construct a queue with all nodes that don’t have parents (i.e. leaves). Those with length zero
Per node you pop from Q, you write its value to answer, but you also make sure to reduce 1 from it from the parents num of children. So if we just handled node 9, that is a leaf, we know that its parent is 5. So we go to 5 and see it has 1 children. We reduce 1, to 0, If the num of children is now zero, we add 5 to the queue…

That way we peal the onion layer by layer, and it’s O(N) for building the special structures, and O(N) in building the answer.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def remove_leaves(self, root):
    nodes_with_the_same_depth = []

    def dfs(node):
        if not node:
            return 0

        current_height = 1
        for child in node.children:
            current_height = max(current_height, dfs(child) + 1)

        if len(nodes_with_the_same_depth) == current_height - 1:
            nodes_with_the_same_depth.append([])
        nodes_with_the_same_depth[current_height-1].append(node.val)

        return current_height

    dfs(root)
    ans = []
    for nodes in nodes_with_the_same_depth:
        ans.extend(nodes)

    return ans

Binary Tree / Divide & Conquer

>

Run time: $O()$, space: $O()$

1

[Print BST leaves in alternate order](https://leetcode.com/discuss/interview-question/615526/Google-or-Phone-or-Print-BST-leaves-in-alternate-order) >

Run time: $O(n)$, space: $O(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def insert_left(node, stack):
      while node:
            stack.append(node)
            node = node.left

def insert_right(node, stack):
      while node:
             stack.append(node)
             node = node.right

stack_left = stack()
stack_right = stack()
insert_left(root, stack_left)
insert_right(root, stack_right)

reverse = False
# not sure about this condition
while stack_left and stack_right:
       if reverse:
             node =stack_right.pop()
             insert_right(node.left)
      else:
            node =stack_left.pop()
            insert_left(node.right)
       if is_leaf(node):
            reverse = not reverse
            print(node.val)
104. Maximum Depth of Binary Tree

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
def maxDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    left = self.maxDepth(root.left)
    right = self.maxDepth(root.right)
    return max(left, right)+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        queue = [root]
        depth = 0
        while queue:
            depth += 1
            for i in range(len(queue)):
                cur_root = queue.pop(0)
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        return depth
652. Find Duplicate Subtrees

Use a map to keep track of the <current node val+left val+right val, <occurrence, current node>>. Then we loop through the values, if occurrence is greater than 1, then we append node to the output array.
https://leetcode.com/problems/find-duplicate-subtrees/discuss/106020/Python-easy-understand-solution

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
    # Concept - We can use a hashmap to store the all the trees and their roots
    # Also advantage of using hashmap is you can easily find for the repeated
    # or duplicate trees
    hashmap = {}
    res = []
    self.solve(root, hashmap)

    # Once the hashmap is built, we can just travserse through the values 
    # and find out the values that are greater than 1 are repeated
    for val, node in hashmap.values():
        if val > 1:
            res.append(node)
    return res

def solve(self, root, hashmap):
    if not root:
        return 'X'
    
    a = self.solve(root.left, hashmap)
    b = self.solve(root.right, hashmap)
    
    # Pre-order tree representation for storing the tree
    temp = str(root.val) + ' ' + a + ' ' + b
    
    # Check if it is already in hashmap
    if temp not in hashmap:
        hashmap[temp] = [1, root]
    
    else:
        hashmap[temp][0] += 1
        
    return temp
572. Subtree of Another Tree

DFS. Recursion.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def dfs(s, t):
        if not s and not t: return True
        if not s or not t: return False
        return s.val == t.val and dfs(s.left, t.left) and dfs(s.right, t.right)

    if not root: 
        return
    if root.val == subRoot.val and dfs(root, subRoot): 
        return True
    return self.isSubtree(root.left, subRoot) or \
           self.isSubtree(root.right, subRoot)

Use queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def dfs(n, t):
        if not n and not t: return True
        if not n or not t: return False
        return n.val == t.val and \
               dfs(n.left, t.left) and \
               dfs(n.right, t.right)

    queue = [root]
    while queue:
        n = queue.pop(0)
        if n.val == subRoot.val and dfs(n, subRoot): 
            return True
        if n.left: 
            queue.append(n.left)
        if n.right: 
            queue.append(n.right)
    return False
111. Minimum Depth of Binary Tree

Recursion, DFS.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
def minDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    if not root.left:
        return self.minDepth(root.right) +1
    if not root.right:
        return self.minDepth(root.left) +1
    return min(self.minDepth(root.right) +1, self.minDepth(root.left) +1)

Iterative, BFS. The first leaf node is the min depth.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def minDepth(self, root: Optional[TreeNode]) -> int:
    visit_queue = deque([(root, 1)])
    while len(visit_queue) != 0:
        # BFS Traversal
        next_visit, cur_depth =visit_queue.popleft()
        if next_visit is None: # empty node or empty tree
            continue
        if next_visit.left is None and next_visit.right is None:
            # reach a leaf node
            # get the minimal depth of binary tree, early return
            return cur_depth
        #append left and right child into visit_queue, increase current depth by 1
        visit_queue.append( (next_visit.left, cur_depth+1) )
        visit_queue.append( (next_visit.right, cur_depth + 1) )

    # depth 0 for empty-tree
    return 0
173. Binary Search Tree Iterator

Push all left nodes to the stack. Once a node is popped from the stack, push its right node back to the stack, and return its value.

Run time: $O(1)$, space: $O(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pushAll(root)

    def next(self) -> int:
        tmpNode = self.stack.pop()
        self.pushAll(tmpNode.right)
        return tmpNode.val

    def hasNext(self) -> bool:
        return self.stack
        
    def pushAll(self, node):
        while node:
            self.stack.append(node)
            node = node.left

Flatten the BST and use a pointer for index.

Run time: $O(1)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.arr = []
        self.ind = -1
        self._inorder(root)
            
    def _inorder(self, root):
        if not root:
            return
        self._inorder(root.left)
        self.arr.append(root.val)
        self._inorder(root.right)
        
    def next(self) -> int:
        if not self.hasNext():
            return None
        self.ind += 1
        return self.arr[self.ind]

    def hasNext(self) -> bool:
        return self.ind+1 < len(self.arr)
199. Binary Tree Right Side View

DFS, Recursion.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    self.ans = []
    
    def helper(node, level):
        if not node:
            return
        if level >= len(self.ans):
            self.ans.append(node.val)

        helper(node.right, level+1)
        helper(node.left, level+1)
    
    helper(root, 0)
    return self.ans

BFS, iterative.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    view = []
    if not root:
        return []
    
    q = collections.deque()
    q.append((root, 0))
    
    while q:
        curr, level = q.popleft()
        if level == 0 or not q or q[0][1] > level:
            view.append(curr.val)
        
        if curr.left:
            q.append((curr.left, level + 1))
        if curr.right:
            q.append((curr.right, level + 1))
    return view
987. Vertical Order Traversal of a Binary Tree

Use defaultdict instead of normal dict to get rid of key not exist case. Put <level, value> as value into the dictionary, use placement as key. In the end sort placement, and sort the level.

Run time: $O(n\log n)$, space: $O()$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
    def helper(placement, level, node, dic):
        if not node:
            return
        dic[placement].append((level, node.val))
        helper(placement-1, level+1, node.left, dic)
        helper(placement+1, level+1, node.right, dic)
        
    dic = defaultdict(list)
    helper(0,0,root,dic)
    res = []
    for i in sorted(dic.keys()):
        temp = []
        for j in sorted(dic[i]):
            temp.append(j[1])
        res.append(temp)
    return res
938. Range Sum of BST

Recursion. Need to check if strictly less than or greater than the range, then call helper function recursively.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
    self.rangeSum = 0
    
    def helper(node, lo, hi):
        if node:
            if lo <= node.val <= hi:
                self.rangeSum += node.val
            if lo < node.val:
                    helper(node.left, lo, hi)
            if node.val < hi:
                helper(node.right, lo, hi)
            
    helper(root, low, high)
    return self.rangeSum

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
    ans = 0
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            if L <= node.val <= R:
                ans += node.val
            if L < node.val:
                stack.append(node.left)
            if node.val < R:
                stack.append(node.right)
    return ans
426. Convert Binary Search Tree to Sorted Doubly Linked List

Recursion

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
    def helper(node):
        """
        Performs standard inorder traversal:
        left -> node -> right
        and links all nodes into DLL
        """
        if node:
            # left
            helper(node.left)
            # node 
            if self.last:
                # link the previous node (last)
                # with the current one (node)
                self.last.right = node
                node.left = self.last
            else:
                # keep the smallest node
                # to close DLL later on
                self.first = node        
            self.last = node
            # right
            helper(node.right)
    
    if not root:
        return None
    
    # the smallest (first) and the largest (last) nodes
    self.first, self.last = None, None
    helper(root)
    # close DLL
    self.last.right = self.first
    self.first.left = self.last
    return self.first
1110. Delete Nodes And Return Forest

DFS.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
      ans = []
      to_delete = set(to_delete)
      
      def helper(node):
          if not node:
              return None
          node.left = helper(node.left)
          node.right = helper(node.right)
	
	# add children of a node that is to be deleted
          if node.val in to_delete:
              if node.left: 
                  ans.append(node.left)
              if node.right:
                  ans.append(node.right)
              return None
          return node
              
      helper(root)
# if root is not to be deleted then add it
      if root.val not in to_delete:
          ans.append(root)
      return ans

BFS.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
    output = []
    to_delete_set = set(to_delete)
    tree_queue = [root]
    
    while tree_queue:
        curr_tree = tree_queue.pop(0)
        if not curr_tree:
            continue
        if curr_tree.val in to_delete_set:
            tree_queue.append(curr_tree.left)
            tree_queue.append(curr_tree.right)
            continue
        
        node_queue = [curr_tree]
        while node_queue:
            curr_node = node_queue.pop(0)
            if not curr_node:
                continue
            if curr_node.left and curr_node.left.val in to_delete_set:
                tree_queue.append(curr_node.left.left)
                tree_queue.append(curr_node.left.right)
                curr_node.left = None
            if curr_node.right and curr_node.right.val in to_delete_set:
                tree_queue.append(curr_node.right.left)
                tree_queue.append(curr_node.right.right)
                curr_node.right = None
                
            node_queue.append(curr_node.left)
            node_queue.append(curr_node.right)
            
        output.append(curr_tree)
    return output
235. Lowest Common Ancestor of a Binary Search Tree

Recursion. Since the input tree is a binary search tree, we can utilize the property and determine the LCA. If both p and q values are smaller or greater than the current node val, we know that the LCA could be further reduced.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root.val < p.val and root.val < q.val:
        return self.lowestCommonAncestor(root.right, p, q)
    elif root.val > p.val and root.val > q.val:
        return self.lowestCommonAncestor(root.left, p, q)
    else:
        return root

Iterative.

1
2
3
4
5
6
7
8
9
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    node = root
    while node:
        if node.val < p.val and node.val < q.val:
            node = node.right
        elif node.val > p.val and node.val > q.val:
            node = node.left
        else:
            return node
637. Average of Levels in Binary Tree > DFS. Create a list of list where the index is the height. If the current node height is greater than or equal to the output array length, then append an empty array. Then access the array at index height and append the value. Use list comprehension to get the average for each list.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
    def getH(node, height):
        if not node:
            return
        if height >= len(self.ans):
            self.ans.append([])
        self.ans[height].append(node.val)
        getH(node.left, height+1)
        getH(node.right, height+1)
        
    self.ans = []
    getH(root, 0)
    return [sum(s)/len(s) for s in self.ans]
450. Delete Node in a BST > There are three possible situations here : - Node is a leaf, and one could delete it straightforward : node = null. - Node is not a leaf and has a right child. Then the node could be replaced by its successor which is somewhere lower in the right subtree. Then one could proceed down recursively to delete the successor. - Node is not a leaf, has no right child and has a left child. That means that its successor is somewhere upper in the tree but we don't want to go back. Let's use the predecessor here which is somewhere lower in the left subtree. The node could be replaced by its predecessor and then one could proceed down recursively to delete the predecessor.

Run time: $O(\log n)$, space: $O(h)$, where $h$ is the tree height, when $h=\log n$, it is a balanced tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    def successor(root):
        root = root.right
        while root.left:
            root = root.left
        return root.val
    
    def predecessor(root):
        root = root.left
        while root.right:
            root = root.right
        return root.val
    
    if not root:
        return root
    if root.val > key:
        root.left = self.deleteNode(root.left, key)
    elif root.val < key:
        root.right = self.deleteNode(root.right, key)
    else:
        if not root.left and not root.right:
            root = None
        elif root.right:
            root.val = successor(root)
            root.right = self.deleteNode(root.right, root.val)
        else:
            root.val = predecessor(root)
            root.left = self.deleteNode(root.left, root.val)
            
    return root

328. Odd Even Linked List

Put the odd nodes in a linked list and the even nodes in another. Then link the evenList to the tail of the oddList.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    d1 = odd = ListNode(0)
    d2 = even = ListNode(0)
    i = 1
    while head:
        if i%2:
            odd.next, odd = head,head
        else:
            even.next, even = head,head
        head = head.next
        i += 1
    odd.next, even.next = d2.next,None
    return d1.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return head
    odd = head
    even = head.next
    evenHead = even
    
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = evenHead
    return head
101. Symmetric Tree

Iterative. Maintain a queue and pop two elements at a time and compare, then append their child nodes pairs to the queue.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    q = [root, root]
    while q:
        n1 = q.pop()
        n2 = q.pop()
        if not n1 and not n2:
            continue
        elif not n1 or not n2:
            return False
        elif n1.val != n2.val:
            return False
        q.append(n1.left)
        q.append(n2.right)
        q.append(n1.right)
        q.append(n2.left)
    return True

Recursion. Use a helper function to check whether the current two nodes have the same value, and check left==right and right==left.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    def helper(n1, n2):
        if not n1 and not n2:
            return True
        elif not n1 or not n2:
            return False

        return n1.val == n2.val and \
               helper(n1.right, n2.left) and \
               helper(n1.left, n2.right)
    
    return helper(root, root)
437. Path Sum III

Use a variable to track the current prefix sum and a hashmap “prefix sum -> how many times was it seen so far”. Parse the input structure and count the requested subarrays/submatrices/tree paths along the way with the help of that hashmap. How to count?
The logic is simple: the current prefix sum is curr_sum, and some elements before the prefix sum was curr_sum - target. All the elements in between sum up to curr_sum - (curr_sum - target) = target.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
    def preorder(node: TreeNode, curr_sum):
        if not node:
            return
        curr_sum += node.val
        if curr_sum == k:
            self.count += 1
        self.count += h[curr_sum-k]
        h[curr_sum] += 1
        preorder(node.left, curr_sum)
        preorder(node.right, curr_sum)
        
    self.count = 0
    k = targetSum
    h = defaultdict(int)
    preorder(root, 0)
    return self.count
1
2
3
4
5
6
7
8
9
10
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
    return self.helper(root, targetSum, [targetSum])

def helper(self, node, origin, targets):
    if not node: return 0
    hit = 0
    for t in targets:
        if not t-node.val: hit += 1                          # count if sum == target
    targets = [t-node.val for t in targets]+[origin]         # update the targets
    return hit+self.helper(node.left, origin, targets)+self.helper(node.right, origin, targets)
543. Diameter of Binary Tree

we know that the longest path in the tree would consist of a node, its longest left branch, and its longest right branch. So, our algorithm to solve this problem will find the node where the sum of its longest left and right branches is maximized. This would hint at us to apply Depth-first search (DFS) to count each node’s branch lengths, because it would allow us to dive deep into the leaves first, and then start counting the edges upwards.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    self.diameter = 0
    def longest(node):
        if not node:
            return 0
        left = longest(node.left)
        right = longest(node.right)
        
        self.diameter = max(self.diameter, left+right)
        return max(left, right)+1
   
    longest(root)
    return self.diameter
110. Balanced Binary Tree

Bottom up. If node is None, return 0. Then check for its left and right child, if any of them returns -1, then it means the subtree is not balanced. Or if the difference is greater than 1, the subtree is also not balanced. In the end return 1 + max of left and right child.

Run time: $O()$, space: $O()$

1
2
3
4
5
6
7
8
9
10
11
def isBalanced(self, root: Optional[TreeNode]) -> bool:
    def check(root):
        if not root:
            return 0
        left  = check(root.left)
        right = check(root.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
        
    return check(root) != -1

if recursive calls before conditional check, then its bottom up. If recursive call after conditional check, its top down.

Run time: $O(n\log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
def isBalanced(self, root: Optional[TreeNode]) -> bool:
    def height(node):
        if not node:
            return -1
        return max(height(node.left), height(node.right))+1
    
    if not root:
        return True
    return abs(height(root.left) - height(root.right)) < 2 \
        and self.isBalanced(root.left) \
        and self.isBalanced(root.right)
236. Lowest Common Ancestor of a Binary Tree > Recursive solution, DFS

Run time: $O(n)$, space: $O(h)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def lowestCommonAncestor(self, root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if not root:
        return None
    if p == root or q == root:
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    elif not left:
        return right
    elif not right:
        return left

Iterative, BFS. Use a stack to keep track of each viewed node, and a parent dict to track a node’s parent. If p and q are not in the parent dict, keep popping from the stack, add to parent dict, and append to stack. Then we create a set called ancestors, keep finding p’s parent. Then find q’s parent until q is in the ancestors, then return q.

Run time: $O(n)$, space: $O(h)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def lowestCommonAncestor(self, root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    stack = [root]
    parent_dict = {root: None}
    while p not in parent_dict or q not in parent_dict:
        node = stack.pop()
        if node.left:
            parent_dict[node.left] = node
            stack.append(node.left)
        if node.right:
            parent_dict[node.right] = node
            stack.append(node.right)
    
    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent_dict[p]
    while q not in ancestors:
        ancestors.add(q)
        q = parent_dict[q]
    return q
1650. Lowest Common Ancestor of a Binary Tree III > Use two pointers to keep track of the parents, until they point to the same node. When either of the pointers points to the root, i.e., parent is None, then set it to the other original node.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
def lowestCommonAncestor(self, p, q):
    """
    :type node: Node
    :rtype: Node
    """
    p1, p2 = p, q
    while p1 != p2:
        p1 =  p1.parent if p1.parent else q
        p2 = p2.parent if p2.parent else p
    return p1
314. Binary Tree Vertical Order Traversal > BFS, obtain the range of the column indices, walk through the column range [min_column, max_column] and retrieve the results accordingly.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import defaultdict
class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []

        columnTable = defaultdict(list)
        min_column = max_column = 0
        queue = deque([(root, 0)])

        while queue:
            node, column = queue.popleft()

            if node is not None:
                columnTable[column].append(node.val)
                min_column = min(min_column, column)
                max_column = max(max_column, column)

                queue.append((node.left, column - 1))
                queue.append((node.right, column + 1))

        return [columnTable[x] for x in range(min_column, max_column + 1)]

BFS, store the current node in the answer, and if left/right child is not None, enqueue.

Run time: $O(n \log n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    
    result = collections.defaultdict(list)
    queue = [(root, 0)]
    
    for node, distance in queue:
        result[distance].append(node.val)
        if node.left:
            queue.append((node.left, distance-1))
        if node.right:
            queue.append((node.right, distance+1))
    
    return [order for distance, order in sorted(result.items())]
my implementation Run time: $O(n)$, space: $O(n)$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        
        def helper(node, level):
            if node is None:
                return
            
            if node.left is not None:
                if level-1 not in d:
                    d[level-1] = []
                d[level-1].append(node.left.val)
            if node.right is not None:
                if level+1 not in d:
                    d[level+1] = []
                d[level+1].append(node.right.val)
            helper(node.left, level-1)
            helper(node.right, level+1)
        
        if root is None:
            return []
        d = {}
        d[0] = [root.val]
        helper(root, 0)
        
        ans = []
        for k in sorted(d):
            ans.append(d[k])
        return ans

Trie

>

Run time: $O()$, space: $O()$

1

208. Implement Trie (Prefix Tree)

Maintain a dictionary and keep adding empty entries if the character does not exist, and update the pointer to the key.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Trie:

    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        curr_d = self.trie
        for c in word:
            if c not in curr_d:
                curr_d[c] = {}
            curr_d = curr_d[c]
        curr_d['-'] = True

    def search(self, word: str) -> bool:
        curr_d = self.trie
        for c in word:
            if c not in curr_d:
                return False
            curr_d = curr_d[c]
        return '-' in curr_d

    def startsWith(self, prefix: str) -> bool:
        curr_d = self.trie
        for c in prefix:
            if c not in curr_d:
                return False
            curr_d = curr_d[c]
        return True

Segment Tree

String

>

Run time: $O()$, space: $O()$

1

859. Buddy Strings > If A.length() != B.length(): no possible swap If A == B, we need swap two same characters. Check is duplicated char in A. In other cases, we find index for A[i] != B[i]. There should be only 2 diffs and it's our one swap.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
def buddyStrings(self, A, B):
    if len(A) != len(B): return False
    if A == B and len(set(A)) < len(A): return True
    dif = [(a, b) for a, b in zip(A, B) if a != b]
    return len(dif) == 2 and dif[0] == dif[1][::-1]
1166. Design File System

https://leetcode.com/problems/design-file-system/discuss/366094/JavaPython-TrieTree-solution

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import defaultdict
class File(object):
    def __init__(self, name):
        self.map = defaultdict(File)
        self.name = name
        self.value = -1
        
class FileSystem(object):

    def __init__(self):
        self.root = File("")

    def create(self, path, value):
        """
        :type path: str
        :type value: int
        :rtype: bool
        """
        array = path.split("/")
        cur = self.root
        for i in range(1, len(array)):
            name = array[i]
            if name not in cur.map:
                if i==len(array)-1:
                    cur.map[name] = File(name)
                else:
                    return False
            cur = cur.map[name]
        
        if cur.value!=-1:
            return False
        cur.value = value
        
        return True
        

    def get(self, path):
        """
        :type path: str
        :rtype: int
        """
        cur = self.root
        array = path.split("/")
        for i in range(1, len(array)):
            name = array[i]
            if name not in cur.map:
                return -1
            cur = cur.map[name]
        return cur.value
        


# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.create(path,value)
# param_2 = obj.get(path)
248. Strobogrammatic Number III

https://leetcode.com/problems/strobogrammatic-number-iii/discuss/201185/python-DFS-solution

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def strobogrammaticInRange(self, low: str, high: str) -> int:
    self.res = 0
    for length in range(len(low), len(high) + 1):
        for d in ['', '1', '8', '0']:
            self.dfs(low, high, length, d)
    return self.res


def dfs(self, low, high, length, path):
    leng = len(path)
    if leng > length: return
    if leng == length:
        if leng != 1 and path[0] == '0':
            return
        elif int(low) <= int(path) <= int(high):
            self.res += 1
        return
    for d in ['00', '69', '96', '88', '11']:
        self.dfs(low, high, length, d[0] + path + d[1])
8. String to Integer (atoi)

https://leetcode.com/problems/string-to-integer-atoi/discuss/4673/60ms-python-solution-OJ-says-this-beats-100-python-submissions

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def myAtoi(self, s: str) -> int:
    MIN_NUM = -2 ** 31
    MAX_NUM = 2 ** 31 - 1
    
    # trim the leading white space first
    s = s.strip()
    sign = 1
    index = 0
    num = 0
    
    if not s:
        return num
    
    if s[0] == '-':
        sign = -1
        index += 1
    elif s[0] == '+':
        index += 1
    
    while index < len(s) and s[index].isdigit():
        curr_digit = ord(s[index]) - ord('0')
        if num > MAX_NUM // 10 or (num == MAX_NUM // 10 and curr_digit > 7): # here we do the check before adding current digit
            if sign == 1:
                return MAX_NUM  
            else:
                return MIN_NUM
        num = num * 10 + curr_digit
        index += 1
    
    num = sign * num
    return num
388. Longest Absolute File Path

Split the input by new line using input.splitlines(), then use lstrip('\t') to remove the new tabs on its left. This would be the directory or file name. If the name contains a dot, then it is a file, and we could update the max length using the current depth plus the length of name. The number of tabs represents the depth of a file. If it is not a file, we put the depth+1 as the key, get the current depth level, add name length and add 1 as the backslash in the file path.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
def lengthLongestPath(self, input: str) -> int:
    maxlen = 0
    pathlen = {0:0}
    for line in input.splitlines():
        name = line.lstrip('\t')
        depth = len(line)-len(name)
        if '.' in name:
            maxlen = max(maxlen, pathlen[depth] + len(name))
        else:
            pathlen[depth+1] = pathlen[depth] + len(name) + 1
    return maxlen
418. Sentence Screen Fitting

Pre-calculation. Not like DP.
https://www.youtube.com/watch?v=kFBbZolQYdI

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
   def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
n = len(sentence)
next_index = [0]*n
times = [0]*n

for i in range(n):
	cur_i = i
	loop = 0
	cur_len = 0
	
	while cur_len + len(sentence[cur_i]) < cols:
		cur_len += len(sentence[cur_i])
		cur_i += 1
		
		if cur_i == n:
			loop += 1
			cur_i = 0
	next_index[i] = cur_i
	times[i] = loop
ans = 0
word_index = 0

for _ in range(rows):
	ans += times[word_index]
	word_index = next_index[word_index]
return ans

https://leetcode.com/problems/sentence-screen-fitting/discuss/1638021/python-solution

Run time: $O(rows)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
    s = ' '.join(sentence) + ' '
    l = len(s)
    count = 0
    
    for _ in range(rows):
        count += cols
        ind = count % l
        if s[ind] == ' ':
            count += 1 # move to next new position
        else:
            while count >= 0 and s[count % l] != ' ':
                count -= 1
            count += 1 # move to next new position
    return count // l
1525. Number of Good Ways to Split a String

Sliding Window. Use one empty dictionary, and one full dictionary containing occurrences. For each char, add it to empty dictionary, and remove it from right dictionary, if the length are the same, increment the final answer.
https://leetcode.com/problems/number-of-good-ways-to-split-a-string/discuss/755264/Python-O(N)-Sliding-Window

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def numSplits(self, s: str) -> int:
    left_count = collections.Counter()
    right_count = collections.Counter(s)
    res = 0
    for c in s:
        left_count[c] += 1
        right_count[c] -= 1
        if right_count[c] == 0:
            del right_count[c]
        
        if len(left_count) == len(right_count):
            res += 1
            
    return res
833. Find And Replace in String

https://leetcode.com/problems/find-and-replace-in-string/discuss/315827/Python-SIMPLE-Forward-O(N)-Solution-(32ms-97)

Run time: $O(m)$, space: $O(n)$, Let N = len(S) and M = len(indexes)

1
2
3
4
5
6
7
8
9
10
11
12
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
    # lookup = {i: (src, tgt) for i, src, tgt in zip(indexes, sources, targets)}
    lookup = dict(zip(indices, zip(sources, targets)))
    i, result = 0, ""
    while i < len(s):
        if i in lookup and s[i:].startswith(lookup[i][0]):
            result += lookup[i][1]
            i += len(lookup[i][0])
        else:
            result += s[i]
            i += 1
    return result
843. Guess the Word

Calculate the occurrences for each character at position i (6 in total). Then sort the list by the sum of the occurrences. For each guess, pop the last word and make a guess, then discard any word that does have the same number of matched characters returned from master.

https://leetcode.com/problems/guess-the-word/discuss/1318789/Careful-explanation-of-two-ideas-that-allow-you-to-solve-this-problem-in-a-few-lines

Run time: $O()$, space: $O()$

1
2
3
4
5
6
7
8
9
def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
    weights = [Counter(word[i] for word in wordlist) for i in range(6)]
    wordlist.sort(key=lambda word: sum(weights[i][c] for i, c in enumerate(word)))
    
    while wordlist:
        word = wordlist.pop()
        matches = master.guess(word)
        wordlist = [candidate for candidate in wordlist
                   if matches == sum(c1 == c2 for c1, c2 in zip(word, candidate))]
791. Custom Sort String >

Run time: $O(\max(m,n))$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  def customSortString(self, order: str, s: str) -> str:
      freq = Counter(s) #O(n) + O(1)
# equivalent:
# freq = {}
      # for ch in s: #O(n) where n is len(s)
      #     freq[ch] = freq.get(ch, 0) + 1

      chars = []
      for ch in order: #O(m) where m is the len(order)
          chars.append(ch*freq.pop(ch, 0)) #O(1)
      
      for key in freq.keys(): #O(k) where k is the size of keys present in s but not in order
          chars.append(key*freq[key]) #O(1)

      return "".join(chars)
766. Toeplitz Matrix

Run time: $O(mn)$, space: $O(1)$

1
2
3
4
5
6
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
    for i in range(len(matrix)-1):
        for j in range(len(matrix[0])-1):
            if matrix[i][j] != matrix[i + 1][j + 1]:
                return False
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
     if not matrix or not matrix[0]:
         return False                
     
     # Create a deque tracking the expected values for the next row
     expected = deque(matrix[0])
     
     # Iterate through all the remaining rows, verifying they align with the
     #   expected row.
     for row_i in range(1, len(matrix)):
         row = matrix[row_i]
         expected.pop()
         expected.appendleft(row[0])
         
# Only check from index 1 and down as we've just added index 0 to expected
         for col_i in range(1, len(row)):
             if row[col_i] != expected[col_i]:
                 return False
     
     # If we've reached here, all diagonals aligned
     return True
953. Verifying an Alien Dictionary

Two cases: 1. prev and curr in correct order but prev length is longer, 2. prev and curr not in order.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 def isAlienSorted(self, words: List[str], order: str) -> bool:
     d = {}
     for i, c in enumerate(order):
         d[c] = i

     for i in range(1, len(words)):
         #flag = 1 here means inner loop is break out due to pre less than cur
#flag = 0 here means inner loop done iteration but two strings length are not equal
         pre, cur, flag = words[i-1], words[i], 0
         for j in range(min(len(pre),len(cur))):
             if d[pre[j]] < d[cur[j]]:
                 flag = 1
                 break
             elif d[pre[j]] > d[cur[j]]:
                 return False
         if not flag and len(pre) > len(cur): 
             return False
     return True
65. Valid Number >

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isNumber(self, s: str) -> bool:
    seen_digit = seen_exponent = seen_dot =  False
    for i, c in enumerate(s):
        if c.isdigit():
            seen_digit = True
        elif c in "+-":
            if i > 0 and s[i - 1] != "e" and s[i - 1] != "E":
                return False
        elif c in "Ee":
            if seen_exponent or not seen_digit:
                return False
            seen_exponent = True
            seen_digit = False
        elif c == ".":
            if seen_dot or seen_exponent:
                return False
            seen_dot = True
        else:
            return False
    
    return seen_digit

Deterministic Finite Automaton (DFA). Initialize the DFA as an array of hash tables. Each hash table’s keys will be a character group, and the values will be the state it should transition to. We can use the indexes of the array to handle state transitions. Set the currentState = 0.
Iterate through the input. For each character, first determine what group it belongs to. Then, check if that group exists in the current state’s hash table. If it does, transition to the next state. Otherwise, return false.
At the end, check if we are currently in a valid end state: 1, 4, or 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def isNumber(self, s):
        # This is the DFA we have designed above
        dfa = [
            {"digit": 1, "sign": 2, "dot": 3},
            {"digit": 1, "dot": 4, "exponent": 5},
            {"digit": 1, "dot": 3},
            {"digit": 4},
            {"digit": 4, "exponent": 5},
            {"sign": 6, "digit": 7},
            {"digit": 7},
            {"digit": 7}
        ]
        
        current_state = 0
        for c in s:
            if c.isdigit():
                group = "digit"
            elif c in ["+", "-"]:
                group = "sign"
            elif c in ["e", "E"]:
                group = "exponent"
            elif c == ".":
                group = "dot"
            else:
                return False

            if group not in dfa[current_state]:
                return False
            
            current_state = dfa[current_state][group]
        
        return current_state in [1, 4, 7]
5. Longest Palindromic Substring

Helper function that gets the start and end indices. Then use max function and set key=lambda x: x[1] - x[0]).

Run time: $O(n)$, space: $O(1)$ or $O(n)$

1
2
3
4
5
6
7
8
9
10
11
def longestPalindrome(self, s: str) -> str:
    def f(i, j):
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return i, j
    
    i = j = 0
    for k in range(len(s)):
        i, j = max((i, j), f(k, k), f(k, k+1), key=lambda x: x[1] - x[0])
    return s[i+1:j] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longestPalindrome(self, s: str) -> str:
    def helper(s, start, end):
        while start >= 0 and end < len(s) and s[start] == s[end]:
            start -= 1
            end += 1
        return s[start+1:end]
    
    if not s:
        return ""
    longest = ""
    for i in range(len(s)):
        curr_substr1 = helper(s, i, i)
        curr_substr2 = helper(s, i, i+1)
        
        if len(curr_substr1) > len(longest):
            longest = curr_substr1
        if len(curr_substr2) > len(longest):
            longest = curr_substr2
    return longest
3. Longest Substring Without Repeating Characters

Sliding window. We use a dictionary to store the character as the key, the last appear index has been seen so far as value. seen[charactor] = index
Move the pointer when you met a repeated character in your window.

Run time: $O(n)$, space: $O(m)$, where $n$ is the length of the input string, $m$ is the number of unique characters of the input.

1
2
3
4
5
6
7
8
9
10
11
12
def lengthOfLongestSubstring(self, s: str) -> int:
    used = {}
    max_length = start = 0
    for i, c in enumerate(s):
        if c in used and start <= used[c]:
            start = used[c] + 1
        else:
            max_length = max(max_length, i - start + 1)

        used[c] = i

    return max_length

Brute force.

Run time: $O(n^2)$, space: $O(min(m,n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lengthOfLongestSubstring(self, s: str) -> int:
    if not s:
        return 0
    count = 1
    i = 0
    while i < len(s):
        seen = set()
        seen.add(s[i])
        j = i+1
        while j < len(s) and s[j] not in seen:
            seen.add(s[j])
            j += 1
        count = max(count, j-i)
        i = j
    return count
647. Palindromic Substrings > There are 2N-1 possible centers for the palindrome: we could have a center at S[0], between S[0] and S[1], at S[1], between S[1] and S[2], at S[2], etc.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def countSubstrings(self, s: str) -> int:
    if not s:
        return 0
    n = len(s)
    count = 0
    for i in range(2*n-1):
        left = i//2
        right = (i+1)//2
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
            count += 1
    return count

Intuitive solution.

Run time: $O(n^2)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def countSubstrings(self, s: str) -> int:
    def helper(s, i):
        if i < 0 or i >= len(s):
            return 0
        count = 1
        left,right = i-1,i+1
        while left >=0 and right < len(s):
            if s[left] == s[right]:
                count += 1
            left, right = left-1, right+1

        if i+1 < len(s) and s[i] == s[i+1]:
            count += 1
            left,right = i-1,i+2
            while left >=0 and right < len(s):
                if s[left] == s[right]:
                    count += 1
                left, right = left-1, right+1
        return count
    
    if not s:
        return 0
    ans = 0
    for i in range(len(s)):
        ans += helper(s, i)
    return ans
415. Add Strings > use `chr()` to convert integer to character. `ord()` converts a charactor to integer.

Run time: $O(max(two strings))$, space: $O(max(two strings))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def addStrings(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    ans = []
    i1, i2 = len(num1)-1, len(num2)-1
    carry = 0
    while i1 >= 0 or i2 >= 0 or carry > 0:
        if i1 >= 0:
            carry += ord(num1[i1]) - ord('0')
            i1 -= 1
        if i2 >= 0:
            carry += ord(num2[i2]) - ord('0')
            i2 -= 1
        ans.append(chr(carry % 10 + ord('0')))
        carry //= 10
    return "".join(ans)[::-1]
My approach 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def addStrings(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    ans = 0
    digit = 0
    i, j = len(num1)-1, len(num2)-1
    while i >= 0 and j >= 0:
        d1 = int(num1[i])
        d2 = int(num2[j])
        temp_sum = d1+d2
        temp = 10**digit * (temp_sum % 10) + 10**(digit+1) *(temp_sum//10)
        ans += temp
        digit += 1
        i, j = i-1, j-1
    
    if i < 0 and j < 0:
        return str(ans)
    elif i < 0:
        ans += (10**digit) * int(num2[:j+1])
    elif j < 0:
        ans += (10**digit) * int(num1[:i+1])
    return str(ans)
68. Text Justification > Use one list for final output, one list for current line, one variable to keep track of current character count. Since the current length also represents the minimum space added between words, if the length of current line, plus current character count, plus current word length exceeds `maxWidth`, then we should not add this word, and need to add more space to make the words on the current line distributed evenly. Therefore, we loop from 0 to `maxWidth-char_count`, which is the number of space to be added on this line, then we take modulo. For example, if there are three words on this line, and we need to add 5 space. We first get 0%(3-1), which is 0. Then we calculate 1%(3-1), which is 1. Then we calculate 2%(3-1), which is 0. Then we calculate 3%(3-1), which is 1. Then we calculate 4%(3-1), which is 0.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def fullJustify(self, words, maxWidth):
    """
    :type words: List[str]
    :type maxWidth: int
    :rtype: List[str]
    """
    ans = []
    cur = []
    char_count = 0
    for w in words:
        if len(cur) + char_count + len(w) > maxWidth:
            for i in range(maxWidth - char_count):
                cur[i % (len(cur)-1 or 1)] += ' '
            ans.append(''.join(cur))
            cur = []
            char_count = 0
        cur += [w]
        char_count += len(w)
    # form last line by join with space and left justify to maxWidth using ljust (python method)
    # that means pad additional spaces to the right to make string length equal to maxWidth
    return ans + [' '.join(cur).ljust(maxWidth)]
68. Text Justification

https://leetcode.com/problems/text-justification/discuss/24891/Concise-python-solution-10-lines.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    result, current_list, num_of_letters = [],[], 0
    # result -> stores final result output
    # current_list -> stores list of words which are traversed but not yet added to result
    # num_of_letters -> stores number of chars corresponding to words in current_list
    
    for word in words:
        
        # total no. of chars in current_list + total no. of chars in current word
        # + total no. of words ~= min. number of spaces between words
        if num_of_letters + len(word) + len(current_list) > maxWidth:
            # size will be used for module "magic" for round robin
            # we use max. 1 because atleast one word would be there and to avoid modulo by 0
            size = max(1, len(current_list)-1)
            
            for i in range(maxWidth-num_of_letters):
                # add space to each word in round robin fashion
                index = i%size
                current_list[index] += ' ' 
            
            # add current line of words to the output
            result.append("".join(current_list))
            current_list, num_of_letters = [], 0
        
        # add current word to the list and add length to char count
        current_list.append(word)
        num_of_letters += len(word)
    
    # form last line by join with space and left justify to maxWidth using ljust (python method)
    # that means pad additional spaces to the right to make string length equal to maxWidth
    result.append(" ".join(current_list).ljust(maxWidth))
    
    return result
408. Valid Word Abbreviation > Use two pointers, one for index in the word, one for the abbr.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def validWordAbbreviation(self, word, abbr):
    """
    :type word: str
    :type abbr: str
    :rtype: bool
    """
    i = j = 0
    while i < len(word) and j < len(abbr):
        if word[i] == abbr[j]:
            i += 1
            j += 1
        elif abbr[j] == "0":
            return False
        elif abbr[j].isdigit():
            k = j+1
            while k < len(abbr) and abbr[k].isdigit():
                k += 1
            i += int(abbr[j:k])
            j = k
        else:
            return False
    return i == len(word) and j == len(abbr)
921. Minimum Add to Make Parentheses Valid > Maintain a count of current ungrouped parentheses, and a count of parentheses needed to be inserted. If we see a (, increment the count, otherwise decrement the count if it is greater than 0, or increment the final count.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minAddToMakeValid(self, s):
    """
    :type s: str
    :rtype: int
    """
    count = 0
    ans = 0
    for c in s:
        if c == '(':
            count += 1
        elif count == 0:
            ans += 1
        else:
            count -= 1
    return ans + count
1249. Minimum Remove to Make Valid Parentheses > Use stack to store "(" only, and when encounter ")" and stack is empty, record this index. If stack is not empy, then pop one "(". In the end union the stack and the list and skip these indices when building the final string.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def minRemoveToMakeValid(self, s):
    """
    :type s: str
    :rtype: str
    """
    def remove_invalid(s, good, bad):
        sb = []
        bal = 0
        for c in s:
            if c == good:
                bal += 1
            if c == bad:
                if bal == 0:
                    continue
                bal -= 1
            sb.append(c)
        return "".join(sb)
    
    
    s = remove_invalid(s, "(", ")")    
    s = remove_invalid(s[::-1], ")", "(")
    return s[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minRemoveToMakeValid(self, s):
    """
    :type s: str
    :rtype: str
    """
    ind_remove = set()
    stack = []
    for i, c in enumerate(s):
        if c not in "()":
            continue
        if c == "(": # add ( to stack
            stack.append(i)
        elif not stack: # ) and stack empty, need to remove
            ind_remove.add(i)
        else: # ) and stack not empty, pop one
            stack.pop()
        
    ind_remove = ind_remove.union(set(stack))
    sb = []
    for i, c in enumerate(s):
        if i not in ind_remove:
            sb.append(c)
    return "".join(sb)

Recursion / Math

>

Run time: $O()$, space: $O()$

1

2128. Remove All Ones With Row and Column Flips

https://leetcode.com/problems/remove-all-ones-with-row-and-column-flips/discuss/1671908/Python-3-or-Math-or-Explanation

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
def removeOnes(self, grid: List[List[int]]) -> bool:
    r1, r1_invert = grid[0], [1-val for val in grid[0]]
    for i in range(1, len(grid)):
        if grid[i] != r1 and grid[i] != r1_invert:
            return False
    return True
593. Valid Square

The idea is to calculate all the distance between each two points, and sort them. In this way, we get 4 edges and 2 diagonals of the square in order. If the 4 edges equal to each other, that means it should be equilateral parallelogram. Finally, we check whether the 2 diagonals equal to each other so as to check if it’s a square.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
    def dist(x,y):
        return math.sqrt(((x[0] - y[0]) ** 2) + ((x[1] - y[1]) ** 2))
    
    if p1==p2==p3==p4:
        return False
    
    lst = [
        dist(p1, p2),
        dist(p1, p3),
        dist(p1, p4),
        dist(p2, p3),
        dist(p3, p4),
        dist(p2, p4)]
    
    lst.sort()
    return lst[0] == lst[1] == lst[2] == lst[3] and lst[4] == lst[5]
273. Integer to English Words

https://leetcode.com/problems/integer-to-english-words/discuss/70632/Recursive-Python

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def numberToWords(self, num: int) -> str:
    to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
       'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
    tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
    thousand = 'Thousand Million Billion'.split()
    
    def word(num, idx=0):
        if num == 0:
            return []
        if num < 20:
            return [to19[num-1]]
        if num < 100:
            return [tens[num//10-2]] + word(num%10)
        if num < 1000:
            return [to19[num//100-1]] + ['Hundred'] + word(num%100)

        p, r = num//1000, num%1000
        if p % 1000 !=0:
            space = [thousand[idx]]
        else:
            space = []
        return  word(p, idx+1) + space + word(r)
    return ' '.join(word(num)) or 'Zero'
670. Maximum Swap

Iterate the list of digits backwards and keep tracking of the max digit, as well as the digit that is smaller than the max.
https://leetcode.com/problems/maximum-swap/discuss/1593049/Python-simple-1-pass-solution

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maximumSwap(self, num: int) -> int:
    digits = list(str(num))
    min_ind, max_ind, max_i = -1, -1, len(digits)-1
    
    for i in range(max_i-1, -1, -1):
        if digits[i] > digits[max_i]:
            max_i = i
        elif digits[i] < digits[max_i]:
            min_ind, max_ind = i, max_i

    if min_ind > -1:
        digits[min_ind], digits[max_ind] = digits[max_ind], digits[min_ind]
        
    return int(''.join(digits))
48. Rotate Image > rotate the image by 90 degrees (clockwise) is equivalent to transpose + reflection.

Run time: $O(mn)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def rotate(self, matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    def transpose(ma):
        n = len(ma)
        for i in range(n):
            for j in range(i+1, n):
                ma[j][i], ma[i][j] = ma[i][j], ma[j][i]
    
    def reflect(ma):
        n = len(ma)
        for i in range(n):
            for j in range(n//2):
                ma[i][j], ma[i][-j-1] = ma[i][-j-1], ma[i][j]

    transpose(matrix)
    reflect(matrix)

Directly rotate. ~ means invert, ~j = -j-1

1
2
3
4
5
6
7
8
9
def rotate(self, matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    n = len(matrix)
    for i in range(n//2):
        for j in range(n - n//2):
            matrix[i][j], matrix[~j][i], matrix[~i][~j], matrix[j][~i] = \
                     matrix[~j][i], matrix[~i][~j], matrix[j][~i], matrix[i][j]
268. Missing Number

Gauss’ Formula. Compute expected sum and actual sum, the difference is the missing number.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
def missingNumber(self, nums: List[int]) -> int:
    n = len(nums)
    expected = n*(n+1) // 2
    actual = sum(nums)
    return expected-actual

Bit Manipulation.
Intuition
We can harness the fact that XOR is its own inverse to find the missing element in linear time.

Algorithm
Because we know that nums contains nn numbers and that it is missing exactly one number on the range [0…n-1][0…n−1], we know that nn definitely replaces the missing number in nums. Therefore, if we initialize an integer to nn and XOR it with every index and value, we will be left with the missing number. Consider the following example (the values have been sorted for intuitive convenience, but need not be):

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
def missingNumber(self, nums: List[int]) -> int:
    missing = len(nums)
    for i, num in enumerate(nums):
        missing ^= i ^ num
    return missing

Initialize a set using the input array. Loop through the length of array + 1, if not in set, return this number.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
def missingNumber(self, nums: List[int]) -> int:
    num_set = set(nums)
    n = len(nums) + 1
    for number in range(n):
        if number not in num_set:
            return number
238. Product of Array Except Self > The output array does not count toward the space complexity. Use original output array to find the cumulative sum from left, then use one variable to keep track of the cumulative sum from right, and multiply it to the output array.

Run time: $O(n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1] * n
    right = 1
    for i in range(1,n): # cumulative sum from left
        ans[i] = ans[i-1]*nums[i-1]
    
    for i in range(n-2,-1,-1): # cumulative sum from right
        right *= nums[i+1]
        ans[i] *= right
        
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    left, right = 1, 1
    ans = [1]*n
    
    for i in range(1,n):
        left *= nums[i-1]
        ans[i] = left
    for i in range(n-2,-1,-1):
        right *= nums[i+1]
        ans[i] *= right

        return ans

One array to track the cumulative sum from left, one array to track the cumulative sum from right. In the end, multiply them together on the same index.

Run time: $O(n)$, space: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    left, right = [1]*n, [1]*n

    for i in range(1, n):
        left[i] = nums[i-1] * left[i-1]
    for i in range(n-2,-1,-1):
        right[i] = nums[i+1] * right[i+1]
    print(left, right)
    for i in range(n):
        left[i] *= right[i]
    return left
67. Add Binary

XOR: ^, AND: &, left-shifted: <<

Run time: $O(m+n)$, space: $O(max(m,n))$

1
2
3
4
5
6
7
def addBinary(self, a: str, b: str) -> str:
    x, y = int(a,2), int(b,2)
    while y:
        ans = x ^ y
        carry = (x & y) << 1
        x, y = ans, carry
    return bin(x)[2:]

two pointers, and one carry

Run time: $O(max(m,n))$, space: $O(max(m,n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def addBinary(self, a: str, b: str) -> str:
    ans = ""
    i,j = len(a)-1, len(b)-1
    carry = 0
    while i>= 0 or j>=0 or carry>0:
        if i>=0:
            carry += int(a[i])
        if j>=0:
            carry += int(b[j])
        if carry == 3:
            ans += "1"
            carry = 1
        elif carry == 2:
            ans += "0"
            carry = 1
        elif carry == 1:
            ans += "1"
            carry = 0
        i,j = i-1,j-1
    return ans[::-1]
69. Sqrt(x)

Newton method. $x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}$, where $f(x) = x^2-a = 0$.

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    a = x
    while a**2 > x:
        a = (a + x/a)//2
    return a

binary search.

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    if x == 0:
        return 0
    lo, hi = 1, x
    while lo <= hi:
        mid = lo + (hi-lo)//2
        sqrt = x // mid
        if sqrt == mid:
            return mid
        elif sqrt < mid:
            hi = mid-1
        else:
            lo = mid +1
    return hi
50. Pow(x, n)

First check if power is 0, and check if power is negative. If so, flip the sign of the power and return the reciprocal. Then calculate the half of the power, and if the original power is odd, multiply by one more x.

Run time: $O(\log n)$, space: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
def myPow(self, x, n):
    """
    :type x: float
    :type n: int
    :rtype: float
    """
    if n == 0: return 1
    if n < 0: return 1.0 / self.myPow(x, -n)
    half = self.myPow(x, n // 2)
    if n % 2 == 0:
        return half * half
    else:
        return half * half * x