📝 Data structures and algorithms

Some notes about DSA

Big O

• Neetcode
• Big O Cheat Sheet
• Recursive with multiple branches: O(branches^depth), if not repeated work, O(n).
• Fibonacci: O(2^n), with memoization: O(n)
• Permutations, TSP: O(n!)

Reacto

• Read the problem, ask clarifying questions, assumptions
• Examples, edge cases
• Approach, pseudocode
• Code
• Test, edge cases
• Optimize, space and time complexity

Legend

• 🅱️ Blind 75 / 🗿 Neetcode / 🏢 Google
• ☀️ Easy / ⛅ Medium / ⛈️ Hard

Arrays

• Kadane’s algorithm: grow and check when to shrink

for n in nums:
    # need to shrink?
    if cur_sum+n < n: ...
    # update result
    if cur_sum > max_sum: ...

• Sliding window fixed size: l, r pointers and current window set

for r in range(len(nums)):
    if r-l+1 == k:
        ...

• Sliding window variable size: l, r pointers, iterate over r, grow while possible and shrink
• Two pointers: Palindrome, l, r from ends, choose which to move
• Prefix Sums: Get sum of any subarray in O(1), prefix / suffix products, etc

Basic & Hashing

• 🅱️Contains Duplicate☀️: 💡

  • nums = [1,2,3,1] => true

  • Hashset seen / sort and check i and i+1

  • O(n) time, O(n) space

    def containsDuplicate(self, nums: List[int]) -> bool:
        """O(n) time, O(n) space"""
        seen = set()
    
        for n in nums:
            if n in seen:
                return True
            seen.add(n)
        return False
    
    def containsDuplicate(self, nums: List[int]) -> bool:
        """O(nlogn) time, O(1) space"""
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False
    

• 🅱️Valid Anagram☀️: 💡

  • s = "anagram", t = "nagaram" => true

  • 2 Counters / 1 counter and decrease / sort

  • O(w) time, O(1) space

    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count_s = Counter(s)
        count_t = Counter(t)
        return count_s == count_t
    

• 🅱️🏢Two Sum☀️: 💡

  • nums = [2,7,11,15], target = 9 => [0,1]

  • Hashmap seen and store index, look for complement

  • O(n) time, O(n) space

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, n in enumerate(nums):
            if target - n in seen:
                return seen[target - n], i
            seen[n] = i
    

• 🅱️Group Anagrams⛅: 💡

  • strs = ["tea","tan","ate","nat"] => [["nat","tan"],["ate","tea"]]

  • Counter for each string, use tuple as key

  • O(strings*average_lenth) time, O(strings) space

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for word in strs:
            groups[tuple(sorted(Counter(word).items()))].append(word)
        return list(groups.values())
    

• 🅱️Top K Frequent Elements⛅: 💡

  • nums = [1,1,1,2,2,3], k = 2 => [1,2]

  • Counter, list of frequencies (len(nums)), iterate from end

  • O(n) time, O(n) space

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        groups_by_freq = [[] for _ in range(len(nums)+1)]
        for n, count in Counter(nums).items():
            groups_by_freq[count].append(n)
        result = []
        for i in range(len(nums), -1, -1):
            for n in groups_by_freq[i]:
                result.append(n)
                if len(result) >= k:
                    return result
        return result
    

• 🅱️Product of Array Except Self⛅: 💡

  • nums = [1,2,3,4] => [24,12,8,6]

  • Prefix product, Suffix product.

  • O(n) time, O(1) space

    def productExceptSelf(self, nums):
        ans = [1]*len(nums)
        suf, pre = 1, 1
        for i in range(len(nums)):
            ans[i] *= pre
            ans[-1-i] *= suf
            pre *= nums[i]
            suf *= nums[-1-i]
        return ans
    

