Richard Qiu

DSA

13 notes

Contents

Templates

Backtracking - Aggregation

def dfs(start_index, [...additional states]):
    if is_leaf(start_index):
        return 1
    ans = initial_value
    for edge in get_edges(start_index, [...additional states]):
        if additional states: 
            update([...additional states])
        ans = aggregate(ans, dfs(start_index + len(edge), [...additional states]))
        if additional states: 
            revert([...additional states])
    return ans

Backtracking - Basic

ans = []
def dfs(start_index, path, [...additional states]):
    if is_leaf(start_index):
        ans.append(path[:]) # add a copy of the path to the result
        return
    for edge in get_edges(start_index, [...additional states]):
        # prune if needed
        if not is_valid(edge):
            continue
        path.add(edge)
        if additional states:
            update(...additional states)
        dfs(start_index + len(edge), path, [...additional states])
        # revert(...additional states) if necessary e.g. permutations
        path.pop()
def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    first_true_index = -1
    while left <= right:
        mid = (left + right) // 2
        if feasible(mid):
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_index

BFS on Tree

def bfs(root):
    queue = deque([root])
    while len(queue) > 0:
        node = queue.popleft()
        for child in node.children:
            if is_goal(child):
                return FOUND(child)
            queue.append(child)
    return NOT_FOUND

DFS on Tree

def dfs(root, target):
    if root is None:
        return None
    if root.val == target:
        return root
    left = dfs(root.left, target)
    if left is not None:
        return left
    return dfs(root.right, target)

BFS on Graphs

def bfs(root):
    queue = deque([root])
    visited = set([root])
    while len(queue) > 0:
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor in visited:
                continue
            queue.append(neighbor)
            visited.add(neighbor)

DFS on Graphs

def dfs(root, visited):
    for neighbor in get_neighbors(root):
        if neighbor in visited:
            continue
        visited.add(neighbor)
        dfs(neighbor, visited)

BFS on a Matrix

num_rows, num_cols = len(grid), len(grid[0])
def get_neighbors(coord):
    row, col = coord
    delta_row = [-1, 0, 1, 0]
    delta_col = [0, 1, 0, -1]
    res = []
    for i in range(len(delta_row)):
        neighbor_row = row + delta_row[i]
        neighbor_col = col + delta_col[i]
        if 0 <= neighbor_row < num_rows and 0 <= neighbor_col < num_cols:
            res.append((neighbor_row, neighbor_col))
    return res

from collections import deque

def bfs(starting_node):
    queue = deque([starting_node])
    visited = set([starting_node])
    while len(queue) > 0:
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor in visited:
                continue
            # Do stuff with the node if required
            # ...
            queue.append(neighbor)
            visited.add(neighbor)

Mono Stack

def mono_stack(insert_entries):
    stack = []
    for entry in insert_entries:
        while stack and stack[-1] <= entry:
            stack.pop()
            # Do something with the popped item here
        stack.append(entry)

Prefix Sum

def build_prefix_sum(arr):
    n = len(arr)
    prefix_sum = [0] * n
    prefix_sum[0] = arr[0]
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i-1] + arr[i]
    return prefix_sum

# Query sum of range [left, right] (inclusive)
def query_range(prefix_sum, left, right):
    if left == 0:
        return prefix_sum[right]
    return prefix_sum[right] - prefix_sum[left-1]

Sliding Window (Fixed Size)

def sliding_window_fixed(input, window_size):
    ans = window = input[0:window_size]
    for right in range(window_size, len(input)):
        left = right - window_size
        remove input[left] from window
        append input[right] to window
        ans = optimal(ans, window)
    return ans

Sliding Window Flexible - Longest

def sliding_window_flexible_longest(input):
    initialize window, ans
    left = 0
    for right in range(len(input)):
        append input[right] to window
        while invalid(window):        # update left until window is valid again
            remove input[left] from window
            left += 1
        ans = max(ans, window)        # window is guaranteed to be valid here
    return ans

Sliding Window Flexible - Shortest

def sliding_window_flexible_shortest(input):
    initialize window, ans
    left = 0
    for right in range(len(input)):
        append input[right] to window
        while valid(window):
            ans = min(ans, window)      # window is guaranteed to be valid here
            remove input[left] from window
            left += 1
    return ans

Topological Sort

def find_indegree(graph):
    indegree = { node: 0 for node in graph }  # dict
    for node in graph:
        for neighbor in graph[node]:
            indgree[neighbor] += 1
    return indegree


def topo_sort(graph):
    res = []
    q = deque()
    indegree = find_indegree(graph)
    for node in indegree:
        if indegree[node] == 0:
            q.append(node)
    while len(q) > 0:
        node = q.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    return res if len(graph) == len(res) else None

Trie

class Node:
    def __init__(self, value):
        self.value = value
        self.children = {}

    def insert(self, s, idx):
        # idx: index of the current character in s
        if idx != len(s):
            self.children.setdefault(s[idx], Node(s[idx]))
            self.children.get(s[idx]).insert(s, idx + 1)

Two Pointers (Opposite Direction)

def two_pointers_opposite(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        # Process current elements
        current = process(arr[left], arr[right])
        
        # Update pointers based on condition
        if condition(arr[left], arr[right]):
            left += 1
        else:
            right -= 1

Two Pointers (Same Direction)

def two_pointers_same(arr):
    slow, fast = 0, 0
    while fast < len(arr):
        # Process current elements
        current = process(arr[slow], arr[fast])
        
        # Update pointers based on condition
        if condition(arr[slow], arr[fast]):
            slow += 1
        
        # Fast pointer always moves forward
        fast += 1

Union Find

class UnionFind:
    def __init__(self):
        self.id = {}

    def find(self, x):
        y = self.id.get(x, x)
        if y != x:
            self.id[x] = y = self.find(y)
        return y

    def union(self, x, y):
        self.id[self.find(x)] = self.find(y)

Arrays & Hashing

Contains Duplicate

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        nums_set = set()
        for num in nums:
            if num in nums_set:
                return True
            else:
                nums_set.add(num)
        return False

Valid Anagram

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        #counter dict
        s_count = Counter(s)
        t_count = Counter(t)
        return s_count == t_count

Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_table = {}

        for index,num in enumerate(nums):
            if target - num in num_table:
                return [num_table[target-num], index]
            else:
                num_table[num] = index

Group Anagrams

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            res[tuple(count)].append(s) # key has to be immutable
        return list(res.values())

* Top K Frequent Elements

image-20250625033006974

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        #bucket sort
        # an array to count the freq
        nums_c = Counter(nums)
        freq = [[] for _ in range(len(nums)+1)] #freq occur at most
        #put cooresponding count to the freq
        print(freq)
        for val,count in nums_c.items():
            freq[count].append(val)
        print(freq)
        res = []
        for i in range(len(freq)-1,-1,-1):
            if freq[i]:
                for num in freq[i]:
                    res.append(num)
                    if len(res) == k:
                        return res
        return res

Heap Solution: T O(n * logk) , S O(n + k) - Where n is the length of the array and k is the number of top frequent elements.

        #another way is to maintain a window size heap
        nums_c = Counter(nums)
        #convert into a k size heap, then for the rest, compare if exists
        res = []
        for val,count in nums_c.items():
            heapq.heappush(res,(count,val))
            if len(res) > k:
                heapq.heappop(res)
        final = []
        for i in range(k):
            count, val = heapq.heappop(res)
            final.append(val)
        return final

Encode and Decode Strings

This is a good question that appears in TCP data transfer when determines the data segments.

class Solution:
    
    def encode(self, strs: List[str]) -> str:
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s: str) -> List[str]:
        print(s)  # 4#neet4#code4#love3#you
        res = []
        i = 0
        
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            i = j + 1
            j = i + length
            res.append(s[i:j])
            i = j
            
        return res

