Algorithm A: O(n)      - Linear time
Algorithm B: O(n²)     - Quadratic time

Input: 1,000 items
Algorithm A: 1,000 operations (1ms)
Algorithm B: 1,000,000 operations (1 second)

Input: 10,000 items
Algorithm A: 10,000 operations (10ms)
Algorithm B: 100,000,000 operations (100 seconds!)

def get_first_element(arr):
    """Always takes same time, regardless of array size"""
    return arr[0]  # One operation

# n=10 or n=1,000,000 → Same time

def binary_search(arr, target):
    """Halves search space each iteration"""
    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

# n=1,000 → 10 iterations
# n=1,000,000 → 20 iterations (doubles size, adds 1 iteration)

def find_max(arr):
    """Must check every element"""
    max_val = arr[0]
    
    for num in arr:  # n iterations
        if num > max_val:
            max_val = num
    
    return max_val

# n=1,000 → 1,000 operations
# n=1,000,000 → 1,000,000 operations

def merge_sort(arr):
    """Divide and conquer - splits log n times, merges n elements each"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # log n splits
    right = merge_sort(arr[mid:])
    
    return merge(left, right)      # n operations per level

# Best general-purpose sorting complexity

def bubble_sort(arr):
    """Nested loops - for each element, check all others"""
    n = len(arr)
    
    for i in range(n):           # n iterations
        for j in range(n - i - 1):  # n iterations
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    return arr

# n=1,000 → 1,000,000 operations

def fibonacci_naive(n):
    """Recalculates same values repeatedly"""
    if n <= 1:
        return n
    
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# n=20 → 21,891 calls
# n=30 → 2,692,537 calls
# n=40 → 331,160,281 calls (unusable!)

# O(1) Space - Constant
def sum_array(arr):
    total = 0  # Only one variable
    for num in arr:
        total += num
    return total

# O(n) Space - Linear
def double_array(arr):
    result = []  # New array of size n
    for num in arr:
        result.append(num * 2)
    return result

# O(n) Space - Recursion (call stack)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # n stack frames

# O(2n) → O(n)
for i in range(n):
    print(i)
for i in range(n):
    print(i)

# Still O(n), not O(2n)

# O(n² + n) → O(n²)
for i in range(n):           # O(n)
    print(i)

for i in range(n):           # O(n²)
    for j in range(n):
        print(i, j)

# O(n² + n) = O(n²) because n² dominates

# O(a + b), NOT O(n)
def process_two_arrays(arr1, arr2):
    for item in arr1:        # O(a)
        print(item)
    for item in arr2:        # O(b)
        print(item)

# O(a × b), NOT O(n²)
def nested_different_arrays(arr1, arr2):
    for item1 in arr1:       # O(a)
        for item2 in arr2:   # O(b)
            print(item1, item2)

# Array operations
arr = [1, 2, 3, 4, 5]

# O(1) - Access by index
print(arr[2])  # 3

# O(n) - Search
def find_element(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# O(1) - Append (amortized)
arr.append(6)

# O(n) - Insert at position (must shift elements)
arr.insert(2, 99)  # [1, 2, 99, 3, 4, 5, 6]

# O(n) - Delete (must shift elements)
arr.pop(2)  # Remove element at index 2

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_beginning(self, val):
        """O(1) insertion"""
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
    
    def search(self, val):
        """O(n) search"""
        current = self.head
        while current:
            if current.val == val:
                return True
            current = current.next
        return False
    
    def delete(self, val):
        """O(n) deletion"""
        if not self.head:
            return
        
        if self.head.val == val:
            self.head = self.head.next
            return
        
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next

# Hash table operations
hash_map = {}

# O(1) - Insert
hash_map['key'] = 'value'

# O(1) - Access
print(hash_map['key'])

# O(1) - Delete
del hash_map['key']

# Common patterns
def count_frequencies(arr):
    """Count element frequencies"""
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq

def two_sum(nums, target):
    """Find two numbers that sum to target"""
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """O(1) - Add to top"""
        self.items.append(item)
    
    def pop(self):
        """O(1) - Remove from top"""
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        """O(1) - View top without removing"""
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        return len(self.items) == 0

# Use case: Valid Parentheses
def is_valid_parentheses(s):
    """Check if brackets are balanced"""
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    
    return not stack

print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("([)]"))    # False

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """O(1) - Add to back"""
        self.items.append(item)
    
    def dequeue(self):
        """O(1) - Remove from front"""
        if not self.is_empty():
            return self.items.popleft()
        return None
    
    def peek(self):
        """O(1) - View front"""
        if not self.is_empty():
            return self.items[0]
        return None
    
    def is_empty(self):
        return len(self.items) == 0

# Use case: BFS
def bfs(graph, start):
    """Breadth-First Search"""
    visited = set()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)
    
    while not queue.is_empty():
        node = queue.dequeue()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)

import heapq

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def push(self, val):
        """O(log n) - Insert"""
        heapq.heappush(self.heap, val)
    
    def pop(self):
        """O(log n) - Extract minimum"""
        if self.heap:
            return heapq.heappop(self.heap)
        return None
    
    def peek(self):
        """O(1) - View minimum"""
        return self.heap[0] if self.heap else None

# Use case: Find K largest elements
def find_k_largest(nums, k):
    """Find K largest numbers efficiently"""
    # Use min heap of size k
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # Remove smallest
    
    return heap

print(find_k_largest([3, 2, 1, 5, 6, 4], 2))  # [5, 6]

Pass 1: [5,2,8,1] → [2,5,1,8] (5 and 2 swap, 8 and 1 swap)
Pass 2: [2,5,1,8] → [2,1,5,8] (5 and 1 swap)
Pass 3: [2,1,5,8] → [1,2,5,8] (2 and 1 swap)
Pass 4: [1,2,5,8] → [1,2,5,8] (no swaps, done!)

def bubble_sort(arr):
    """
    Time: O(n²) worst/average, O(n) best (already sorted)
    Space: O(1)
    Stable: Yes
    """
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        # Last i elements are already in place
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # If no swaps, array is sorted
        if not swapped:
            break
    
    return arr

# Example
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

def selection_sort(arr):
    """
    Time: O(n²) all cases
    Space: O(1)
    Stable: No
    """
    n = len(arr)
    
    for i in range(n):
        # Find minimum in remaining array
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap minimum with first position
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

[5,2,8,1]
Step 1: [5] [2,8,1] → [2,5] [8,1] (insert 2 before 5)
Step 2: [2,5] [8,1] → [2,5,8] [1] (8 already in place)
Step 3: [2,5,8] [1] → [1,2,5,8] (insert 1 at beginning)

def insertion_sort(arr):
    """
    Time: O(n²) worst/average, O(n) best
    Space: O(1)
    Stable: Yes
    
    Best for: Small arrays, nearly sorted data
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Move elements greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