• 🗿Valid Sudoku⛅: 💡

  • partially filled 9x9 grid

  • sets, squares[(r // 3, c // 3)].add(board[r][c])

  • O(1) time, O(1) space

    def isValidSudoku(self, board: List[List[str]]) -> bool:
    
        for row in board:
            numbers = [n for n in row if n != "."]
            if len(set(numbers)) != len(numbers):
                return False
    
        for i in range(9):
            numbers = [row[i] for row in board if row[i] != "."]
            if len(set(numbers)) != len(numbers):
                return False
    
        squares = defaultdict(set)
        for r in range(9):
            for c in range(9):
                block = squares[(r // 3, c // 3)]
                if board[r][c] != "." and board[r][c] in block:
                    return False
                block.add(board[r][c])
        return True
    

• 🅱️Encode and Decode Strings⛅: 💡

  • Create single string and split it back

  • Length + Separator

  • O(n) encode, O(n) decode

    def encode(self, strs):
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res
    
    def decode(self, s):
        res, i = [], 0
    
        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            res.append(s[j + 1 : j + 1 + length])
            i = j + 1 + length
        return res
    

• 🅱️Longest Consecutive Sequence⛅: 💡

  • nums = [100,4,200,1,3,2] => 4

  • Set and start if n-1 not in set

  • O(n) time, O(n) space

    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        hashset = set(nums)
        result = 1
        for n in hashset:
            if (n-1) not in hashset:
                length = 0
                cur = n
                while cur in hashset:
                    cur = cur+1
                    length += 1
                result = max(result, length)
        return result
    

Two Pointers

• 🅱️Valid Palindrome☀️: 💡

  • s = "A man, a plan, a canal: Panama" => true

  • Two pointers, if not s[i].isalnum(): i += 1

  • O(n) time, O(1) space

    def isPalindrome(self, s: str) -> bool:
        l = 0
        r = len(s)-1
        while l < r:
            while l < len(s) and not s[l].isalnum(): l += 1
            while r >= 0 and not s[r].isalnum(): r -= 1
            if l >= r:
                return True
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
    
        return True
    

• 🗿Two Sum II⛅: 💡

  • numbers = [2,7,11,15], target = 9 => [1,2]

  • 2 pointers.

  • O(n) time, O(1) space

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l = 0
        r = len(numbers)-1
        while l < r:
            cursum = numbers[l] + numbers[r]
            if cursum == target:
                return [l+1, r+1]
            if cursum < target:
                l += 1
            else:
                r -= 1
        return None
    

• 🅱️3Sum⛅: 💡

  • nums = [-1,0,1,2,-1,-4] => [[-1,-1,2],[-1,0,1]]

  • sort, for each i, 2 pointers (l = i+1, r = len(nums)-1)

  • O(n^2) time, O(n) space (sorting)

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = set()
        nums.sort()
        for i in range(len(nums)):
            l, r = i+1, len(nums)-1
            while l < r:
                sum3 = nums[l] + nums[r] + nums[i]
                if sum3 == 0:
                    result.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif sum3 < 0:
                    l += 1
                else:
                    r -= 1
        return result
    

• 🅱️Container With Most Water⛅: 💡

  • height = [1,8,6,2,5,4,8,3,7] => 49

  • start from both ends, move the smaller one

  • O(n) time, O(1) space

    def maxArea(self, height: List[int]) -> int:
        result = 0
        l, r = 0, len(height)-1
        while l < r:
            result = max(result, min(height[l], height[r])*(r-l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result
    

• 🗿Trapping Rain Water⛈️: 💡

  • height = [0,1,0,2,1,0,1,3,2,1,2,1] => 6

  • using 2 pointers, update result before moving the pointer

  • O(n) time, O(n) space

    def trap(self, height: List[int]) -> int:
        leftmax, rightmax = 0, 0
        l, r = 0, len(height)-1
        result = 0
    
        while l <= r:
            if leftmax <= rightmax:
                result += max(min(leftmax, rightmax)-height[l], 0)
                leftmax = max(leftmax, height[l])
                l += 1
            else:
                result += max(min(leftmax, rightmax)-height[r], 0)
                rightmax = max(rightmax, height[r])
                r -= 1
        return result
    

Sliding Window

• 🅱️🏢Best Time to Buy and Sell Stock☀️: 💡

  • prices = [7,1,5,3,6,4] => 5

  • Kadane’s algorithm / Two pointers (start from 0, 1)

  • O(n) time, O(1) space

    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        cheapest = prices[0]
        for p in prices:
            result = max(result, p-cheapest)
            cheapest = min(cheapest, p)
        return result
    

• 🅱️🏢Longest Substring Without Repeating Characters⛅: 💡

  • s = "abcabcbb" => 3 (“abc”)

  • Hashmap (seen, index), left = max(left, seen[c]+1)

  • O(n) time, O(1) space

    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        l = 0
        last_seen = {}
        for i, c in enumerate(s):
            if c in last_seen:
                l = max(l, last_seen[c]+1)  # do not decrease!
            last_seen[c] = i
            result = max(result, i-l+1)
        return result
    

• 🅱️Longest Repeating Character Replacement⛅: 💡

  • s = "ABAB", k = 2 => 4 (replace both A with B)

  • Window with most repeating, shrink if windowLen - max(count.values()) > k

  • O(n) time, O(1) space

    def characterReplacement(self, s: str, k: int) -> int:
        result = 0
        l = 0
        char_count = {}
        for r, c in enumerate(s):
            char_count[c] = char_count.get(c, 0) + 1
            if (r-l+1) > max(char_count.values())+k:
                char_count[s[l]] -= 1
                l += 1
            result = max(result, r-l+1)
        return result
    

• 🗿Permutation in String⛅: 💡

  • s1 = "ab" s2 = "eidbaooo" => true

  • Counter, sliding window of size len(s1)

  • O(n) time, O(1) space

    def checkInclusion(self, s1: str, s2: str) -> bool:
        cntr, w = Counter(s1), len(s1)
        for i in range(len(s2)):
            if s2[i] in cntr:
                cntr[s2[i]] -= 1
            if i >= w and s2[i-w] in cntr:  # shrink
                cntr[s2[i-w]] += 1
            if all([cntr[i] == 0 for i in cntr]):
                return True
        return False
    

• 🅱️Minimum Window Substring⛈️: 💡

  • s = "ADOBECODEBANC", t = "ABC" => "BANC"

  • Counter, if all window counter >= counter, shrink, i = 0, for j in …

  • O(n) time, O(1) space

    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        l = 0
        result = ""
        for r, c in enumerate(s):
            need[c] -= 1
            if all(v <= 0 for v in need.values()):
                while l < r and need[s[l]] < 0:
                    need[s[l]] += 1
                    l += 1
                if not result or r-l+1 < len(result):
                    result = s[l:r+1]
        return result
    

• 🗿Sliding Window Maximum⛈️: 💡

  • nums = [1,3,-1,-3,5,3,6,7], k = 3 => [3,3,5,5,6,7]

  • l, r pointers, Monotonic dec deque, store idx, pop everything smaller than current

  • O(n) time, O(k) space

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
    
        q = deque()
        l = 0
        for r in range(len(nums)):
            while q and nums[q[-1]] < nums[r]:
                q.pop()
    
            q.append(r)
            if l > q[0]:
                q.popleft()
    
            if r-k+1 >= 0:
                result.append(nums[q[0]])
                l += 1
    
        return result
    

Stack

• 🅱️Valid Parentheses☀️: 💡

  • s = "()[]{}" => true

  • store last opened in stack, check stack empty at the end

  • O(n) time, O(n) space

    def isValid(self, s: str) -> bool:
        stack = []
        close_to_open = {"}": "{", ")": "(", "]": "["}
        for p in s:
            if p in close_to_open:
                if not stack or close_to_open[p] != stack[-1]:
                    return False
                stack.pop()
            else:
                stack.append(p)
        return len(stack) == 0
    

• 🗿Min Stack⛅: 💡

  • push(val), pop(), top(), getMin()

  • stack, append((min_so_far, val)), min_so_far = min(val, self.stack[-1][0])

  • O(1) time, O(n) space

    def __init__(self):
        self.stack = []
    
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            min_so_far = min(val, self.stack[-1][0])
            self.stack.append((min_so_far, val))
    
    def pop(self) -> None:
        return self.stack.pop()[1]
    
    
    def top(self) -> int:
        return self.stack[-1][1]
    
    
    def getMin(self) -> int:
        return self.stack[-1][0]
    

• 🗿 🏢Reverse Polish Notation⛅: 💡

  • tokens = ["2","1","+","3","*"] => 9

  • b, a = stack.pop(), stack.pop() … return stack[0]

  • O(n) time, O(n) space

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {
            "+": lambda a,b: a+b,
            "-": lambda a,b: a-b,
            "*": lambda a,b: a*b,
            "/": lambda a,b: int(a/b),
        }
        for t in tokens:
            if t not in operators:
                stack.append(int(t))
            else:
                b, a = stack.pop(), stack.pop()
                stack.append(operators[t](a, b))
        return stack[0]
    

• 🗿Generate Parentheses⛅: 💡

  • n = 3 => ["((()))","(()())","(())()","()(())","()()()"]

  • stack, backtracking, dfs(opened, closed), if opened < n, if closed < opened

  • O(2^(2n)) time, O(n) space

    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        path = []
    
        def dfs(opened, closed):
            if opened == closed == n:
                result.append("".join(path))
                return
            if opened < n:
                path.append("(")
                dfs(opened+1, closed)
                path.pop()
    
            if closed < opened:
                path.append(")")
                dfs(opened, closed+1)
                path.pop()
    
        dfs(0, 0)
        return result
    

• 🗿Daily Temperatures⛅: 💡

  • T = [73,74,75,71,69,72,76,73] => [1,1,4,2,1,1,0,0]

  • init result = [0]*len, stack of pending, while tmp[i] > tmp[stack[-1]], pop and update

  • O(n) time, O(n) space

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = [0]*len(temperatures)
        pending = []
        for i, t in enumerate(temperatures):
            while pending and temperatures[pending[-1]] < t:
                prev = pending.pop()
                result[prev] = i-prev
            pending.append(i)
        return result
    

• 🗿Car fleet⛅: 💡

  • target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] => 3

  • Sort by position, start from end, calculate time to reach, ignore if faster

  • O(nlogn) time, O(n) space

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = []
        for p, s in sorted([(p,s) for p, s in zip(position, speed)], reverse=True):
            time = (target-p)/s
            if stack and time <= stack[-1]:
                continue
            stack.append(time)
        return len(stack)
    

• 🗿Largest Rectangle in Histogram⛈️: 💡

  • heights = [2,1,5,6,2,3] => 10

  • stack.append((start, h)), if decreasing, pop and update maxArea and current start

  • O(n) time, O(n) space

    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []
    
        for i, h in enumerate(heights):
            start = i
            # found a decrease in height
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index  # we can start from the leftmost index that is higher
            stack.append((start, h))
    
        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea
    

Binary Search

Remember it can be used on a range of values

• 🗿Binary Search☀️: 💡

  • nums = [-1,0,3,5,9,12], target = 9 => 4

  • while l <= r, mid = (l+r)//2

  • O(logn) time, O(1) space

    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return -1
    

• 🗿Search a 2D Matrix⛅: 💡

  • matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 => true

  • calculate row = mid // len(matrix[0]), col = mid % len(matrix[0])

  • O(logmn) time, O(1) space

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        l, r = 0, len(matrix)*len(matrix[0])-1
        while l <= r:
            mid = (l+r)//2
            row = mid // len(matrix[0])
            col = mid % len(matrix[0])
            if matrix[row][col] == target:
                return True
            if matrix[row][col] < target:
                l = mid+1
            else:
                r = mid-1
        return False
    

• 🗿Koko Eating Bananas⛅: 💡

  • piles = [3,6,7,11], H = 8 => 4

  • binary search over speed, l, r = 1, max(piles)

  • O(nlogm) time, O(1) space

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        result = r
        while l <= r:
            mid = (l+r)//2
            hours = sum(math.ceil(p/mid) for p in piles)
            if hours <= h:
                result = min(result, mid)
                r = mid-1
            else:
                l = mid+1
        return result
    

• 🅱️Search in Rotated Sorted Array⛅: 💡

  • nums = [4,5,6,7,0,1,2], target = 0 => 4

  • see which side is sorted and then if target > nums[mid] or target < nums[l]

  • O(logn) time, O(1) space

    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
    
        while l <= r:
            mid = (l+r) // 2
            if target == nums[mid]:
                return mid
    
            if nums[l] <= nums[mid]:
                if nums[l] <= target <= nums[mid]:
                    r = mid-1
                else:
                    l = mid+1
    
            else:
                if nums[mid] <= target <= nums[r]:
                    l = mid+1
                else:
                    r = mid-1
        return -1
    

• 🅱️Find Minimum in Rotated Sorted Array⛅: 💡

  • nums = [3,4,5,1,2] => 1

  • stop if nums[l] < nums[r], move l if nums[mid] >= nums[l]

  • O(logn) time, O(1) space

    def findMin(self, nums: List[int]) -> int:
        start, end = 0, len(nums)-1
        curr_min = float("inf")
    
        while start < end:
            mid = (start+end) // 2
            curr_min = min(curr_min, nums[mid])
    
            if nums[mid] > nums[end]:
                start = mid + 1
            else:
                end = mid - 1
    
        return min(curr_min, nums[start])
    

• 🗿Time Based Key-Value Store⛅: 💡

  • set(k, v, time), get(k, time)

  • if values[m][1] <= timestamp: res = values[m][0], l = m + 1

  • O(logn) time, O(n) space

    def __init__(self):
        self.store = {}
    
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((value, timestamp))
    
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        res = ""
        values = self.store[key]
        l, r = 0, len(values)-1
        while l <= r:
            m = (l+r)//2
            if values[m][1] <= timestamp:
                res = values[m][0]
                l = m+1
            else:
                r = m-1
        return res
    

• 🗿 🏢Median of Two Sorted Arrays⛈️: 💡

  • nums1 = [1,2], nums2 = [3,4] => 2.5

  • Binary search on the shorter array until Aleft <= Bright and Bleft <= Aright.

  • O(log(m+n)) time, O(1) space

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2
    
        if len(B) < len(A):
            A, B = B, A
    
        l, r = 0, len(A) - 1
        while True:
            i = (l + r) // 2  # A
            j = half - i - 2  # B
    
            Aleft = A[i] if i >= 0 else float("-inf")
            Aright = A[i + 1] if (i + 1) < len(A) else float("inf")
            Bleft = B[j] if j >= 0 else float("-inf")
            Bright = B[j + 1] if (j + 1) < len(B) else float("inf")
    
            # partition is correct
            if Aleft <= Bright and Bleft <= Aright:
                # odd
                if total % 2:
                    return min(Aright, Bright)
                # even
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1
    

Linked List

• 🅱️Reverse Linked List☀️: 💡

  • head = [1,2] => [2,1]

  • store previous, save cur.next in temp

  • O(n) time, O(1) space

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        cur = head
    
        while cur:
            next_cur = cur.next
            cur.next = prev
            prev = cur
            cur = next_cur
        return prev
    

• 🅱️Merge Two Sorted Lists☀️: 💡

  • l1 = [1,2,4], l2 = [1,3,4] => [1,1,2,3,4,4]

  • dummy first node, curr node, while l1 and l2, add remaining

  • O(n) time, O(1) space

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        p1 = list1
        p2 = list2
        dummy = ListNode()
        cur = dummy
    
        while p1 and p2:
            if p1.val > p2.val:
                p1, p2 = p2, p1
            cur.next = p1
            cur = cur.next
            p1 = p1.next
    
        if p1: cur.next = p1
        if p2: cur.next = p2
    
        return dummy.next
    

• 🅱️Merge K Sorted Lists⛈️: 💡

  • lists = [[1,4,5],[1,3,4],[2,6]] => [1,1,2,3,4,4,5,6]

  • Merge two lists at a time, for i in range(0, len(lists), 2)

  • O(nlogk) time, O(1) space

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists or len(lists) == 0:
            return None
    
        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]
    

• 🅱️Reorder List⛅ 💡

  • head = [1,2,3,4] => [1,4,2,3] (L0 -> Ln -> L1 -> Ln-1 -> L2…)

  • find mid, reverse second half, merge two lists

  • O(n) time, O(1) space

    def reorderList(self, head: Optional[ListNode]) -> None:
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
    
        p1 = head
        p2 = self.reverse(slow)
        # merge
        while p1 and p2:
            tmp1 = p1.next
            tmp2 = p2.next
            p1.next = p2
            p2.next = tmp1
            p1 = tmp1
            p2 = tmp2
        return head
    
    def reverse(self, node):
        ...
    

• 🅱️Remove Nth Node From End of List⛅: 💡

  • head = [1,2,3,4,5], n = 2 => [1,2,3,5]

  • Two pointers, move one n steps ahead.

  • O(n) time, O(1) space

    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
    

• 🗿Copy List with Random Pointer⛅: 💡

  • head = [[3,null],[3,0],[3,null]] => [[3,null],[3,0],[3,null]]

  • old_to_new = {None: None}, two passes, copy and then update next and random

  • O(n) time, O(n) space

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        old_to_new = {None: None}
        cur = head
        while cur:
            copy = Node(cur.val)
            old_to_new[cur] = copy
            cur = cur.next
    
        cur = head
        while cur:
            copy = old_to_new[cur]
            copy.next = old_to_new[cur.next]
            copy.random = old_to_new[cur.random]
            cur = cur.next
        return old_to_new[head]
    

• 🗿 🏢Add Two Numbers⛅: 💡

  • l1 = [2,4,3], l2 = [5,6,4] => [7,0,8]

  • carry = sum_ // 10, remain = p1 or p2, etc.

  • O(max(m,n)) time, O(max(m,n)) space

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode()
        cur = head
        carry = 0
        while l1 or l2 or carry:
            cur.next = ListNode()
            cur = cur.next
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            cur.val = v1 + v2 + carry
            if cur.val >= 10:
                cur.val = cur.val % 10
                carry = 1
            else:
                carry = 0
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return head.next
    

• 🅱️Linked List Cycle☀️: 💡

  • head = [3,2,0,-4], -4 -> 2 => true

  • Floyd’s Tortoise and hare / hashset of seen

  • O(n) time, O(1) space

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast: return True
        return False
    
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if id(head) in seen: return True
            seen.add(id(head))
            head = head.next
        return False
    

• 🗿Find The Duplicate Number⛅: 💡

  • nums = [1,3,4,2,2] => 2

  • Floyd’s cycle detection, slow = nums[slow]; fast = nums[nums[fast]], slow2

  • O(n) time, O(1) space

    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True :
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
    
        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow
    

• 🗿LRU Cache⛅: 💡

  • LRUCache(int capacity), get(int key), put(int key, int value)

  • double linked list (easy remove/insertion), dict key -> node, dummy head and tail

  • O(1) time, O(capacity) space

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
    
        self.left = Node(0, 0)
        self.right = Node(0, 0)
        self.left.next = self.right
        self.right.prev = self.left
    
    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])
    
        if len(self.cache) > self.cap:
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]
    
    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev
    
    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = node
        self.right.prev = node
        node.next = nxt
        node.prev = prev
    

• 🗿Reverse Nodes in k-Group⛈️: 💡

  • head = [1,2,3,4,5], k = 2 => [2,1,4,3,5]

  • groupPrev, groupNext, reverse while curr != groupNext

  • O(n) time, O(1) space

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        node = head
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        if count < k:
            return head
        new_head, prev = self.reverse(head, k)
        head.next = self.reverseKGroup(new_head, k)
        return prev
    
    def reverse(self, head, count):
        prev = None
        curr = head
        while count > 0:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
            count -= 1
        return curr, prev
    

Trees

Careful with recursion limit (bound to the application stack)

• 🅱️Invert Binary Tree☀️: 💡

  • root = [4,2,7,1,3,6,9] => [4,7,2,9,6,3,1]

  • r.right, r.left = self.invert(r.left), self.invert(r.right) or stack

  • O(n) time, O(height) space

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack = [root]
        while stack:
            node = stack.pop()
            if node is None: continue
            node.left, node.right = node.right, node.left
            stack.append(node.left)
            stack.append(node.right)
        return root
    
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root
    

• 🅱️Maximum Depth of Binary Tree☀️: 💡

  • root = [3,9,20,null,null,15,7] => 3

  • return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

  • O(n) time, O(height) space

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
    

• 🗿Diameter of Binary Tree☀️: 💡

  • root = [1,2,3,4,5] => 3

  • def dfs(node) that returns depth, update global diameter

  • O(n) time, O(height) space

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        self.dfs(root)
        return self.diameter
    
    def dfs(self, node):
        if not node:
            return 0
        left = self.dfs(node.left)
        right = self.dfs(node.right)
        self.diameter = max(self.diameter, left+right)
        return 1 + max(left, right)
    

• 🗿Balanced Binary Tree☀️: 💡

  • root = [3,9,20,null,null,15,7] => true

  • def dfs(node) that returns depth, update global balanced

  • O(n) time, O(height) space

    def isBalanced(self, root):
        self.bal = True
        self.dfs(root)
        return self.bal
    
    def dfs(self, node):
         if not node: return 0
         lft, rgh = self.dfs(node.left), self.dfs(node.right)
         if abs(lft - rgh) > 1: self.bal = False
         return max(lft, rgh) + 1
    

• 🅱️Same Tree☀️: 💡

  • p = [1,2,3], q = [1,2,3] => true

  • check None, check val and recursive call

  • O(n) time, O(height) space

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
    

• 🅱️Subtree of Another Tree☀️: 💡

  • s = [3,4,5,1,2], t = [4,1,2] => true

  • isSameTree(s, t) or isSubtree(s.left, t) or isSubtree(s.right, t)

  • O(n*m) time, O(n+m) space

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root:
            return False
        if self.is_same_tree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
    

• 🅱️Binary Tree Level Order Traversal⛅: 💡

  • root = [3,9,20,null,null,15,7] => [[3],[9,20],[15,7]]

  • while level: ans.append([node.val for node in level]); level = [...] or queue

  • O(n) time, O(n) space

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        level = [root]
        result = []
        while level:
            new_level = []
            level = [l for l in level if l]
            if level:
                result.append([n.val for n in level])
            for n in level:
                new_level.append(n.left)
                new_level.append(n.right)
            level = new_level
        return result
    

• 🗿Binary Tree Right Side View⛅: 💡

  • root = [1,2,3,null,5,null,4] => [1,3,4]

  • Level order, right most

  • O(n) time, O(n) space

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
    
        result = []
        level = [root]
        while level:
            result.append(level[-1].val)
            new_level = []
            for n in level:
                if n.left:
                    new_level.append(n.left)
                if n.right:
                    new_level.append(n.right)
            level = new_level
        return result
    

• 🗿Count Good Nodes in Binary Tree⛅: 💡

  • root = [3,1,4,3,null,1,5] => 4

  • dfs, stack = [(node, max_so_far)]

  • O(n) time, O(height) space

    def goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
    
        result = 0
        def dfs(node, max_so_far):
            nonlocal result
            if not node:
                return
    
            max_so_far = max(max_so_far, node.val)
            if node.val >= max_so_far:
                result += 1
    
            dfs(node.left, max_so_far)
            dfs(node.right, max_so_far)
    
        dfs(root, root.val)
        return result
    

• 🅱️Construct Binary Tree from Preorder and Inorder Traversal⛅: 💡

  • preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] => [3,9,20,null,null,15,7]

  • recursive, pop(0) from preorder, find index in inorder, split inorder

  • O(n^2) time, O(n) space

    def buildTree(self, preorder, inorder):
        if not preorder or not inorder:
            return
        ind = inorder.index(preorder.pop(0))  # optimize with deque
        root = TreeNode(inorder[ind])
        root.left = self.buildTree(preorder, inorder[:ind])
        root.right = self.buildTree(preorder, inorder[ind+1:])
        return root
    