* Products of Array Except Self

image-20250625033222073

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        #forward and backward
        # 1 2 3 4
        # 1 2 6 24 ->prefix, forward order times 1
        # 24 12 12 4 ->postfix, reverse order times 1
        # the answer is equal to the prefix * postfix  except that index val output
        # so we can first store our prefix in res, then postfix to the current result O(1) time
        prefix, postfix = 1,1
        res = [0] * len(nums)
        res[0] = prefix
        n = len(nums)
        for i in range(n):
            res[i] = prefix
            prefix = nums[i] * prefix

        for i in range(n-1,-1,-1):
            res[i] = res[i] * postfix
            postfix = postfix * nums[i]
        return res
  • Time complexity: O(n)O(n)
  • Space complexity:
    • O(1) extra space.
    • O(n) space for the output array.

Valid Sudoku - Simulation

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        #matrix question
        #check diagonal, row, column
        m = len(board)
        n = len(board[0])

        for i in range(m):
            #set for duplicates
            duplicate_set = set( [str(x) for x in range(1,10)])

            for j in range(n):
                if board[i][j] == '.': continue
                if board[i][j] in duplicate_set:
                    duplicate_set.remove(board[i][j])
                else:
                    return False


        for i in range(n):
            duplicate_set = set( [str(x) for x in range(1,10)])
            for j in range(m):
                if board[j][i] == '.': continue
                if board[j][i] in duplicate_set:
                    duplicate_set.remove(board[j][i])
                else:
                    return False

        #check the square, know 9*9, 9 loops
        for i in range(9): # 0,1,2  3,4,5 // 3   6,7,8 ->2
            start_row = i // 3 * 3
            start_index = i % 3 * 3
            duplicate_set = set( [str(x) for x in range(1,10)])
            for j in range(9):
                row = j // 3 + start_row
                col = j % 3 + start_index
                print(row,col)
                if board[row][col] == '.': continue
                if board[row][col] in duplicate_set:
                    duplicate_set.remove(board[row][col])
                else:
                    return False

        return True

* Longest Consecutive Sequence

The core idea is that we only need to check if an element is start of the consecutive sequence by comparing (num - 1) in the hashset, then check the incrementing and get the length

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # start with the num - 1, put the rest in  the set
        nums = set(nums)
        longest = 0
        for num in nums:
            if num-1 not in nums: #the start index
                count = 0
                while num in nums:
                    count += 1
                    num += 1
                longest = max(longest, count)

        return longest

Two Pointers

Valid Palindrome

class Solution:
    def isPalindrome(self, s: str) -> bool:
        #2 pointers, begine
        begin = 0
        end = len(s) - 1
        def isValid(char):
            print(char)
            if char and (48 <= ord(char) <= 57) or (65 <= ord(char) <= 90) or (97 <= ord(char) <= 122):
                return True
            return False

        while begin <= end:
            #skip the white space
            if isValid(s[begin]) and isValid(s[end]):
                # print(s[begin], s[end])
                if s[begin].lower() == s[end].lower():
                    begin += 1
                    end -= 1
                else:
                    return False
            elif not isValid(s[begin]):
                begin += 1
            elif not isValid(s[end]):
                end -= 1
            
        return True

Two Sum Il - Input Array Is Sorted

When the input array is sorted, usually there are 2 patterns, use binary search for searching in O(log n) time and O(n) iterations, and 2 pointers in O(n) time.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
        return []

3Sum

image-20250625030928385

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 1 way is to use the hashmap, then similar to 2sums
        # but we can use sort to optimize it to O(1) space
        res = []
        nums.sort()

        for i, num in enumerate(nums):
            if i > 0 and nums[i] == nums[i - 1]:
                continue # Skip duplicates

            l, r = i + 1, len(nums) - 1
            while l < r:
                total = num + nums[l] + nums[r]
                if total == 0:
                    res.append([num, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]: # still continue to search
                        l += 1
                elif total < 0:
                    l += 1
                elif total > 0:
                    r -= 1

        return res

Container With Most Water

image-20250625031626312

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        # left and right
        l, r = 0, len(heights) - 1
        max_area = 0

        while l < r: # Move towards the lower boundary
            l_max, r_max = heights[l], heights[r]

            area = min(l_max, r_max) * (r - l)
            max_area = max(max_area, area)

            if l_max < r_max:
                l += 1
            else:
                r -= 1
                
        return max_area

Trapping Rain Water

The difference between the last question is that we need to keep track of all the water, so instead of comparing the max areas, we need to have another 2 pointers represents the l_max, r_max where indicates that when the l, r moves, the amount of water it can total get.

class Solution:
    def trap(self, height: List[int]) -> int:
        # increment the counts

        l, r = 0, len(height) - 1
        l_max, r_max = height[l], height[r]
        water_area = 0

        while l < r:
            # Move towards the higher boundary
            if l_max < r_max:
                l += 1
                #check if the new l_max, I more prefer this way although we can use the max() to simplify the code, but this version can illustrate the thinking process better.
                if height[l] < l_max:
                    water_area += l_max - height[l]
                else:
                    l_max = height[l]
            else:
                r -= 1
                if height[r] < r_max:
                    water_area += r_max - height[r]
                else:
                    r_max = height[r]
        
        return water_area

Summary

Todo

Sliding Window

Best Time to Buy and Sell Stock

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        min_price = prices[0]
        
        for price in prices[1:]:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)
        
        return max_profit

Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res

This is an optimize approach where we store the left pointer directly.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {}
        l = 0
        res = 0
        
        for r in range(len(s)):
            if s[r] in mp:
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
        return res

Longest Repeating Character Replacement

O(26 n)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = defaultdict(int)
        l = 0
        max_len = 0

        for r, char in enumerate(s):
            # print(char)
            count[char] += 1

            while r - l + 1 - max(count.values()) > k:
                count[s[l]] -= 1
                l += 1
            
            max_len = max(max_len, r - l + 1)
        
        return max_len
        

O(n)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = defaultdict(int)
        l = 0
        max_len = 0
        maxf = 0

        for r, char in enumerate(s):
            # print(char)
            count[char] += 1
            maxf = max(maxf, count[s[r]]) # the most frequenct chars

            while r - l + 1 - maxf > k: 
                count[s[l]] -= 1
                l += 1

            max_len = max(max_len, r - l + 1)
        
        return max_len

Minimum Window Substring

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        T = Counter(t)
        window = defaultdict(int) # Window only track the valid keys

        needed = len(T) # We compare the match dict keys
        haved = 0

        min_len = float('inf')
        l = 0
        res = [-1, -1] # Store the index of the returned

        for r,char in enumerate(s):
            if char in T: # If a match
                window[char] += 1
                if window[char] == T[char]: # If value matches
                    haved += 1

                while haved == needed: 
                    # Update result
                    if (r - l + 1) < min_len:
                        min_len = r - l + 1
                        res = [l, r]

                    # Try to shrink window
                    left_char = s[l]
                    if left_char in T:
                        if window[left_char] == T[left_char]:
                            haved -= 1
                        window[left_char] -= 1
                    l += 1
        l, r = res
        if l != -1:            
            return s[l:r + 1]
        else:
            return ""

Stack

Stack, Deque

📦 Stack (LIFO – Last In, First Out)

In python, stack can be simply represented using the list.

stack = []

# Push
stack.append(10)
stack.append(20)

# Pop
top = stack.pop()  # 20

# Peek
peek = stack[-1]    # 10

# Check if empty
is_empty = len(stack) == 0

🔁 Deque (Double-Ended Queue)