[38,27,43,3] 
    ↓ Split
[38,27] [43,3]
    ↓ Split
[38] [27] [43] [3]
    ↓ Merge
[27,38] [3,43]
    ↓ Merge
[3,27,38,43]

def merge_sort(arr):
    """
    Time: O(n log n) all cases
    Space: O(n)
    Stable: Yes
    
    Best for: Stable sorting, linked lists, external sorting
    """
    if len(arr) <= 1:
        return arr
    
    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # Conquer (merge)
    return merge(left, right)

def merge(left, right):
    """Merge two sorted arrays"""
    result = []
    i = j = 0
    
    # Compare elements from both arrays
    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
    
    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# Example
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

[10,80,30,90,40,50,70] pivot=50
    ↓ Partition
[10,30,40] 50 [80,90,70]
    ↓ Recurse
[10,30,40] 50 [70,80,90]

def quick_sort(arr):
    """
    Time: O(n log n) average, O(n²) worst
    Space: O(log n) stack space
    Stable: No
    
    Best for: General purpose, in-place sorting
    """
    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 quick_sort(left) + middle + quick_sort(right)

# In-place version (more efficient)
def quick_sort_inplace(arr, low, high):
    """In-place quicksort"""
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)
    return arr

def partition(arr, low, high):
    """Partition array around pivot"""
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Usage
arr = [10, 7, 8, 9, 1, 5]
print(quick_sort_inplace(arr, 0, len(arr) - 1))
# [1, 5, 7, 8, 9, 10]