• 🅱️Binary Tree Maximum Path Sum⛈️: 💡

  • root = [1,2,3] => 6

  • dfs, allow split or not, nonlocal max

  • O(n) time, O(height) space

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_path = float("-inf")
        def get_max_gain(node):
            nonlocal max_path
            if node is None:
                return 0
    
            gain_on_left = max(get_max_gain(node.left), 0)
            gain_on_right = max(get_max_gain(node.right), 0)
            current_max_path = node.val + gain_on_left + gain_on_right
            max_path = max(max_path, current_max_path)
    
            return node.val + max(gain_on_left, gain_on_right)
    
        get_max_gain(root)
        return max_path
    

• 🅱️Serialize and Deserialize Binary Tree⛈️: 💡

  • serialize(self, root) and deserialize(self, data)

  • Preorder travelsal, "1,2,N,N,3,4,N,N,5,N,N"

  • O(n) time, O(n) space

    def serialize(self, root):
        values = []
        def preorder(node):
            if node:
                values.append(str(node.val))
                preorder(node.left)
                preorder(node.right)
            else:
                values.append('#')
        preorder(root)
        return ' '.join(values)
    
    def deserialize(self, data):
        values = list(reversed(data.split()))
        def preorder():
            value = values.pop()
            if value == '#':
                return None
            node = TreeNode(int(value))
            node.left = preorder()
            node.right = preorder()
            return node
        return preorder()
    