For more efficient stack/queue operations, use collections.deque:, we can also use it to represent queue (FIFO) directly

from collections import deque

dq = deque()

# Stack operations
dq.append(1)     # push to end
val = dq.pop()   # pop from end

# Queue operations
dq.appendleft(2)   # enqueue to front
val = dq.popleft() # dequeue from front

Both data structures are O(1).

Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        # Use Stack
        stack = []
        
        for char in s:
            # If closing bracket
            if stack and char in (')','}',']'):
                top = stack.pop()
                if top == '(' and char == ')':
                    continue
                elif top == '{' and char == '}':
                    continue
                elif top == '[' and char == ']':
                    continue
                else:
                    # Not a valid match
                    return False
            stack.append(char)
        if stack:
            return False
        return True

Minimum Stack

class MinStack:

    def __init__(self):
        self.stack = []
        # Keep a record of each value with the min

    def push(self, val: int) -> None:
        if self.stack:
            min_value = self.getMin()
            if min_value < val:
                self.stack.append((val, min_value))
            else:
                self.stack.append((val, val))
        else:
            self.stack.append((val, val))

    def pop(self) -> None:
        self.stack.pop()

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

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

Evaluate Reverse Polish Notation

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            # assume the stack would always be true when encounter a symbol
            if token in ('+', '-', '*', '/'):
                right = stack.pop()
                left = stack.pop()
                if token == '+':
                    stack.append(int(left) + int(right))
                elif token == '-':
                    stack.append(int(left) - int(right))
                elif token == '*':
                    stack.append(int(left) * int(right))
                elif token == '/':
                    stack.append(int(left) / int(right))
            else:
                stack.append(token)
        
        return int(stack[-1])

Generate Parentheses

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # Backtracking with stack
        stack = []
        res = []

        def backtrack(openN, closeN):
            if openN == closeN == n:
                res.append(''.join(stack))
                return
            
            # openN should alwasy be greater than closeN
            if openN < n:    # 2 conditions
                stack.append('(')
                backtrack(openN + 1, closeN)
                stack.pop()
            
            if closeN < openN:
                stack.append(')')
                backtrack(openN, closeN + 1)
                stack.pop()
        
        backtrack(0, 0)
        return res

Daily Temperatures - Monotonic Stack

A monotonic stack or queue is a data structure that maintains its elements in a strictly increasing or decreasing order, allowing efficient access to the next greater or smaller element during traversal or processing. A good link

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Mono stack with the index stored

        stack = []
        res = [0] * len(temperatures)

        for r, temp in enumerate(temperatures):
            while stack and temp > stack[-1][0]:
                val, l = stack.pop()
                res[l] = r - l

            stack.append((temp, r))
        return res

Car Fleet

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # position = [4,1,0,7], speed = [2,2,1,1]
        pos_speed = []
        for i in range(len(position)):
            pos_speed.append((position[i], speed[i]))
        
        pos_speed.sort(reverse = True)

        stack = [] # maintain the number of overlapped fleets
        for i in range(len(pos_speed)):
            time_take = (target - pos_speed[i][0]) / pos_speed[i][1] # Float
            if stack and time_take > stack[-1]: # copmare every element, cuz the stack is in increasing order, so we don't need to worry about the order, always compare with the current largest, if over means a new fleet found
                stack.append(time_take)
            if i == 0:
                stack.append(time_take)
                continue
        return len(stack)

Largest Rectangle In Histogram

Core idea is that we need to identify use stack for this problem to aim O(n) time.

This algorithm uses a monotonic increasing stack to find the largest rectangle in a histogram by storing (height, index) pairs.

  • As you iterate, if the current height is smaller than the height at the top of the stack, you pop from the stack, treating it as the height of a potential rectangle that ends at the current index.
  • For each popped bar, you calculate the area using its height and the width from its stored index to the current index.
  • After finishing the iteration, you process any remaining bars in the stack as if they extend to the end of the histogram.

image-20250625025648160

image-20250625025710919

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        stack = [] # Keep track of the areas

        for r, height in enumerate(heights):
            # If the curr height is smaller than previous, pop the stack
            curr = r
            while stack and height < stack[-1][0]: # pop the bar where height is greater than current bar
                l_height, l = stack.pop() 
                max_area = max(max_area, (curr - l) * l_height) # compute the max area
                r = l
            stack.append((height, r)) 
        # And also process the end of stack
        r = len(heights)
        while stack:
            l_height, l = stack.pop()
            max_area = max(max_area, (r - l) * l_height)
        return max_area

Largest Square In Histogram

Got this question in the code signal Q4, the question is basically asking finding the largest square similar to the previous one. And the only difference would be we need to add a constraint this time which we can only choose the minimum(width, height) to calculate the square.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        stack = []  # (height, index)

        for r, height in enumerate(heights):
            curr = r
            while stack and height < stack[-1][0]:
                l_height, l = stack.pop()
                width = curr - l
                side = min(l_height, width)  # side of the square
                max_area = max(max_area, side * side)
                r = l  # reuse previous left boundary
            stack.append((height, r))

        r = len(heights)
        while stack:
            l_height, l = stack.pop()
            width = r - l
            side = min(l_height, width)
            max_area = max(max_area, side * side)

        return max_area

Summary

🧾 Stack, Deque, and Monotonic Stack/Queue Summary

Structure Purpose Python Implementation Common Ops (Time) Notes
Stack LIFO (Last In First Out) list or collections.deque append(), pop() – O(1) Use list for simple stacks; prefer deque for large/modifying stacks
Deque Double-ended queue collections.deque append(), appendleft(), pop(), popleft() – O(1) Efficient at both ends; good for queues, sliding windows
Monotonic Stack Maintain increasing/decreasing order list Custom push/pop logic Used in next greater/smaller element problems
Monotonic Queue Maintain increasing/decreasing order deque Custom append/pop logic Often used in sliding window maximum/minimum problems

Linked List

Reverse Linked List

Main idea is about switching the direction between 2 nodes by using 2 variables, similar to the swapping algorithm, keep a variable of the next one and switching the prev and curr places, then finally reassigning.

image-20250622000839488

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head

        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        
        return prev

Merge Two Sorted Linked Lists

Notice that linked list is stored in memory, so reassigning the order wouldn’t need extra space, get confused for the in-place changing at first.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()
        while list1 and list2:
            if list2.val <= list1.val:
                tail.next = list2
                list2 = list2.next
            else:
                tail.next = list1
                list1 = list1.next
            tail = tail.next

        if list1:
            tail.next = list1
        elif list2:
            tail.next = list2

        return dummy.next

Linked List Cycle Detection

A good way to remember is that start at the same position, and fast pointer moves by 2. So we want to check that fast and fast.next if it’s null, cuz it would throw an error if we indexing the null since we are incrementing the fast pointer by 2 then we can compare with the slow and fast.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 2 pointers, a cycle would never reach the end
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False

Reorder Linked List

We can find that is about moving the left and right pointer, the issue is that for linked list we can’t easily get the prev list, we can solve this by reversing the second half then using the 2 pointers.

image-20250622155228004

An efficient way to find the mid position is to use a slow and fast pointer.

image-20250622155343958

https://leetcode.com/problems/middle-of-the-linked-list/

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

image-20250622163550339

Notice that how we use slow.next = None to break the linked list into half.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow.next # curr now holds a reference to the node *after* slow
        slow.next = None # breaks the first half of the list by setting slow.next to None
        #reverse the linked list
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

Remove Node From End of Linked List

image-20250622184934281

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # two pointers with n incrementing space to know the end
        # dummy = head
        dummy = slow = ListNode(next = head)
        fast = head
        for _ in range(n):
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next
        
        # remove = slow.next
        # slow.next = remove.next
        slow.next = slow.next.next # another way to delete

        return dummy.next