def heap_sort(arr):
    """
    Time: O(n log n) all cases
    Space: O(1)
    Stable: No
    
    Best for: Memory constrained, guaranteed O(n log n)
    """
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements from heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Swap
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    """Maintain heap property"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def counting_sort(arr):
    """
    Time: O(n + k) where k is range of input
    Space: O(k)
    Stable: Yes
    
    Best for: Small range of integers (0 to k)
    """
    if not arr:
        return arr
    
    # Find range
    max_val = max(arr)
    min_val = min(arr)
    range_size = max_val - min_val + 1
    
    # Count occurrences
    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1
    
    # Reconstruct sorted array
    result = []
    for i, freq in enumerate(count):
        result.extend([i + min_val] * freq)
    
    return result

# Example
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
# [1, 2, 2, 3, 3, 4, 8]

def linear_search(arr, target):
    """
    Time: O(n)
    Space: O(1)
    
    Use: Unsorted arrays, small datasets
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Works on any array
print(linear_search([3, 1, 4, 1, 5, 9], 5))  # 4

def binary_search(arr, target):
    """
    Time: O(log n)
    Space: O(1)
    
    REQUIRES: Sorted array
    """
    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  # Search right half
        else:
            right = mid - 1  # Search left half
    
    return -1  # Not found

# Recursive version
def binary_search_recursive(arr, target, left, right):
    """Recursive binary search"""
    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)

# Example
sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(sorted_arr, 7))  # 3

def find_first(arr, target):
    """Find first occurrence of target"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

print(find_first([1, 2, 2, 2, 3, 4], 2))  # 1

def find_last(arr, target):
    """Find last occurrence of target"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Keep searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

print(find_last([1, 2, 2, 2, 3, 4], 2))  # 3

def search_insert_position(arr, target):
    """Find position where target should be inserted"""
    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 left  # Insert position

print(search_insert_position([1, 3, 5, 6], 5))  # 2
print(search_insert_position([1, 3, 5, 6], 2))  # 1

def my_sqrt(x):
    """
    Find floor of square root using binary search
    Time: O(log x)
    """
    if x < 2:
        return x
    
    left, right = 1, x // 2
    
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        
        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return right  # Floor value

print(my_sqrt(8))  # 2 (floor of 2.828)

def two_sum_sorted(arr, target):
    """
    Find two numbers that sum to target in SORTED array
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum
    
    return []

# Example
print(two_sum_sorted([1, 2, 3, 4, 6], 6))  # [1, 2] (2 + 4 = 6)

def remove_duplicates(arr):
    """
    Remove duplicates from sorted array in-place
    Time: O(n), Space: O(1)
    """
    if not arr:
        return 0
    
    # Slow pointer: position for next unique element
    # Fast pointer: explores array
    slow = 0
    
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    
    return slow + 1  # Length of unique elements

# Example
arr = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(arr)
print(f"Unique elements: {arr[:length]}")  # [1, 2, 3, 4]

def has_cycle(head):
    """
    Floyd's Cycle Detection (Tortoise and Hare)
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next
    
    return False

def find_cycle_start(head):
    """Find where cycle begins"""
    # First detect cycle
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

def three_sum(nums):
    """
    Find all unique triplets that sum to 0
    Time: O(n²), Space: O(1)
    """
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Two pointers for remaining array
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

# Example
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

def max_sum_subarray(arr, k):
    """
    Find maximum sum of subarray of size k
    Time: O(n), Space: O(1)
    """
    if len(arr) < k:
        return None
    
    # Initial window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window
    for i in range(len(arr) - k):
        # Remove left element, add right element
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Example
print(max_sum_subarray([1, 4, 2, 10, 2, 3, 1, 0, 20], 4))
# 24 (subarray [2, 10, 2, 3])

