Dynamic Programing

Coin Change Problem

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Predict the Winner

def predict_winner(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = nums[i]
    for L in range(2, n + 1):
        for i in range(n - L + 1):
            j = i + L - 1
            dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
    return dp[0][n - 1] >= 0

Ugly Number II

def nth_ugly_number(n):
    dp = [1]
    idx2 = idx3 = idx5 = 0
    while len(dp) < n:
        next2 = dp[idx2] * 2
        next3 = dp[idx3] * 3
        next5 = dp[idx5] * 5
        next_val = min(next2, next3, next5)
        dp.append(next_val)
        if next_val == next2:
            idx2 += 1
        if next_val == next3:
            idx3 += 1
        if next_val == next5:
            idx5 += 1
    return dp[-1]

Binary Search

Search Insert Position

def search_insert(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left

Graph Algorithms

Number of Islands

def num_islands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
            grid[i][j] = '0'
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

Backtracking

N-Queans Problem

def solve_n_queens(n):
    def backtrack(row, cols, diag1, diag2, board, res):
        if row == n:
            res.append([''.join(row) for row in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            board[row][col] = 'Q'
            backtrack(row + 1, cols | {col}, diag1 | {row - col}, diag2 | {row + col}, board, res)
            board[row][col] = '.'
    
    res = []
    board = [['.'] * n for _ in range(n)]
    backtrack(0, set(), set(), set(), board, res)
    return res