Copy Linked List with Random Pointer

Core idea is that we want to construct a hashmap that stores each node as the key, and also create a corresponding newNode for each node. So that on the next iteration we can connect the hashmap value based on the current node.

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return None

        tail = head
        table = {None: None} # key: node, value: newNode

        while tail:
            table[tail] = Node(tail.val)
            tail = tail.next
        tail = head
        
        while tail:
            table[tail].next = table[tail.next]
            table[tail].random = table[tail.random]
            tail = tail.next

        return table[head]

We can also optimize this to O(1) auxiliary space.

Step1:

image-20250623001804451

Step2:

image-20250623001821356

Step3:

image-20250623001830587

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        node = head
        while node:
            nxt = node.next
            node.next = Node(node.val) # Create a clone
            node.next.next = nxt
            node = nxt

        # Assign the random
        node = head
        while node:
            random_node = node.random
            if random_node:
                node.next.random = random_node.next
            node = node.next.next
        
        # Now reconstructing the original list and also store the new list
        node = head
        copy_node = clone = head.next
        while node:
            node.next = node.next.next
            clone.next = (clone.next.next if clone.next else None)
            node = node.next
            clone = clone.next
        
        return copy_node

Add Two Numbers

Not too many tricks, just be careful to handle the length and carry.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy

        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # new digit
            val = v1 + v2 + carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)

            # update ptrs
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

Find the Duplicate Number - Floyd’s Cycle Detection

  1. Linked List Cycle
  2. Floyd’s

2 iterations:

1st first find the start and slow pointer

image-20250623024140673

2nd slow2 start at the beginning, once the slow and slow2 reach, it means the duplicate is found.

image-20250623024627344

class Solution:
    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

https://www.geeksforgeeks.org/floyds-cycle-finding-algorithm/

Find the Starting Node of a Cycle in a Linked List

To find the starting node of a cycle in a linked list, follow the steps below:

  • Using above algorithm we can find the *meeting point (if cycle exists)* where the slow and fast pointers *intersect* inside the cycle.
  • After detecting the cycle, reset one pointer *(slow)* to the *head* of the list. Keep the other pointer *(fast)* at the meeting point.
  • Move both pointers *one s*tep at a time. The node where they meet again is the *start* of the cycle.

LRU cache

Doubly Linked List, practice, practice and practice …

class Node:
    def __init__(self, key=0, val=0, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key: int -> Node
        self.start = Node()  # dummy head
        self.tail = Node()   # dummy tail
        self.start.next = self.tail
        self.tail.prev = self.start

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove_node(node)
            self._add_node(node)
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove_node(node)
            self._add_node(node)
        else:
            if len(self.cache) >= self.capacity:
                lru = self.tail.prev
                self._remove_node(lru)
                del self.cache[lru.key]
            new_node = Node(key, value)
            self._add_node(new_node)
            self.cache[key] = new_node

    def _add_node(self, node):
        # Always add to the front (right after dummy head)
        node.prev = self.start
        node.next = self.start.next
        self.start.next.prev = node
        self.start.next = node

    def _remove_node(self, node):
        # Detach from its neighbors
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

Merge K Sorted Linked Lists

The core idea is we can separate this question from merge multiple linked lists to merge 2 linked lists per time and it will eventually result into a single list. Time: O(n logk), Space(k), k is the length of the input lists

image-20250624031526364

class Solution:    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # split the lists into 2 and merge every time and eventually it will converge to 1

        if not lists:
            return None

        while len(lists) > 1:
            merged_lists = []
            for i in range(0, len(lists), 2): # merge 2 lists each time
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None # may out of bounds
                merged_lists.append(self.mergeLists(l1, l2))
            lists = merged_lists

        return lists[0]

    def mergeLists(self, l1, l2):
        # Merge 2 lists and return the megered list
        dummy = tail = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next

Reverse Nodes in K-Group

The main idea is that we can split this question into the version of reverse linked list by comparing the end node after k steps. But we need to be very careful on relinking the reverse nodes.

image-20250624030627295

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None

        start = dummy = ListNode(next = head)

        while True:
            end_k = self.getReversePos(k, start)
            
            if not end_k:
                break
            groupNext = end_k.next

            prev, curr = end_k.next, start.next
            # reverse linked lists
            while curr != groupNext:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            # complicated ->
            tmp = start.next # first node
            start.next = end_k # the kth reverse node position
            start = tmp # now the first node is pointing to the remaining linked list, we can use this as our start
        return dummy.next

    def getReversePos(self, k, l):
        while l and k > 0:
            l = l.next
            k -= 1
        return l
   

Summary

After working through these linked list problems, several recurring techniques emerge, each with specific scenarios where they are most effective:

🟩 Two Pointers (Slow/Fast)

  • Finding the Middle Node → Use slow and fast pointers. Fast moves 2 steps, slow moves 1. When fast reaches the end, slow is at the middle. ⤷ middleNode, reorderList
  • Cycle Detection → Use the same pattern. If a cycle exists, slow and fast will eventually meet. ⤷ hasCycle, findDuplicate (array-based cycle)
  • Finding Cycle Start Point → After detecting a cycle, reset one pointer to head and move both 1 step at a time. Their meeting point is the start of the cycle. ⤷ findDuplicate (Floyd’s Tortoise & Hare)
  • Finding K-th Node from End → Move fast pointer n steps ahead, then move both slow and fast together. When fast reaches the end, slow is at the target. ⤷ removeNthFromEnd

🟨 Reversing a Linked List

  • Full List Reverse → Use prev, curr, and nxt to reverse pointers. ⤷ reverseList
  • Reverse Partial (e.g., K-group) → Apply the same logic within a group. First validate group size using pointer traversal, then reverse in-place. ⤷ reverseKGroup
  • Helper for Complex Operations → Used in problems like reorderList to reverse the second half before merging.

🟦 Dummy Node

  • Simplify Insert/Delete Operations → Always use a dummy head when dealing with potential edge cases (e.g., inserting at head or removing head node). ⤷ mergeTwoLists, removeNthFromEnd, addTwoNumbers, mergeKLists

🟧 Hash Map

  • Track Correspondence Between Original and Copied Nodes → Use when each node has more than just .next (e.g., random pointer). ⤷ copyRandomList (O(n) space solution)

🟥 Priority Queue / Divide and Conquer

  • Merging K Sorted Lists → Use min-heap for O(N log K) or pairwise divide-and-conquer merges. ⤷ mergeKLists

🟨 Doubly Linked List + HashMap

  • LRU Cache → Use a doubly linked list for ordering and hashmap for O(1) lookup and insert/remove. ⤷ LRUCache

Key Takeaways

  • Linked List = Pointer Manipulation → Understand how to disconnect/reconnect nodes safely.

  • Patterns are Reusable → Nearly every complex linked list problem is a variation of a basic pattern.

  • Space vs. Time Trade-offs → Know when to use extra space (e.g., HashMap) vs. clever pointer tricks (e.g., interleaving nodes in-place).

  • ycle or locating duplicates when the input is constrained (e.g., values used as pointers).

Trees

Trees

https://www.w3schools.com/dsa/dsa_theory_trees.php

binary_tree_dfs

def pre_order(root: TreeNode | None):
    """Pre-order traversal"""
    if root is None:
        return
    # visit order: root -> left -> right
    res.append(root.val)
    pre_order(root=root.left)
    pre_order(root=root.right)

def in_order(root: TreeNode | None):
    """In-order traversal"""
    if root is None:
        return
    # visit order: left -> root -> right
    in_order(root=root.left)
    res.append(root.val)
    in_order(root=root.right)

def post_order(root: TreeNode | None):
    """Post-order traversal"""
    if root is None:
        return
    # visit order: left -> right -> root
    post_order(root=root.left)
    post_order(root=root.right)
    res.append(root.val)

Invert Binary Tree

We can identify that each node in the tree is switched, so we can simply just switch the left and right node

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        #dfs on each node and switch each other
        def dfs(root):
            if not root:
                return

            root.left, root.right = root.right, root.left
            dfs(root.left)
            dfs(root.right)

        dfs(root)
        return root

Maximum Depth of Binary Tree

DFS use the level to track each node and return when it reaches the bottom, and compare the max(left, right). Bottom up

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

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

# Below is an uncommon top-down style approach where we increment the level for each step
def dfs(node, level):
    if not node:
        return level
    left = dfs(node.left, level + 1)
    right = dfs(node.right, level + 1)
    return max(left, right)

BFS approach

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # bfs store each node and pop
        if not root:
            return 0
        def bfs(root):
            depth = 0
            q = deque([root])
            while q:
                n = len(q)
                depth += 1
                for _ in range(n):
                    node = q.popleft()
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
            return depth
        return bfs(root)

Diameter of Binary Tree

Similar to find the depth of binary tree, we just need to also track if the left + right is the maximum, we could add a comparison function before returning each node’s depth.

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # for each node, we check the left and right, and also left + right
        self.res = 0
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.res = max(self.res, left + right) # track the diameter

            return 1 + max(left, right)

        dfs(root)
        return self.res

Balanced Binary Tree

Similar idea of finding the depth of the binary tree, this case we would compare each node’s height. Notice there are serval ways to determine the result, I am using a self.balanced for simplicity, but we could also use a tuple to store the state or change the return on left and right (-1) when it is unbalanced in this question.

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.balanced = True
        def dfs(root):
            if not root:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)

            if abs(left - right) > 1:
                self.balanced = False

            return 1 + max(left, right)

        dfs(root)
        return self.balanced