def longest_substring_k_distinct(s, k):
    """
    Find length of longest substring with at most k distinct characters
    Time: O(n), Space: O(k)
    """
    if k == 0:
        return 0
    
    left = 0
    max_length = 0
    char_count = {}
    
    for right in range(len(s)):
        # Add right character
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # Shrink window if too many distinct chars
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example
print(longest_substring_k_distinct("eceba", 2))  # 3 ("ece")

def min_window_substring(s, t):
    """
    Find minimum window in s that contains all characters of t
    Time: O(n), Space: O(1)
    """
    from collections import Counter
    
    if not s or not t:
        return ""
    
    # Count characters in t
    dict_t = Counter(t)
    required = len(dict_t)
    
    # Sliding window
    left = right = 0
    formed = 0
    window_counts = {}
    
    # Result
    ans = float("inf"), None, None
    
    while right < len(s):
        # Add character from right
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1
        
        # Try to shrink window
        while left <= right and formed == required:
            # Update result
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            
            # Remove from left
            char = s[left]
            window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1
            
            left += 1
        
        right += 1
    
    return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

# Example
print(min_window_substring("ADOBECODEBANC", "ABC"))  # "BANC"

def factorial(n):
    """
    Classic recursion example
    Time: O(n), Space: O(n) call stack
    """
    # Base case
    if n <= 1:
        return 1
    
    # Recursive case
    return n * factorial(n - 1)

# Trace: factorial(5)
# 5 * factorial(4)
# 5 * (4 * factorial(3))
# 5 * (4 * (3 * factorial(2)))
# 5 * (4 * (3 * (2 * factorial(1))))
# 5 * (4 * (3 * (2 * 1)))
# 120

def fibonacci(n):
    """
    Multiple recursive calls (inefficient)
    Time: O(2^n), Space: O(n)
    """
    if n <= 1:
        return n
    
    return fibonacci(n - 1) + fibonacci(n - 2)

# Better with memoization
def fibonacci_memo(n, memo={}):
    """
    Optimized with memoization
    Time: O(n), Space: O(n)
    """
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