BST: nodes left < node < nodes right

• 🅱️Lowest Common Ancestor of a Binary Search Tree⛅: 💡

  • root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 => 6

  • cur, left if p<cur and q<cur, right if p>cur and q>cur else return

  • O(n) time, O(1) space

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur = root
        while cur:
            if p.val < cur.val and q.val < cur.val:
                cur = cur.left
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right
            else:
                return cur
    

• 🅱️Validate Binary Search Tree⛅: 💡

  • root = [2,1,3] => true

  • validate(n.left, min_val, n.val) and validate(n.right, n.val, max_val)

  • O(n) time, O(height) space

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.validate(root)
    
    def validate(self, node, min_val=None, max_val=None):
        if not node:
            return True
        if min_val is not None and node.val <= min_val:
            return False
        if max_val is not None and node.val >= max_val:
            return False
        return self.validate(node.left, min_val, node.val) and self.validate(node.right, node.val, max_val)
    

• 🅱️Kth Smallest Element in a BST⛅ 💡

  • root = [3,1,4,null,2], k = 1 => 1

  • inorder traversal, return res[k-1] (or iterative inorder with stack)

  • O(n) time, O(height) space

     def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        count = []
        self.helper(root, count)
        return count[k-1]
    
    def helper(self, node, count):
        if not node:
            return
    
        self.helper(node.left, count)
        count.append(node.val)
        self.helper(node.right, count)
    

