Algorithms Cheatsheet

• LeetCode (leetcode.com)
• HackerRank
• GeeksforGeeks
• Visualgo

# Quick Sort Implementation
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# Merge Sort Implementation
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Binary Search Implementation
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Linear Search Implementation
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Binary Search (Recursive)
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# Factorial Recursion
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Fibonacci Recursion
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# N-Queens Backtracking
def solve_n_queens(n):
    def is_safe(board, row, col):
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == abs(i - row):
                return False
        return True
    
    def backtrack(board, row):
        if row == n:
            return [board[:]]
        solutions = []
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solutions.extend(backtrack(board, row + 1))
        return solutions
    
    return backtrack([0] * n, 0)

# Karatsuba Multiplication
def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    
    a = x // 10**m
    b = x % 10**m
    c = y // 10**m
    d = y % 10**m
    
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_bc = karatsuba(a + b, c + d) - ac - bd
    
    return ac * 10**(2*m) + ad_bc * 10**m + bd

# Closest Pair of Points
def closest_pair(points):
    if len(points) <= 3:
        return min_distance_brute_force(points)
    
    mid = len(points) // 2
    left = points[:mid]
    right = points[mid:]
    
    d1 = closest_pair(left)
    d2 = closest_pair(right)
    d = min(d1, d2)
    
    # Check strip
    strip = [p for p in points if abs(p[0] - points[mid][0]) < d]
    return min(d, strip_closest(strip, d))

# Activity Selection Problem
def activity_selection(start, finish):
    n = len(start)
    activities = []
    i = 0
    activities.append(i)
    
    for j in range(1, n):
        if start[j] >= finish[i]:
            activities.append(j)
            i = j
    
    return activities

# Fractional Knapsack
def fractional_knapsack(values, weights, capacity):
    items = [(values[i], weights[i], values[i]/weights[i]) for i in range(len(values))]
    items.sort(key=lambda x: x[2], reverse=True)
    
    total_value = 0
    for value, weight, ratio in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += ratio * capacity
            break
    
    return total_value

# Huffman Coding
import heapq
def huffman_coding(freq):
    heap = [[f, [char, ""]] for char, f in freq.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return heap[0][1:]

# Fibonacci with DP
def fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Longest Common Subsequence
def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

# 0/1 Knapsack
def knapsack_01(values, weights, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

# BFS Implementation
from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# DFS Implementation
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Dijkstra's Algorithm
import heapq
def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# Topological Sort
def topological_sort(graph):
    def dfs(node):
        visited.add(node)
        visiting.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor in visiting:
                return False  # Cycle detected
            if neighbor not in visited:
                if not dfs(neighbor):
                    return False
        
        visiting.remove(node)
        result.append(node)
        return True
    
    visited = set()
    visiting = set()
    result = []
    
    for node in graph:
        if node not in visited:
            if not dfs(node):
                return []  # Cycle detected
    
    return result[::-1]

# Tree Node Definition
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

# Inorder Traversal
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

# Preorder Traversal
def preorder_traversal(root):
    if root:
        print(root.val, end=' ')
        preorder_traversal(root.left)
        preorder_traversal(root.right)

# Postorder Traversal
def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val, end=' ')

# Level Order Traversal (BFS)
from collections import deque
def level_order_traversal(root):
    if not root:
        return []
    
    queue = deque([root])
    result = []
    
    while queue:
        level = []
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

# BST Insert
def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    
    return root

# KMP Algorithm
def kmp_search(text, pattern):
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
    
    lps = compute_lps(pattern)
    i = j = 0
    matches = []
    
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == len(pattern):
            matches.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return matches

# Longest Palindromic Substring
def longest_palindrome(s):
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    if len(s) < 2:
        return s
    
    longest = ""
    for i in range(len(s)):
        # Odd length palindrome
        palindrome1 = expand_around_center(i, i)
        # Even length palindrome
        palindrome2 = expand_around_center(i, i + 1)
        
        if len(palindrome1) > len(longest):
            longest = palindrome1
        if len(palindrome2) > len(longest):
            longest = palindrome2
    
    return longest

# Rabin-Karp Algorithm
def rabin_karp(text, pattern):
    d = 256  # Number of characters in input alphabet
    q = 101  # A prime number
    
    M = len(pattern)
    N = len(text)
    p = 0  # Hash value for pattern
    t = 0  # Hash value for text
    h = 1
    
    # Calculate h = pow(d, M-1) % q
    for i in range(M - 1):
        h = (h * d) % q
    
    # Calculate hash value of pattern and first window of text
    for i in range(M):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q
    
    # Slide the pattern over text one by one
    for i in range(N - M + 1):
        if p == t:
            # Check for characters one by one
            for j in range(M):
                if text[i + j] != pattern[j]:
                    break
            else:
                return i
        
        if i < N - M:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + M])) % q
            if t < 0:
                t = t + q
    
    return -1

# Common Bit Operations
def count_set_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

def get_single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

def reverse_bits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

def add_without_plus(a, b):
    while b:
        carry = a & b
        a = a ^ b
        b = carry << 1
    return a

# Bit manipulation tricks
def power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0

def count_trailing_zeros(n):
    count = 0
    while n and (n & 1) == 0:
        count += 1
        n >>= 1
    return count

def swap_without_temp(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b

# GCD using Euclidean Algorithm
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# LCM using GCD
def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# Sieve of Eratosthenes
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    
    return [i for i in range(n + 1) if is_prime[i]]

# Fast Exponentiation
def fast_power(base, exponent, modulus=None):
    result = 1
    base = base % modulus if modulus else base
    
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus if modulus else result * base
        base = (base * base) % modulus if modulus else base * base
        exponent //= 2
    
    return result

# Prime Factorization
def prime_factorization(n):
    factors = []
    d = 2
    
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    
    if n > 1:
        factors.append(n)
    
    return factors

# Extended Euclidean Algorithm
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return gcd, y - (b // a) * x, x

# Common Complexity Examples
def constant_time():
    return 1  # O(1)

def logarithmic_time(n):
    i = 1
    while i < n:
        i *= 2  # O(log n)

def linear_time(n):
    for i in range(n):
        pass  # O(n)

def linearithmic_time(n):
    for i in range(n):
        j = 1
        while j < n:
            j *= 2  # O(n log n)

def quadratic_time(n):
    for i in range(n):
        for j in range(n):
            pass  # O(n²)

def exponential_time(n):
    if n <= 1:
        return 1
    return exponential_time(n-1) + exponential_time(n-2)  # O(2ⁿ)

# Space Complexity Examples
def constant_space():
    a = 1
    b = 2  # O(1)

def linear_space(n):
    arr = [0] * n  # O(n)

def quadratic_space(n):
    matrix = [[0] * n for _ in range(n)]  # O(n²)