def power(x, n):
    """
    Efficient power calculation
    Time: O(log n), Space: O(log n)
    """
    if n == 0:
        return 1
    if n < 0:
        return 1 / power(x, -n)
    
    # Divide problem
    if n % 2 == 0:
        half = power(x, n // 2)
        return half * half
    else:
        return x * power(x, n - 1)

print(power(2, 10))  # 1024

def backtrack(path, choices):
    if is_solution(path):
        solutions.append(path[:])  # Found solution
        return
    
    for choice in choices:
        if is_valid(choice, path):
            # Make choice
            path.append(choice)
            
            # Recurse
            backtrack(path, choices)
            
            # Undo choice (backtrack)
            path.pop()

def permute(nums):
    """
    Generate all permutations
    Time: O(n! * n), Space: O(n)
    """
    result = []
    
    def backtrack(path, remaining):
        # Base case: complete permutation
        if not remaining:
            result.append(path[:])
            return
        
        # Try each remaining number
        for i in range(len(remaining)):
            # Choose
            path.append(remaining[i])
            
            # Explore
            backtrack(path, remaining[:i] + remaining[i+1:])
            
            # Un-choose (backtrack)
            path.pop()
    
    backtrack([], nums)
    return result

print(permute([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

def combine(n, k):
    """
    Generate all combinations of k numbers from 1 to n
    Time: O(C(n,k) * k), Space: O(k)
    """
    result = []
    
    def backtrack(start, path):
        # Base case
        if len(path) == k:
            result.append(path[:])
            return
        
        # Try numbers from start to n
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)  # i+1 ensures no duplicates
            path.pop()
    
    backtrack(1, [])
    return result

print(combine(4, 2))
# [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

def subsets(nums):
    """
    Generate all subsets
    Time: O(2^n * n), Space: O(n)
    """
    result = []
    
    def backtrack(start, path):
        # Add current subset
        result.append(path[:])
        
        # Try adding each remaining number
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

def solve_n_queens(n):
    """
    Place n queens on n×n board
    Time: O(n!), Space: O(n)
    """
    def is_safe(board, row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check upper left diagonal
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i, j = i - 1, j - 1
        
        # Check upper right diagonal
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i, j = i - 1, j + 1
        
        return True
    
    def backtrack(board, row):
        # Base case: all queens placed
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        # Try placing queen in each column
        for col in range(n):
            if is_safe(board, row, col):
                board[row][col] = 'Q'
                backtrack(board, row + 1)
                board[row][col] = '.'  # Backtrack
    
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(board, 0)
    return result

# Example: 4-Queens
solutions = solve_n_queens(4)
for solution in solutions:
    for row in solution:
        print(row)
    print()
# .Q..
# ...Q
# Q...
# ..Q.

# Naive recursion: O(2^n)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# Top-down DP (Memoization): O(n)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Bottom-up DP (Tabulation): O(n)
def fib_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]

# Space optimized: O(1) space
def fib_optimized(n):
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

def climb_stairs(n):
    """
    Number of ways to climb n stairs (1 or 2 steps at a time)
    Time: O(n), Space: O(n)
    """
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# Space optimized: O(1)
def climb_stairs_optimized(n):
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

def rob(nums):
    """
    Maximum money from non-adjacent houses
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    # prev2: max money up to i-2
    # prev1: max money up to i-1
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        # Rob current house or skip it
        current = max(prev2 + nums[i], prev1)
        prev2 = prev1
        prev1 = current
    
    return prev1

print(rob([2, 7, 9, 3, 1]))  # 12 (rob houses 0, 2, 4)

def coin_change(coins, amount):
    """
    Minimum coins needed to make amount
    Time: O(amount * len(coins)), Space: O(amount)
    """
    # dp[i] = min coins needed for amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 2, 5], 11))  # 3 (11 = 5 + 5 + 1)

def longest_common_subsequence(text1, text2):
    """
    Length of longest common subsequence
    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(text1), len(text2)
    
    # dp[i][j] = LCS of text1[0:i] and text2[0:j]
    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]

print(longest_common_subsequence("abcde", "ace"))  # 3 ("ace")

def knapsack(weights, values, capacity):
    """
    Maximum value with weight limit
    Time: O(n * capacity), Space: O(n * capacity)
    """
    n = len(weights)
    
    # dp[i][w] = max value with first i items and weight limit w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # Don't take item i-1
            dp[i][w] = dp[i-1][w]
            
            # Take item i-1 if it fits
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    return dp[n][capacity]

# Example
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))  # 9