Tries

• 🅱️Implement Trie (Prefix Tree)⛅: 💡

  • insert(word), search(word), startsWith(prefix)

  • TrieNode has children dict and end bool

  • O(n) time, O(n) space

    class TrieNode:
        def __init__(self):
            self.children = {}
            self.end = False
    
    
    class Trie:
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word: str) -> None:
            curr = self.root
            for c in word:
                if c not in curr.children:
                    curr.children[c] = TrieNode()
                curr = curr.children[c]
            curr.end = True
    
        def search(self, word: str) -> bool:
            curr = self.root
            for c in word:
                if c not in curr.children:
                    return False
                curr = curr.children[c]
            return curr.end
    
        def startsWith(self, prefix: str) -> bool:
            curr = self.root
            for c in prefix:
                if c not in curr.children:
                    return False
                curr = curr.children[c]
            return True
    

• 🅱️Design Add And Search Words Data Structure⛅: 💡

  • addWord(word), search(word)

  • trie, recursive dfs(idx, node) for “.”

  • O(c) time, O(c) space

    
    class TrieNode:
        def __init__(self):
            self.children = {}  # a : TrieNode
            self.word = False
    
    
    class WordDictionary:
        def __init__(self):
            self.root = TrieNode()
    
        def addWord(self, word: str) -> None:
            cur = self.root
            for c in word:
                if c not in cur.children:
                    cur.children[c] = TrieNode()
                cur = cur.children[c]
            cur.word = True
    
        def search(self, word: str) -> bool:
            def dfs(j, root):
                cur = root
    
                for i in range(j, len(word)):
                    c = word[i]
                    if c == ".":
                        for child in cur.children.values():
                            if dfs(i + 1, child):
                                return True
                        return False
                    else:
                        if c not in cur.children:
                            return False
                        cur = cur.children[c]
                return cur.word
    
            return dfs(0, self.root)
    

• 🅱️Word Search II⛈️ 💡

  • board, words = ["oath","pea","eat","rain"] => ["eat","oath"]

  • build words trie from each cell, dfs

  • O(mn\4^mn) time, O(n) space

    class TrieNode:
        def __init__(self):
            self.children = {}
            self.isWord = False
            self.refs = 0
    
        def addWord(self, word):
            cur = self
            cur.refs += 1
            for c in word:
                if c not in cur.children:
                    cur.children[c] = TrieNode()
                cur = cur.children[c]
                cur.refs += 1
            cur.isWord = True
    
        def removeWord(self, word):
            cur = self
            cur.refs -= 1
            for c in word:
                if c in cur.children:
                    cur = cur.children[c]
                    cur.refs -= 1
    
    
    class Solution:
        def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
            root = TrieNode()
            for w in words:
                root.addWord(w)
    
            ROWS, COLS = len(board), len(board[0])
            res, visit = set(), set()
    
            def dfs(r, c, node, word):
                if (
                    r not in range(ROWS) 
                    or c not in range(COLS)
                    or board[r][c] not in node.children
                    or node.children[board[r][c]].refs < 1
                    or (r, c) in visit
                ):
                    return
    
                visit.add((r, c))
                node = node.children[board[r][c]]
                word += board[r][c]
                if node.isWord:
                    node.isWord = False
                    res.add(word)
                    root.removeWord(word)
    
                dfs(r + 1, c, node, word)
                dfs(r - 1, c, node, word)
                dfs(r, c + 1, node, word)
                dfs(r, c - 1, node, word)
                visit.remove((r, c))
    
            for r in range(ROWS):
                for c in range(COLS):
                    dfs(r, c, root, "")
    
            return list(res)
    

Heap & Priority Queue

• Binary Tree
• Heap invariant: each node is <= than its children.
• Implemented as array: root at 0, children 2i+1 & 2i+2, parent at (i-1)//2