Same Binary Tree

Traverse both trees at the same time and compare each node’s value.

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def dfs(p, q):
            if not p and not q:
                return True
            elif not p:
                return False
            elif not q:
                return False

            if p.val != q.val:
                return False

            left = dfs(p.left, q.left)
            right = dfs(p.right, q.right)

            return left and right

        return dfs(p, q)

Subtree of Another Tree

We could separate this question into 2 parts, one is find if 2 trees are identical and second is to iterate each node on the root and compare to check if there is a match.

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def isSameTree(p, q):
            if not p and not q:
                return True
            elif not p:
                return False
            elif not q:
                return False

            if p.val != q.val:
                return False

            left = isSameTree(p.left, q.left)
            right = isSameTree(p.right, q.right)

            return left and right

        def dfs(root):
            if not root:
                return False
            if isSameTree(root, subRoot):
                return True
            left = dfs(root.left)
            right = dfs(root.right)

            return left or right

        return dfs(root)

* Lowest Common Ancestor in Binary Search Tree - DFS

The DFS approach is straightforward and would take O(n) space, but we can further optimize into O(1) space.

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # mid, left, right
        self.ans = None
        def dfs(root):
            if not root:
                return False

            left = dfs(root.left)
            right = dfs(root.right)

            mid = True if root.val == p.val or root.val == q.val else False
            if left + right + mid >= 2:
                self.ans = root

            return left or right or mid

        dfs(root)
        return self.ans

We can use the property of the binary search tree, when that basically if a node is between the p and q, then it should become the LCA and we can return. If both nodes smaller, we can set the curr to left node and vice versa for the right node.

class Solution:
    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.right
            elif p.val < cur.val and q.val < cur.val:
                cur = cur.left
            else:
                return cur

Binary Tree Level Order Traversal - BFS

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # bfs on each q length, append the left right node
        if not root:
            return []
        q = deque([root])
        res = []
        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level)
        return res

Binary Tree Right Side View - BFS

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # bfs and store the first appeared result
        res = []
        q = deque([root])
        if not root:
            return []
        while q:
            for i in range(len(q)):
                node = q.popleft()
                if i == 0:
                    res.append(node.val)
                if node.right:
                    q.append(node.right)
                if node.left:
                    q.append(node.left)
        return res

Count Good Nodes in Binary Tree

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        # top down, pass the root.val 
        self.count = 0
        def dfs(root, prev_max):
            if not root:
                return

            if root.val >= prev_max:
                self.count += 1
                prev_max = root.val

            dfs(root.right, prev_max)
            dfs(root.left, prev_max)

        dfs(root, float('-inf'))
        return self.count

Another way without using the global variables

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(root,max_temp):
            if root is None:
                return 0

            total = 0
            if root.val >= max_temp:
                total = 1
                max_temp = root.val
            total += dfs(root.left,max_temp)
            total += dfs(root.right,max_temp)

            return total

        return dfs(root,-inf)

Valid Binary Search Tree

image-20250625141045896

DFS approach - Better

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False

            return valid(node.left, left, node.val) and valid(
                node.right, node.val, right
            )

        return valid(root, float("-inf"), float("inf"))

BFS approach

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        q = deque([(root, float('-inf'), float('inf'))])
        
        while q:
            node, left, right = q.popleft()
            if not node:
                continue
            if not left < node.val < right:
                return False
            
            q.append((node.left, left, node.val))
            q.append((node.right, node.val, right))
        return True

Kth Smallest Integer in BST

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # in order traversal, count
        self.count = 0
        self.res = root.val
        def dfs(root):
            if not root:
                return

            dfs(root.left)
            self.count += 1
            if self.count == k:
                self.res = root.val
            dfs(root.right)
        dfs(root)
        return self.res

Construct Binary Tree from Preorder and Inorder Traversal

image-20250628154649667

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None

        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
        return root

Binary Tree Maximum Path Sum

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.res = root.val
        def dfs(root):
            if not root:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)
            left_max = max(left, 0)
            right_max = max(right, 0)
            # computer max path sum WITH split
            self.res = max(self.res, root.val + left_max + right_max)
            # computer max path sum WITHOUT split
            return root.val + max(left_max, right_max)

        dfs(root)
        return self.res

Heap / Priority Queue

Priority Queue (Heap)

  • A heap is a binary tree where the parent node is smaller (min-heap) or larger (max-heap) than its children.
  • Python’s heapq implements a min-heap.
  • For max-heap, insert negative values.

min_heap_and_max_heap

🧮 Time Complexity

Operation Time Complexity
heappush() O(log n)
heappop() O(log n)
heapify() O(n)
heapreplace() O(log n)
nsmallest() O(n log k)

Syntax

import heapq

# Min-Heap, by default Python using min heap
min_heap = []
for num in [3, 1, 5]:
    heapq.heappush(min_heap, num)
print("Top of Min-Heap:", heap[0])  # → 1
print("Min-Heap pop:", heapq.heappop(min_heap))  # → 1

# Max-Heap using negation
max_heap = []
for num in [3, 1, 5]:
    heapq.heappush(max_heap, -num)
print("Top of Max-Heap:", -max_heap[0])  # → 5
print("Max-Heap pop:", -heapq.heappop(max_heap))  # → 5, notice the minus sign

# Heapify a list
arr = [4, 2, 7, 1]
heapq.heapify(arr)
print("Heapified array:", arr)  # → [1, 2, 7, 4] or similar heap order

Find Median From Data Stream

image-20250625165234530