def edit_distance(word1, word2):
    """
    Minimum operations to convert word1 to word2
    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(word1), len(word2)
    
    # dp[i][j] = min operations for word1[0:i] to word2[0:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # Delete all
    for j in range(n + 1):
        dp[0][j] = j  # Insert all
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],      # Delete
                    dp[i][j-1],      # Insert
                    dp[i-1][j-1]     # Replace
                )
    
    return dp[m][n]

print(edit_distance("horse", "ros"))  # 3

def activity_selection(activities):
    """
    Maximum non-overlapping activities
    Time: O(n log n), Space: O(1)
    """
    # Sort by end time
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

# Example
activities = [(0, 6), (1, 4), (3, 5), (5, 7), (8, 9), (5, 9)]
print(activity_selection(activities))
# [(1, 4), (5, 7), (8, 9)]

def can_jump(nums):
    """
    Can reach last index?
    Time: O(n), Space: O(1)
    """
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    
    return True

def jump_min_steps(nums):
    """
    Minimum jumps to reach end
    Time: O(n), Space: O(1)
    """
    if len(nums) <= 1:
        return 0
    
    jumps = 0
    current_max = 0
    next_max = 0
    
    for i in range(len(nums) - 1):
        next_max = max(next_max, i + nums[i])
        
        if i == current_max:
            jumps += 1
            current_max = next_max
            
            if current_max >= len(nums) - 1:
                break
    
    return jumps

print(jump_min_steps([2, 3, 1, 1, 4]))  # 2

import heapq
from collections import Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(text):
    """
    Build Huffman tree and encode text
    Time: O(n log n), Space: O(n)
    """
    if not text:
        return "", None
    
    # Count frequencies
    freq = Counter(text)
    
    # Build heap
    heap = [HuffmanNode(char, f) for char, f in freq.items()]
    heapq.heapify(heap)
    
    # Build Huffman tree
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        heapq.heappush(heap, merged)
    
    # Generate codes
    root = heap[0]
    codes = {}
    
    def generate_codes(node, code=""):
        if node:
            if node.char:  # Leaf node
                codes[node.char] = code
            generate_codes(node.left, code + "0")
            generate_codes(node.right, code + "1")
    
    generate_codes(root)
    
    # Encode text
    encoded = "".join(codes[char] for char in text)
    
    return encoded, root

text = "BCAADDDCCACACAC"
encoded, tree = huffman_encoding(text)
print(f"Original: {text}")
print(f"Encoded: {encoded}")

# Undirected graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Weighted graph
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 5)],
    'C': [('A', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

# 4 nodes (0-3)
adj_matrix = [
    [0, 1, 1, 0],  # Node 0 connects to 1, 2
    [1, 0, 0, 1],  # Node 1 connects to 0, 3
    [1, 0, 0, 1],  # Node 2 connects to 0, 3
    [0, 1, 1, 0]   # Node 3 connects to 1, 2
]

def dfs_recursive(graph, node, visited=None):
    """
    DFS using recursion
    Time: O(V + E), Space: O(V)
    """
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

def dfs_iterative(graph, start):
    """
    DFS using stack
    Time: O(V + E), Space: O(V)
    """
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            
            # Add neighbors to stack
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

from collections import deque

def bfs(graph, start):
    """
    BFS using queue
    Time: O(V + E), Space: O(V)
    """
    visited = set([start])
    queue = deque([start])
    level = {start: 0}
    
    while queue:
        node = queue.popleft()
        print(f"{node} (level {level[node]})")
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                level[neighbor] = level[node] + 1
    
    return visited, level

def shortest_path_unweighted(graph, start, end):
    """
    Find shortest path in unweighted graph
    Time: O(V + E), Space: O(V)
    """
    if start == end:
        return [start]
    
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                
                if neighbor == end:
                    return new_path
                
                visited.add(neighbor)
                queue.append((neighbor, new_path))
    
    return None  # No path exists

import heapq

def dijkstra(graph, start):
    """
    Shortest paths from start to all nodes
    Time: O((V + E) log V), Space: O(V)
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Priority queue: (distance, node)
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# Example
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 3, 'C': 2, 'D': 8}

def topological_sort_dfs(graph):
    """
    Topological ordering of DAG
    Time: O(V + E), Space: O(V)
    """
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        
        stack.append(node)
    
    # Visit all nodes
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]  # Reverse for topological order

def topological_sort_kahn(graph):
    """
    Kahn's algorithm (BFS approach)
    Time: O(V + E), Space: O(V)
    """
    # Calculate in-degrees
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
    
    # Start with nodes having 0 in-degree
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == len(graph) else None  # Cycle detected

class UnionFind:
    """
    Disjoint set with path compression and union by rank
    """
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n
    
    def find(self, x):
        """Find with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """Union by rank"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False
        
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        self.components -= 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