• 🗿Kth Largest Element in a Stream☀️: 💡

  • KthLargest(int k, int[] nums), add(num) -> int

  • simple minheap, pop if len > k, return heap[0]

  • O(logk) time, O(k) space

    def __init__(self, k: int, nums: List[int]):
        heapq.heapify(nums) # O(n)
        self.heap = nums
        self.k = k
    
    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        while len(self.heap) > self.k:
            heapq.heappop(self.heap) # O(logk)
        return self.heap[0]
    

• 🗿Last Stone Weight☀️: 💡

  • stones = [2,7,4,1,8,1] => 1

  • Heapify, pop 2 largest, push diff, repeat while len > 1

  • O(nlogn) time, O(n) space

    def lastStoneWeight(self, stones: List[int]) -> int:
        result = [-s for s in stones]
        heapq.heapify(result) # n
        while len(result) > 1: # n times
            y = heapq.heappop(result)  # logn
            x = heapq.heappop(result)
            if x != y:
                heapq.heappush(result, y-x) # logn
        # nlogn
        return -result[0] if result else 0
    

• 🗿K Closests Points to Origin⛅: 💡

  • points = [[1,3],[-2,2]], K = 1 => [[-2,2]]

  • simple maxheap (-dist, x, y), pop if len > k

  • O(nlogk) time, O(k) space

    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = -(x*x + y*y)
            if len(heap) == K:
                heapq.heappushpop(heap, (dist, x, y))
            else:
                heapq.heappush(heap, (dist, x, y))
        return [(x,y) for (dist,x, y) in heap]
    

• 🗿Kth Largest Element in an Array⛅: 💡

  • nums = [3,2,1,5,6,4], k = 2 => 5

  • quickselect,

  • O(n) avg time, O(n) space

    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]
    

• 🗿Task Scheduler⛅: 💡

  • tasks = ["A","A","A","B","B","B"], n = 2 => 8

  • max_heap of times, queue, while max_heap or q, increase time

  • O(n) time, O(n) space

    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)  # O(n)
    
        time = 0
        q = deque()  # pairs of [-cnt, idleTime]
        while maxHeap or q:
            time += 1
    
            if not maxHeap:
                time = q[0][1]
            else:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    q.append([cnt, time + n])
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])
        return time
    

• 🗿Design Twitter⛅: 💡

  • postTweet, getNewsFeed, follow, unfollow

  • heap, followerset per user, tweetmap per user

  • O(nlogn) time, O(n) space

    def __init__(self):
        self.count = 0
        self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]
        self.followMap = defaultdict(set)  # userId -> set of followeeId
    
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append([self.count, tweetId])
        self.count -= 1
    
    def getNewsFeed(self, userId: int) -> List[int]:
        res = []
        minHeap = []
    
        self.followMap[userId].add(userId)
        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap:
                index = len(self.tweetMap[followeeId]) - 1
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
    
        while minHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            res.append(tweetId)
            if index >= 0:
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
        return res
    
    def follow(self, followerId: int, followeeId: int) -> None:
        self.followMap[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)
    

• 🅱️Find Median from Data Stream⛈️ 💡

  • addNum(num) and findMedian()

  • 2 heaps, max heap for left, min heap for right, balance

  • O(logn) time, O(n) space

    class MedianFinder:
        def __init__(self):
            """
            initialize your data structure here.
            """
            # two heaps, large, small, minheap, maxheap
            # heaps should be equal size
            self.small, self.large = [], []  # maxHeap, minHeap (python default)
    
        def addNum(self, num: int) -> None:
            if self.large and num > self.large[0]:
                heapq.heappush(self.large, num)
            else:
                heapq.heappush(self.small, -1 * num)
    
            if len(self.small) > len(self.large) + 1:
                val = -1 * heapq.heappop(self.small)
                heapq.heappush(self.large, val)
            if len(self.large) > len(self.small) + 1:
                val = heapq.heappop(self.large)
                heapq.heappush(self.small, -1 * val)
    
        def findMedian(self) -> float:
            if len(self.small) > len(self.large):
                return -1 * self.small[0]
            elif len(self.large) > len(self.small):
                return self.large[0]
            return (-1 * self.small[0] + self.large[0]) / 2
    

Backtracking

• Subsets:
  • append to path, dfs, pop, dfs
  • if don’t want duplicates while loop to increase idx before second dfs
• Combinations:

  for j in range(i, n+1):
      path.append(j)
      dfs(j+1)
      path.pop()
  

• Permutations:

  def backtrack(first = 0):
      if first == n:
          output.append(nums[:])
      for i in range(first, n):
          nums[first], nums[i] = nums[i], nums[first]
          backtrack(first + 1)
          nums[first], nums[i] = nums[i], nums[first]
  