class MedianFinder:

    def __init__(self):
        # two heaps, heap should have equal size
        # 3 2 7 4
        # rebalance the heap, every elements in small heap < large_heap[0]
        self.small_heap = [] # max heap, default
        self.large_heap = [] # min heap

    def addNum(self, num: int) -> None:
        # when the length of the two heap difference > 1, rebalance the heap
        # check where to add
        # rebalance based on the 2 heap lengths
        if not self.small_heap:
            heapq.heappush(self.small_heap, -num)
        elif num > -self.small_heap[0]:
            heapq.heappush(self.large_heap, num)
            # balance
            if len(self.large_heap) - len(self.small_heap) > 1:
                val = heapq.heappop(self.large_heap)
                heapq.heappush(self.small_heap, -val)
        else:
            heapq.heappush(self.small_heap, -num)
            if len(self.small_heap) - len(self.large_heap) > 1:
                val = -heapq.heappop(self.small_heap)
                heapq.heappush(self.large_heap, val)

    def findMedian(self) -> float:
        # check the length
        if len(self.small_heap) == len(self.large_heap):
            res = (-self.small_heap[0] + self.large_heap[0]) / 2
            return res
        elif len(self.small_heap) > len(self.large_heap):
            return -self.small_heap[0]
        else:
            return self.large_heap[0]

Task Scheduler

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        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

Backtracking

Subsets

image-20250625174257689

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrack(path, start):
            res.append(path[:])  # Add current subset (copy)

            for i in range(start, len(nums)):
                path.append(nums[i])               # Choose
                backtrack(path, i + 1)             # Explore (next element)
                path.pop()                         # Un-choose (backtrack)

        backtrack([], 0)
        return res

* Combination Sum

image-20250625181455212

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def backtrack(path, remain, start):
            if remain == 0:
                res.append(path[:])
                return
            if remain < 0:
                return  # pruning

            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(path, remain - candidates[i], i)  # reuse same element
                path.pop()

        backtrack([], target, 0)
        return res

Combination Sum II

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()

        def backtrack(candidates, remaining, path, start):
            if remaining == 0:
                res.append(path[:])
                return
            elif remaining < 0: # prunning
                return

            for i in range(start, len(candidates)):
                # i > start, means we dont want to skip the first level in backtracking
                # in 3 sums, we use i > 0, but this case we also need to consider duplicates
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                backtrack(candidates, remaining - candidates[i], path, i + 1)
                path.pop()

        backtrack(candidates, target, [], 0)
        return res

There is also a faster approach, to learn

def permute(self, nums: List[int]) -> List[List[int]]:
    self.res = []
    self.backtrack(nums, 0)
    return self.res

def backtrack(self, nums: List[int], idx: int):
    if idx == len(nums):
        self.res.append(nums[:])
        return
    for i in range(idx, len(nums)):
        nums[idx], nums[i] = nums[i], nums[idx]   # Swap
        self.backtrack(nums, idx + 1)
        nums[idx], nums[i] = nums[i], nums[idx]   # Swap back
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

        def dfs(r, c, index):
            if index == len(word):
                return True
            if not (0 <= r < m and 0 <= c < n):
                return False
            if board[r][c] != word[index]:
                return False

            temp = board[r][c]
            board[r][c] = "#"

            for dr, dc in directions:
                if dfs(r + dr, c + dc, index + 1):
                    return True

            board[r][c] = temp
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

N-Queens

The order for below code is that it first tried the first column and backtrack next row, since the col on the first row first column is taken it will try the second column, mean time it will also add the diagonal to the set and configure the board[r][c]. so it would return till the very top first row, second column once the r == n, and meantime it will revert all the previous changes

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()  # r + c
        negDiag = set()  # r - c

        res = []
        board = [["."] * n for _ 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

BFS on Graphs

def bfs(root):
    queue = deque([root])
    visited = set([root])
    while len(queue) > 0:
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor in visited:
                continue
            queue.append(neighbor)
            visited.add(neighbor)

DFS on Graphs

def dfs(root, visited):
    for neighbor in get_neighbors(root):
        if neighbor in visited:
            continue
        visited.add(neighbor)
        dfs(neighbor, visited)

* Number of Islands

DFS is more preferred for this question

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # bfs
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        m = len(grid)
        n = len(grid[0])
        count = 0

        def dfs(i, j):
            if not (0 <= i < m and 0 <= j < n):
                return
            if grid[i][j] != '1':
                return
            grid[i][j] = '0'    
            for dx, dy in directions:
                dfs(i + dx, j + dy)
            return
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        
        return count

BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        #adjacent horizontally and vertically
        #notice it is char instead of int
        #m,n is greater than 1
        #can only be 0 and 1, char

        m = len(grid)
        n = len(grid[0])

        edges = [(-1,0),(1,0),(0,-1),(0,1)]

        def bfs(grid,i,j):
            queue = deque([(i,j)])
            
            while queue:
                r,c = queue.popleft()
                #check 4 directions
                for dr,dc in edges:
                    n_r,n_c = r+dr,c+dc
                    if 0 <= n_r < len(grid) and 0 <= n_c < len(grid[0]) and grid[n_r][n_c] == '1':
                        grid[n_r][n_c] = '0' #mark as visited
                        queue.append((n_r,n_c))
            # print(grid)

        count = 0
        #bfs constantly checking the grid
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    bfs(grid,i,j)

        return count

Max Area of Island (Bottom up)

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0
        m = len(grid)
        n = len(grid[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def dfs(x, y) -> int:
            if not (0 <= x < m and 0 <= y < n and grid[x][y] == 1):
                return 0
            area = 1
            grid[x][y] = 0
            for dx, dy in directions:
                area += dfs(x + dx, y + dy)
            return area

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    max_area = max(dfs(i, j), max_area)

        return max_area

Clone Graph

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # hashmap [oldNode, newNode]
        old_to_new = {}

        def dfs(node):
            if node in old_to_new:
                return old_to_new[node]
            
            copy = Node(node.val)
            old_to_new[node] = copy
            for neighbour in node.neighbors:
                copy.neighbors.append(dfs(neighbour))

            return copy
        
        return dfs(node) if node else None

Islands and Treasure - Multi source BFS

The term multi-source BFS refers to the fact that you are starting your breadth-first search (BFS) from multiple sources simultaneously, rather than just one. In this question, we start the bfs from mutiple treasures at the same time interval.

class Solution:
    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        m, n = len(grid), len(grid[0])
        INF = 2147483647
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        q = deque()

        # Add all treasures (0s) to the queue
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    q.append((i, j))

        # Multi-source BFS
        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == INF:
                    grid[nx][ny] = grid[x][y] + 1
                    q.append((nx, ny))

* Rotting Fruit - Multisource BFS

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        m = len(grid)
        n = len(grid[0])
        fresh = 0
        q = deque()

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1

        minute = 0
        while q and fresh > 0:
            for _ in range(len(q)):
                x, y = q.popleft()

                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        fresh -= 1
                        q.append((nx, ny))
            minute += 1

        return minute if fresh == 0 else -1

* Course Schedule

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        adj = [[] for i in range(numCourses)]
        for src, dst in prerequisites:
            indegree[dst] += 1
            adj[src].append(dst)

        q = deque()
        for n in range(numCourses):
            if indegree[n] == 0:
                q.append(n)
        
        finish = 0
        while q:
            node = q.popleft()
            finish += 1
            for nei in adj[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)
                
        return finish == numCourses

* Number of Connected Components in an Undirected Graph

DFS, Union find is more preferred for this problem

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        visit = [False] * n
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def dfs(node):
            for nei in adj[node]:
                if not visit[nei]:
                    visit[nei] = True
                    dfs(nei)
        
        res = 0
        for node in range(n):
            if not visit[node]:
                visit[node] = True
                dfs(node)
                res += 1
        return res

1-D Dynamic Programming

1D Dynamic Programming

Climbing Stairs

class Solution:
    def climbStairs(self, n: int) -> int:
        # 1,1,1
        # 1,2
        # 2,1

        # i feel like sometimes is hard to find the recursion function
        # dp = [0] * n

        # for i in range(n):
        #     dp[]

        # n = 2, 2
        # n =3, 3
        # if u find the state function, then it will come eaisly
        if n == 1:
            return 1
        first = 1
        second = 2
        
        for i in range(3,n+1):
            third = first + second
            first = second
            second = third
        
        return second

        # def recursion(n, i):
        #     if i == n:
        #         print()
        #         return 1
        #     if i > n:
        #         return 0
            
        #     return recursion(n, i+1) + recursion(n, i +2)
        
        # return recursion(n,0)

House Robber

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])
        
        # dp = [0] * n
        # dp[0] = nums[0]
        # dp[1] = max(nums[0], nums[1])
        prev2, prev1 = 0,0
        prev2 = nums[0]
        prev1 = max(nums[0], nums[1])

        for i in range(2,n):
            # dp[i] = max(dp[i-1], dp[i-2]+nums[i])
            temp = max(prev1, nums[i] + prev2)
            prev2 = prev1
            prev1 = temp
        return prev1

House Robber II

class Solution:
    def rob(self, nums: List[int]) -> int:
        #just treat this as either nums[:-1], not include the last number to end or nums[1:]
        n = len(nums)
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])
        def houserobber(arr):
            # print(arr)
            first,second = arr[0], max(arr[1], arr[0])
            for i in range(2,n - 1):
                temp = max(second, first + arr[i])
                first = second
                second = temp
            return second
        
        return max(houserobber(nums[:n-1]), houserobber(nums[1:]))