# Example: Number of connected components
def count_components(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.components

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

def inorder(root):
    """
    Left → Root → Right
    Time: O(n), Space: O(h)
    """
    if not root:
        return []
    
    result = []
    result.extend(inorder(root.left))
    result.append(root.val)
    result.extend(inorder(root.right))
    return result

def preorder(root):
    """
    Root → Left → Right
    Time: O(n), Space: O(h)
    """
    if not root:
        return []
    
    result = [root.val]
    result.extend(preorder(root.left))
    result.extend(preorder(root.right))
    return result

def postorder(root):
    """
    Left → Right → Root
    Time: O(n), Space: O(h)
    """
    if not root:
        return []
    
    result = []
    result.extend(postorder(root.left))
    result.extend(postorder(root.right))
    result.append(root.val)
    return result

# Iterative inorder
def inorder_iterative(root):
    """Iterative inorder traversal"""
    result = []
    stack = []
    current = root
    
    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Current must be None here
        current = stack.pop()
        result.append(current.val)
        
        # Visit right subtree
        current = current.right
    
    return result

def level_order(root):
    """
    Level by level traversal
    Time: O(n), Space: O(w) where w is max width
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        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

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        """
        Insert value into BST
        Time: O(h), Space: O(1)
        """
        if not self.root:
            self.root = TreeNode(val)
            return
        
        current = self.root
        while True:
            if val < current.val:
                if current.left:
                    current = current.left
                else:
                    current.left = TreeNode(val)
                    break
            else:
                if current.right:
                    current = current.right
                else:
                    current.right = TreeNode(val)
                    break
    
    def search(self, val):
        """
        Search for value in BST
        Time: O(h), Space: O(1)
        """
        current = self.root
        
        while current:
            if val == current.val:
                return True
            elif val < current.val:
                current = current.left
            else:
                current = current.right
        
        return False
    
    def delete(self, root, val):
        """
        Delete value from BST
        Time: O(h), Space: O(h)
        """
        if not root:
            return None
        
        if val < root.val:
            root.left = self.delete(root.left, val)
        elif val > root.val:
            root.right = self.delete(root.right, val)
        else:
            # Node with only one child or no child
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            
            # Node with two children
            # Get inorder successor (smallest in right subtree)
            min_node = root.right
            while min_node.left:
                min_node = min_node.left
            
            root.val = min_node.val
            root.right = self.delete(root.right, min_node.val)
        
        return root

def max_depth(root):
    """
    Maximum depth of tree
    Time: O(n), Space: O(h)
    """
    if not root:
        return 0
    
    return 1 + max(max_depth(root.left), max_depth(root.right))

def is_balanced(root):
    """
    Check if tree is height-balanced
    Time: O(n), Space: O(h)
    """
    def check(node):
        if not node:
            return True, 0
        
        left_balanced, left_height = check(node.left)
        if not left_balanced:
            return False, 0
        
        right_balanced, right_height = check(node.right)
        if not right_balanced:
            return False, 0
        
        # Check if current node is balanced
        balanced = abs(left_height - right_height) <= 1
        height = 1 + max(left_height, right_height)
        
        return balanced, height
    
    return check(root)[0]

def is_valid_bst(root):
    """
    Validate Binary Search Tree
    Time: O(n), Space: O(h)
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

def lowest_common_ancestor(root, p, q):
    """
    LCA in binary tree
    Time: O(n), Space: O(h)
    """
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    if left and right:
        return root
    
    return left if left else right

def kmp_search(text, pattern):
    """
    KMP string matching
    Time: O(n + m), Space: O(m)
    """
    if not pattern:
        return 0
    
    # Build LPS array
    def build_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 = build_lps(pattern)
    i = j = 0
    
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        
        if j == len(pattern):
            return i - j  # Pattern found
        elif i < len(text) and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return -1  # Pattern not found

print(kmp_search("ababcababa", "ababa"))  # 5

def rabin_karp(text, pattern):
    """
    String matching using rolling hash
    Time: O(nm) worst, O(n+m) average
    """
    if not pattern or len(pattern) > len(text):
        return -1
    
    # Prime number for hashing
    prime = 101
    pattern_len = len(pattern)
    
    # Calculate hash
    def calculate_hash(s):
        hash_val = 0
        for i, char in enumerate(s):
            hash_val += ord(char) * (prime ** i)
        return hash_val
    
    pattern_hash = calculate_hash(pattern)
    text_hash = calculate_hash(text[:pattern_len])
    
    for i in range(len(text) - pattern_len + 1):
        if pattern_hash == text_hash:
            # Double check (hash collision possible)
            if text[i:i + pattern_len] == pattern:
                return i
        
        # Roll the hash
        if i < len(text) - pattern_len:
            text_hash -= ord(text[i])
            text_hash //= prime
            text_hash += ord(text[i + pattern_len]) * (prime ** (pattern_len - 1))
    
    return -1

def is_palindrome(s):
    """
    Check if string is palindrome
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

def longest_palindrome_expand(s):
    """
    Find longest palindromic substring
    Time: O(n²), Space: O(1)
    """
    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]
    
    longest = ""
    
    for i in range(len(s)):
        # Odd length palindromes
        palindrome1 = expand_around_center(i, i)
        # Even length palindromes
        palindrome2 = expand_around_center(i, i + 1)
        
        # Update longest
        for p in [palindrome1, palindrome2]:
            if len(p) > len(longest):
                longest = p
    
    return longest

print(longest_palindrome_expand("babad"))  # "bab" or "aba"

# Basic operations
a = 5  # 101 in binary
b = 3  # 011 in binary

print(a & b)   # 1 (001) - AND
print(a | b)   # 7 (111) - OR  
print(a ^ b)   # 6 (110) - XOR
print(~a)      # -6 (inverts all bits)
print(a << 1)  # 10 (1010) - Left shift
print(a >> 1)  # 2 (10) - Right shift

def get_bit(num, i):
    """Get i-th bit"""
    return (num >> i) & 1

def set_bit(num, i):
    """Set i-th bit to 1"""
    return num | (1 << i)

def clear_bit(num, i):
    """Clear i-th bit to 0"""
    return num & ~(1 << i)

def toggle_bit(num, i):
    """Toggle i-th bit"""
    return num ^ (1 << i)

def count_bits(n):
    """Count number of 1 bits"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def is_power_of_two(n):
    """Check if n is power of 2"""
    return n > 0 and (n & (n - 1)) == 0

def find_single_number(nums):
    """
    Find number that appears once (others appear twice)
    Time: O(n), Space: O(1)
    """
    result = 0
    for num in nums:
        result ^= num  # XOR cancels duplicates
    return result

print(find_single_number([4, 1, 2, 1, 2]))  # 4

def is_prime(n):
    """
    Check if number is prime
    Time: O(√n)
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    
    return True

def sieve_of_eratosthenes(n):
    """
    Find all primes up to n
    Time: O(n log log n), Space: O(n)
    """
    if n < 2:
        return []
    
    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]:
            # Mark multiples as not prime
            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]]

print(sieve_of_eratosthenes(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def gcd(a, b):
    """
    Greatest Common Divisor (Euclidean algorithm)
    Time: O(log min(a, b))
    """
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Least Common Multiple"""
    return abs(a * b) // gcd(a, b)

def extended_gcd(a, b):
    """
    Extended Euclidean algorithm
    Returns (gcd, x, y) where ax + by = gcd
    """
    if a == 0:
        return b, 0, 1
    
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    
    return gcd, x, y

def mod_pow(base, exp, mod):
    """
    Fast modular exponentiation
    Time: O(log exp)
    """
    result = 1
    base = base % mod
    
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp >> 1
        base = (base * base) % mod
    
    return result

def mod_inverse(a, mod):
    """
    Modular multiplicative inverse
    Returns x where (a * x) % mod = 1
    """
    gcd, x, _ = extended_gcd(a, mod)
    
    if gcd != 1:
        return None  # Inverse doesn't exist
    
    return (x % mod + mod) % mod

def factorial(n):
    """Calculate n!"""
    if n <= 1:
        return 1
    
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def nCr(n, r):
    """
    Binomial coefficient (n choose r)
    Time: O(r)
    """
    if r > n:
        return 0
    if r == 0 or r == n:
        return 1
    
    # Optimize by using smaller r
    r = min(r, n - r)
    
    result = 1
    for i in range(r):
        result *= (n - i)
        result //= (i + 1)
    
    return result

def pascal_triangle(n):
    """
    Generate Pascal's triangle
    Time: O(n²), Space: O(n²)
    """
    triangle = []
    
    for i in range(n):
        row = [1]
        if triangle:
            for j in range(len(triangle[-1]) - 1):
                row.append(triangle[-1][j] + triangle[-1][j + 1])
            row.append(1)
        triangle.append(row)
    
    return triangle

# Example
for row in pascal_triangle(5):
    print(row)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]