• 🗿Subsets⛅: 💡

  • nums = [1,2,3] => [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

  • dfs with backtracking, result and path

  • O(n*2^n) time, O(n) space

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
    
        path = []
        def dfs(i):
            if i == len(nums):
                result.append(path[:])
                return
    
            path.append(nums[i])
            dfs(i+1)
            path.pop()
            dfs(i+1)
    
        dfs(0)
        return result
    

• 🅱️Combination Sum⛅ 💡

  • candidates = [2,3,6,7], target = 7 => [[7],[2,2,3]]

  • dfs, backtracking, append path to global res

  • O(2^target) time, O(target) space

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
    
        path = []
        def dfs(i, t):
            if t == 0:
                result.append(path[:])
                return
            if i >= len(candidates) or t < 0:
                return
    
            path.append(candidates[i])
            dfs(i, t-candidates[i])
            path.pop()
            dfs(i+1, t)
    
        dfs(0, target)
        return result
    

• 🗿Permutations⛅: 💡

  • nums = [1,2,3] => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

  • stack of

  • O(n*n!) time, O(n!) space

    def permute(self, nums: List[int]) -> List[List[int]]:
        stack = [(nums, [])]
        res = []
        while stack:
            nums, path = stack.pop()
            if not nums:
                res.append(path)
                continue
            for i in range(len(nums)):
                stack.append((nums[:i] + nums[i+1:], path+[nums[i]]))
        return res
    

• 🗿Subsets II⛅: 💡

  • nums = [1,2,2] => [[2],[1],[1,2,2],[2,2],[1,2],[]]

  • sort, while i+1 < len(nums) and nums[i] == nums[i+1]:

  • O(n*2^n) time, O(n) space

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
    
        def backtrack(i, subset):
            if i == len(nums):
                res.append(subset[::])
                return
    
            # All subsets that include nums[i]
            subset.append(nums[i])
            backtrack(i + 1, subset)
            subset.pop()
            # All subsets that don't include nums[i]
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1
            backtrack(i + 1, subset)
    
        backtrack(0, [])
        return res
    

• 🗿Combination Sum II⛅: 💡

  • candidates = [10,1,2,7,6,1,5], target = 8 => [[1,1,6],[1,2,5],[1,7],[2,6]]

  • dfs(pos, target), path = [], top if target <= 0

  • O(2^n) time, O(n) space

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
    
        res = []
    
        def backtrack(cur, pos, target):
            if target == 0:
                res.append(cur.copy())
                return
            if target <= 0:
                return
    
            prev = -1
            for i in range(pos, len(candidates)):
                if candidates[i] == prev:
                    continue
                cur.append(candidates[i])
                backtrack(cur, i + 1, target - candidates[i])
                cur.pop()
                prev = candidates[i]
    
        backtrack([], 0, target)
        return res
    

• 🅱️Word Search⛅ 💡

  • board = [["A","B","C","E"],["S","F","C","S"],...], word = "ABCCED" => true

  • dfs, backtracking, mark visited

  • O(mn\*4^l) time, O(l) space

    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()
    
        def dfs(r, c, i):
            if i == len(word):
                return True
            if (
                min(r, c) < 0
                or r >= ROWS
                or c >= COLS
                or word[i] != board[r][c]
                or (r, c) in path
            ):
                return False
            path.add((r, c))
            res = (
                dfs(r + 1, c, i + 1)
                or dfs(r - 1, c, i + 1)
                or dfs(r, c + 1, i + 1)
                or dfs(r, c - 1, i + 1)
            )
            path.remove((r, c))
            return res
    
        # To prevent TLE,reverse the word if frequency of the first letter is more than the last letter's
        count = defaultdict(int, sum(map(Counter, board), Counter()))
        if count[word[0]] > count[word[-1]]:
            word = word[::-1]
    
        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False
    
    # O(n * m * 4^n)
    

• 🗿Palindrome Partitioning⛅: 💡

  • s = "aab" => [["a","a","b"],["aa","b"]]

  • res = [], path = [], dfs(pos), for j in range(i, len(s))

  • O(n*2^n) time, O(n) space

     def partition(self, s: str) -> List[List[str]]:
        res, part = [], []
    
        def dfs(i):
            if i >= len(s):
                res.append(part.copy())
                return
            for j in range(i, len(s)):
                if self.isPali(s, i, j):
                    part.append(s[i : j + 1])
                    dfs(j + 1)
                    part.pop()
    
        dfs(0)
        return res
    
    def isPali(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l + 1, r - 1
        return True
    

• 🗿Letter Combinations of a Phone Number⛅: 💡

  • digits = "23" => ["ad","ae","af","bd","be","bf","cd","ce","cf"]

  • digit_to_char map, dfs, backtracking

  • O(n*4^n) time, O(n) space

    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }
    
        def backtrack(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return
            for c in digitToChar[digits[i]]:
                backtrack(i + 1, curStr + c)
    
        if digits:
            backtrack(0, "")
    
        return res
    

• 🗿N Queens⛈️: 💡

  • n = 4 => [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

  • dfs(row): for c in range(n), col, pos_diag, neg_diag sets

  • O(n!) time, O(n²) space

    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()  # (r + c)
        negDiag = set()  # (r - c)
    
        res = []
        board = [["."] * n for i in range(n)]
    
        def backtrack(r):
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return
    
            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue
    
                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                board[r][c] = "Q"
    
                backtrack(r + 1)
    
                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
                board[r][c] = "."
    
        backtrack(0)
        return res
    

Graphs

• Dijkstra’s Algorithm: shortest path algo, greedy, O(ElogV) time

  shortest = {}
  heap = [(0, src)]
  while heap:
      w, node = heapq.heappop(heap)
      if node in shortest:
          continue
      shortest[node] = w
      for d, w2 in adj[node]:
          if d not in shortest:
              heapq.heappush(heap, (w + w2, d))
  

• Prim’s Algorithm: MST, O(ElogV) time, O(V) space

  heap = []
  for n, w in adj[0]:
      heapq.heappush(heap, (w, 0, n))
  visited = set()
  while heap:
      w, s, d = heapq.heappop(heap)
      if d in visited:
          continue
      mst.append((s, d))
      visited.add(d)
      for n, w2 in adj[d]:
          if n not in visited:
              heapq.heappush(heap, (w2, d, n))
  

• Kruskal: Union Find

• Topological Sort: Alien dict, dfs to the end and reverse, O(V+E) time, O(V) space

Basic

• 🅱️🏢Number of Islands⛅: 💡

  • grid = [["1", "0"], ["0", "1"]] => 2

  • skip visited (mark 0 or set), dfs (4 directions) on 1s.

  • O(cells) time, O(cells) space

    def numIslands(self, grid: List[List[str]]) -> int:
        result = 0
    
        visited = set()
        def dfs(i, j):
            if (i, j) in visited: return
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]): return
            if grid[i][j] != "1": return
            visited.add((i, j))
            for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                dfs(ii, jj)
    
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1" and (i, j) not in visited:
                    result += 1
                    dfs(i, j)
    
        return result
    

• 🅱️Clone Graph⛅: 💡

  • Node with val, neighbors.

  • cache[old] = copy, for n in neighbors: copy.neighbors.append(dfs(n))).

  • O(v+e) time, O(v) space

    def cloneGraph(self, node: "Node") -> "Node":
        oldToNew = {}
    
        def dfs(node):
            if node in oldToNew:
                return oldToNew[node]
    
            copy = Node(node.val)
            oldToNew[node] = copy
            for nei in node.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy
    
        return dfs(node) if node else None
    

• 🗿 🏢Max Area of Island⛅: 💡

  • grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],...,[0,0,0,0,0,0,0,1,1,1,0,0,0]] => 6

  • return 1 + dfs(4 directions), max_area = max(max_area, dfs)

  • O(mn) time, O(mn) space

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()
    
        def dfs(r, c):
            if (
                r < 0
                or r == ROWS
                or c < 0
                or c == COLS
                or grid[r][c] == 0
                or (r, c) in visit
            ):
                return 0
            visit.add((r, c))
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
    
        area = 0
        for r in range(ROWS):
            for c in range(COLS):
                area = max(area, dfs(r, c))
        return area
    

• 🅱️🏢Pacific Atlantic Water Flow⛅: 💡

  • grid of heights.

  • start from edge and dfs(x, y, ocean, last_height) to higher, return set intersection

  • O(mn) time, O(mn) space

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        pacific = set()
        atlantic = set()
    
        for i in range(len(heights)):
            for j in range(len(heights[0])):
                if i == 0 or j == 0:
                    pacific.add((i, j))
                if i == len(heights)-1 or j == len(heights[0])-1:
                    atlantic.add((i, j))
    
        # pacific
        stack = list(pacific)
        while stack:
            i, j = stack.pop()
            for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                if (ii, jj) in pacific:
                    continue
                if self.is_valid(ii, jj, heights) and heights[ii][jj] >= heights[i][j]:
                    stack.append((ii, jj))
                    pacific.add((ii, jj))
    
        stack = list(atlantic)
        while stack:
            i, j = stack.pop()
            for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                if (ii, jj) in atlantic:
                    continue
                if self.is_valid(ii, jj, heights) and heights[ii][jj] >= heights[i][j]:
                    stack.append((ii, jj))
                    atlantic.add((ii, jj))
    
        return list(pacific.intersection(atlantic))
    
    def is_valid(self, i, j, heights):
        return 0 <= i <= (len(heights)-1) and 0 <= j <= (len(heights[0])-1)
    