Longest Palindromic Substring

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expandAroundCenter(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[(left + 1):right]  # The valid palindrome window, cuz left and right would go one step too far when condition fails

        res = ""
        for i in range(len(s)):
            # Odd-length
            odd = expandAroundCenter(i, i)
            # Even-length
            even = expandAroundCenter(i, i + 1)
            # Pick the longer one
            if len(odd) > len(res):
                res = odd
            if len(even) > len(res):
                res = even
        return res

Palindromic Substrings

class Solution:
    def countSubstrings(self, s: str) -> int:
        #similar to the expansion,
        count = 0
        n = len(s)
        def expansion(left,right):
            temp_count = 0
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
                temp_count += 1
            return temp_count

        for i in range(n):
            count += expansion(i,i) #expansion from center
            count += expansion(i,i+1) #even

        return count

Decode Ways

class Solution:
    def numDecodings(self, s: str) -> int:
        # 2236, 2,2,3,6,  
        n = len(s)
        dp = [0] * (n+1)
        dp[0] = 1
        if s[0] != '0':
            dp[1] = 1
        else:
            dp[1] = 0

        for i in range(2,n+1):
            one_digit = int(s[i - 1])
            two_digits = int(s[i - 2:i])

            if one_digit != 0:
                dp[i] = dp[i - 1]

            if 10 <= two_digits <= 26:
                dp[i] += dp[i - 2]
        print(dp)
        return dp[n]

Simulation

CodeSignal

Understand the question type through this general-coding-assessment-framework.pdf.

Recommend question order, Q1 -> Q2 > Q3 (look through the question) -> Q4 (brute force if not able to come up an optimal solution) -> Q3(finish) -> Q4(optimize)

Q1 & Q2

For q1, straightforward, understand common used array and string manipulation methods. (5 - 10 lines of code)

For q2, The question can be long, take time to understand the question and solve use the brute force way. (10 - 20 lines of code)

# 2. String Indexing and Slicing
s = "AdvancedPython"
print(s[0])    # First character: 'A'
print(s[-1])   # Last character: 'n'
print(s[2:8])  # Substring from index 2 to 7: 'vanced'
print(s[:7])   # From beginning to index 6: 'Advance'
print(s[::2])  # Every 2nd character: 'Aaceyh'
print(s[::-1]) # Reverse the string
# 3. Common String Methods
text = "  Hello, Python World!  "
print(text.strip())      # Remove leading and trailing whitespace
print(text.lower())      # Convert to lowercase
print(text.upper())      # Convert to uppercase
print(text.title())      # Capitalize each word
print(text.replace("Python", "C#"))  # Replace substring
print(text.find("Python"))           # Find index of substring (-1 if not found)
print(text.startswith("  Hello"))    # Check if starts with
print(text.endswith("World!  "))     # Check if ends with
print("123abc".isalnum())            # Check alphanumeric
print("123".isdigit())               # Check digits only
print("abc".isalpha())               # Check alphabetic only
# 4. Joining and Splitting
words = ["Python", "is", "awesome"]
sentence = " ".join(words)    # Join list into a string with spaces
print(sentence)				 # Output: Python is awesome
split_words = sentence.split(" ")  # Split string back into list
print(split_words)

length = [3, 5, 7]
sentence = "#".join(length)  # ❌ TypeError: expected str, got int, join would always the iterable elements string
length = [3, 5, 7]
sentence = "#".join(map(str, length))  # ✅ "3#5#7"
sentence = "#".join([str(x) for x in length]) #Alternatively:
print(sentence)  # Output: 3#5#7

csv = "3#5#7"
split_numbers = csv.split("#") # Split a string using custom delimiter
print(split_numbers)  # Output: ['3', '5', '7']

Q3 - Simulation

25 - 40 lines of code, aim to solve in 15 - 20 minutes

54. Spiral Matrix

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        #spiral order, from outer circle to inner circle
        #simulate boundary, use smth to record index
        res = []
        top,bottom = 0, len(matrix)-1
        left,right = 0, len(matrix[0])-1
        order_state = "right"
        while len(res) < (len(matrix) * len(matrix[0])):
            if order_state == "right":
                for i in range(left, right+1): # 123
                    res.append(matrix[top][i])
                order_state = "bottom"
                top += 1
            elif order_state == "bottom": # 69
                for j in range(top, bottom+1):
                    res.append(matrix[j][right])
                order_state = "left"
                right-=1
            elif order_state == "left":
                for i in range(right,left-1, -1): #8 7
                    res.append(matrix[bottom][i])
                order_state = "up"
                bottom -= 1
            elif order_state == "up":
                # print(bottom,top,left)
                for j in range(bottom, top-1, -1): # 4
                    res.append(matrix[j][left])
                order_state = "right"
                #increment the boundary
                left += 1
            # print(res)
        return res

59. Spiral Matrix II

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        #generate in spiral order

        # define the boundary
        res = [[0]*n for _ in range(n)]

        # print(res)
        left, right = 0, n
        top, bottom = 0, n
        count = 1
        state = "right"
        while count <= (n*n):
            if state == "right":
                for i in range(left, right):
                    res[top][i] = count
                    count += 1
                state = "bottom"
                top += 1
            elif state == "bottom":
                for i in range(top, bottom):
                    res[i][right-1] = count
                    count += 1
                right -= 1
                state = "left"
            elif state == "left":
                for i in range(right-1, left-1,-1):
                    res[bottom-1][i] = count
                    count += 1
                bottom -= 1
                state = "up"
            elif state == "up":
                for i in range(bottom-1, top-1,-1):
                    res[i][left] = count
                    count += 1
                left += 1
                state = "right"
            print(res)
        return res

* 48. Rotate Image

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        #first transpose then mirror, also in place is hard
        n = len(matrix)
        def transpose(matrix):
            for i in range(len(matrix)):
                for j in range(i):
                    matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        transpose(matrix)
        # print(matrix)
        def mirror(matrix):
            for i in range(n):
                for j in range(n//2):
                    matrix[i][j],matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
        mirror(matrix)

* 498. Diagonal Traverse

Got a similar one in the q3. Which request traverse 4 directions.

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        # feel like just going through up and down ?
        res = []
        state = "up"
        r, c = 0, 0
        m = len(mat)
        n = len(mat[0])
        def isvalid(r, c):
            if 0 <= r < m and 0 <= c < n:
                return True
            else:
                return False
        #change each state based on the valid condition
        while len(res) < (m *n):
            if state == "up":
                while isvalid(r, c):
                    res.append(mat[r][c])
                    r -= 1
                    c += 1 
                r += 1
                c -= 1     
                state = "down"
                if c < (n-1):
                    c += 1
                else:
                    r += 1
            elif state == "down":
                while isvalid(r, c):
                    res.append(mat[r][c])
                    r += 1
                    c -= 1
                r -= 1
                c += 1
                state = "up"
                if r < (m-1):
                    r += 1
                else:
                    c += 1
            # print(res, r, c)
        return res

566. Reshape the Matrix

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        #if legal
        m = len(mat)
        n = len(mat[0])
        if not m *n == r *c: return mat

        res = [[0] *c for _ in range(r)]

        # print(res)
        flat = []
        for i in range(m):
            for j in range(n):
                flat.append(mat[i][j])
        
        for i in range(len(flat)):
            # 12
            # if i:
            row = i // c
            col = i % c
            res[row][col] = flat[i]
            # print(res,row,col)
            # else:
            #     res[0][0] = flat[i]
            
        return res

766. Toeplitz Matrix

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m, n = len(matrix), len(matrix[0])
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] != matrix[i - 1][j - 1]:
                    return False
        
        return True

835. Image Overlap

from collections import defaultdict
from typing import List

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        ones1 = []
        ones2 = []

        # Step 1: Record positions of 1s
        for i in range(n):
            for j in range(n):
                if img1[i][j] == 1:
                    ones1.append((i, j))
                if img2[i][j] == 1:
                    ones2.append((i, j))

        # Step 2: Count all translation vectors from img1 -> img2
        vector_count = defaultdict(int)
        for x1, y1 in ones1:
            for x2, y2 in ones2:
                dx = x2 - x1
                dy = y2 - y1
                vector_count[(dx, dy)] += 1
            print(vector_count)
        # Step 3: Return the maximum overlap
        return max(vector_count.values() or [0])

2373. Largest Local Values in a Matrix

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        maxLocal = [[0] * (n - 2) for _ in range(n - 2)]

        for i in range(1, n - 1):
            for j in range(1, n - 1):
                tempMax = float('-inf')
                # Traverse the 3x3 subgrid centered at (i, j)
                for r in range(i - 1, i + 2):
                    for c in range(j - 1, j + 2):
                        tempMax = max(tempMax, grid[r][c])
                maxLocal[i - 1][j - 1] = tempMax

        return maxLocal

867. Transpose Matrix

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        
        m, n = len(matrix), len(matrix[0])
        trans = [[0] * m for _ in range(n)]

        for i in range(m):
            for j in range(n):
                trans[j][i] = matrix[i][j]

        return trans

68. Text Justification - Low chance

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        n = len(words)
        word_arr = []
        word_arr_len = []
        curr_len = 0
        temp = []
        temp_len = []
        
        for word in words:
            word_len = len(word)
            if word_len + curr_len + len(temp)-1 < maxWidth:
                temp.append(word)
                temp_len.append(len(word))
                curr_len += len(word)
            else:
                word_arr.append(temp)
                word_arr_len.append(temp_len)
                curr_len = len(word)
                temp = [word]
                temp_len = [len(word)]
        word_arr.append(temp)
        word_arr_len.append(temp_len)
        #now justify the length, handle the last row separately
        for i in range(len(word_arr)):
            remain_space = maxWidth - sum(word_arr_len[i])
            # print(remain_space)
            empty_slot = len(word_arr[i]) - 1
            if i != len(word_arr)-1 and empty_slot != 0:
                for j in range(remain_space): # add space after equally
                    insert_index = j % empty_slot
                    word_arr[i][insert_index] += ' '
            elif empty_slot == 0:
                for _ in range(remain_space):
                    word_arr[i][-1] += ' '
            
            else:
                for j in range(empty_slot):
                    word_arr[i][j] += ' '
                
                for _ in range(remain_space - empty_slot):
                    word_arr[i][-1] += ' '
        res = []
        for i in range(len(word_arr)):
            res.append(''.join(word_arr[i]))

        print(word_arr, word_arr_len)
        return res

Q4 - Algorithm

20 - 35 lines of code.

3160. Find the Number of Distinct Colors Among the Balls

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        # hashmap -> 1 -> 1
        color_count = defaultdict(int) # color: count
        # ball color can get replaced
        # hashmap: list
        color_index = {} # ball: color
        res = []
        for query in queries:
            x, y = query
            if x in color_index:
                color = color_index[x]
                color_count[color] -= 1
                if color_count[color] == 0:
                    del color_count[color]
                color_index[x] = y
                color_count[y] += 1
            else:
                color_index[x] = y
                color_count[y] += 1
            res.append(len(color_count))
        return res

3159. Find Occurrences of an Element in an Array

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        # put the ans in the res index list -> brute force, use a loop
        # list[3]1 [index:]

        index_ls = []
        res = []
        for i,num in enumerate(nums):
            if num == x:
                index_ls.append(i)

        print(index_ls)
        for query in queries:
            if len(index_ls) >= query:
                res.append(index_ls[query-1])
            else:
                res.append(-1)
        return res

532. K-diff Pairs in an Array

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        freq = Counter(nums)
        res = 0

        for num in freq:
            if k !=0 and num + k in freq:
                res += 1
            
            if k == 0 and freq[num] > 1:
                res += 1
        
        return res

1248. Count Number of Nice Subarrays

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        left = 0
        n = len(nums)
        q_size = 0
        count = 0
        move = 0
        for right, num in enumerate(nums):
            if num % 2 != 0:
                q_size += 1
            
            if q_size == k:
                #need to shrink the window but also count the moves
                move = 0
                while q_size == k:
                    q_size -= nums[left] % 2 # if odd will give a result 1 and end the loop
                    move += 1 # 1 subarray
                    left += 1
            count += move
            print(num,count)

        return count

923. 3Sum With Multiplicity

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        f_count = Counter()
        n = len(arr)
        res = 0
        MOD = 10 ** 9 + 7
        for second in range(n):
            for third in range(second+1, n):
                find = target - arr[second] - arr[third]
                if find in f_count:
                    res += f_count[find] 
            #update the first index at the end to ensure the order access
            f_count[arr[second]] += 1
        
        return res % MOD

954. Array of Doubled Pairs

class Solution:
    def canReorderDoubled(self, arr: List[int]) -> bool:
        #convert to abs

        freq =  Counter(arr)
        print(sorted(freq, key=abs)) #output a list

        for num in sorted(freq, key=abs):
            if freq[num * 2] < freq[num]:
                return False

            freq[num*2] -= freq[num]
        return True

2131. Longest Palindrome by Concatenating Two Letter Words

from collections import Counter
from typing import List

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        word_count = Counter(words)
        count = 0

        for word in word_count.keys():
            rev = word[::-1]

            if word[0] == word[1]:
                # symmetric case like "gg"
                pairs = word_count[word] // 2
                count += pairs * 4
                word_count[word] -= pairs * 2
            elif rev in word_count:
                # asymmetric pair like "ab" and "ba"
                pairs = min(word_count[word], word_count[rev])
                count += pairs * 4
                # del word_count[word]
                # del word_count[rev]
                word_count[word] = 0
                word_count[rev] = 0

        # After all pairing, try to use a center word like "gg"
        for word in word_count:
            if word[0] == word[1] and word_count[word] > 0:
                count += 2
                break

        return count

← All notes