• 🗿Surrounded Regions⛅: 💡

  • board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

  • dfs regions connected to edge, mark temporary, flip rest.

  • O(mn) time, O(1) space

    def solve(self, board: List[List[str]]) -> None:
        ROWS, COLS = len(board), len(board[0])
    
        def capture(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
                return
            board[r][c] = "T"
            capture(r + 1, c)
            capture(r - 1, c)
            capture(r, c + 1)
            capture(r, c - 1)
    
        # 1. (DFS) Capture unsurrounded regions (O -> T)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                    capture(r, c)
    
        # 2. Capture surrounded regions (O -> X)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
    
        # 3. Uncapture unsurrounded regions (T -> O)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "T":
                    board[r][c] = "O"
    

• 🗿Rotting Oranges⛅: 💡

  • grid = [[2,1,1],[1,1,0],[0,1,1]] => 4

  • BFS, while queue: minutes+=1 for i in range(len(queue)), check if any remain

  • O(nm) time, O(nm) space

    def orangesRotting(self, grid: List[List[int]]) -> int:
        q = collections.deque()
        fresh = 0
        time = 0
    
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    fresh += 1
                if grid[r][c] == 2:
                    q.append((r, c))
    
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while fresh > 0 and q:
            length = len(q)
            for i in range(length):
                r, c = q.popleft()
    
                for dr, dc in directions:
                    row, col = r + dr, c + dc
                    # if in bounds and nonrotten, make rotten
                    # and add to q
                    if (
                        row in range(len(grid))
                        and col in range(len(grid[0]))
                        and grid[row][col] == 1
                    ):
                        grid[row][col] = 2
                        q.append((row, col))
                        fresh -= 1
            time += 1
        return time if fresh == 0 else -1
    

• 🗿Walls and Gates⛅: 💡

  • rooms = [[2147483647,-1,0,2147483647],...,[2147483647,2147483647,2147483647,-1]]

  • BFS, while queue pop left, add to queue if rooms[r][c] > rooms[i][j]+1

  • O(nm) time, O(nm) space

    def walls_and_gates(self, rooms: List[List[int]]):
        ROWS, COLS = len(rooms), len(rooms[0])
        visit = set()
        q = deque()
    
        def addRooms(r, c):
            if (
                min(r, c) < 0
                or r == ROWS
                or c == COLS
                or (r, c) in visit
                or rooms[r][c] == -1
            ):
                return
            visit.add((r, c))
            q.append([r, c])
    
        for r in range(ROWS):
            for c in range(COLS):
                if rooms[r][c] == 0:
                    q.append([r, c])
                    visit.add((r, c))
    
        dist = 0
        while q:
            for i in range(len(q)):
                r, c = q.popleft()
                rooms[r][c] = dist
                addRooms(r + 1, c)
                addRooms(r - 1, c)
                addRooms(r, c + 1)
                addRooms(r, c - 1)
            dist += 1
    

• 🅱️Course Schedule⛅: 💡

  • DFS cycle detection (visited set, cycle set).

  • O(v+e) time, O(v) space

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # dfs
        preMap = {i: [] for i in range(numCourses)}
    
        # map each course to : prereq list
        for crs, pre in prerequisites:
            preMap[crs].append(pre)
    
        visiting = set()
    
        def dfs(crs):
            if crs in visiting:
                return False
            if preMap[crs] == []:
                return True
    
            visiting.add(crs)
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False
            visiting.remove(crs)
            preMap[crs] = []
            return True
    
        for c in range(numCourses):
            if not dfs(c):
                return False
        return True
    

• 🗿 🏢Course Schedule II⛅: 💡

  • numCourses = 2, prerequisites = [[1,0]] => [0,1]

  • DFS topological sort, return [] if cycle, visited and cycle set

  • O(v+e) time, O(v) space

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        prereq = {c: [] for c in range(numCourses)}
        for crs, pre in prerequisites:
            prereq[crs].append(pre)
    
        output = []
        visit, cycle = set(), set()
    
        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True
    
            cycle.add(crs)
            for pre in prereq[crs]:
                if dfs(pre) == False:
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True
    
        for c in range(numCourses):
            if dfs(c) == False:
                return []
        return output
    

• 🗿Redundant Connection⛅: 💡

  • edges = [[1,2], [1,3], [2,3]] => [2,3]

  • union find, return edge if cycle (parent(x) == parent(y))

  • O(n) time, O(n) space / actually O(inv_ackerman(n))

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        parents = {}
    
        def find_parent(n):
            y = parents.get(n, n)
            if y != n:
                y = find_parent(y)
                parents[n] = y
            return y
    
        def union(n1, n2):
            p1 = find_parent(n1)
            p2 = find_parent(n2)
            if p1 == p2:  # cycle
                return False
            parents[p1] = p2
            return True
    
        for n1, n2 in edges:
            if not union(n1, n2):
                return [n1, n2]
    

• 🅱️Number of Connected Components in an Undirected Graph⛅: 💡

  • n = 5, edges = [[0, 1], [1, 2], [3, 4]] => 2

  • union find

  • O(n+m) time, O(n) space

    class UnionFind:
        def __init__(self):
            self.f = {}
    
        def findParent(self, x):
            y = self.f.get(x, x)
            if x != y:
                y = self.f[x] = self.findParent(y)
            return y
    
        def union(self, x, y):
            self.f[self.findParent(x)] = self.findParent(y)
    
    
    class Solution:
        def countComponents(self, n: int, edges: List[List[int]]) -> int:
            dsu = UnionFind()
            for a, b in edges:
                dsu.union(a, b)
            return len(set(dsu.findParent(x) for x in range(n)))
    

• 🅱️Graph Valid Tree⛅: 💡

  • n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]] => true

  • adj list, DFS cycle detection, dfs(0, prev=-1) and n == len(visit)

  • O(e+v) time, O(e+v) space

    def validTree(self, n, edges):
        if not n:
            return True
        adj = {i: [] for i in range(n)}
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)
    
        visit = set()
    
        def dfs(i, prev):
            if i in visit:
                return False
    
            visit.add(i)
            for j in adj[i]:
                if j == prev:
                    continue
                if not dfs(j, i):
                    return False
            return True
    
        return dfs(0, -1) and n == len(visit)
    

• 🗿Word Ladder⛈️: 💡

  • beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] => 5

  • BFS, queue, create adj list with patterns pattern = word[:i] + '*' + word[i+1:]

  • O(m^2*n) time, O(m^2*n) space

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
    
        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)
    
        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0