Python3 LeetCode Complete Wiki

Basic Data Structures
Collections Module
Heaps (Priority Queues)
Trees
Graphs
Strings
Common Patterns
Built-in Functions
Type Hints Reference
Complexity Cheat Sheet

Basic Data Structures

Lists (Arrays)

from typing import List

# Initialization
arr: List[int] = []
arr: List[int] = [1, 2, 3, 4, 5]
arr: List[int] = [0] * n  # n zeros

# Common Operations - O(1)
arr.append(x)           # Add to end
last = arr.pop()        # Remove and return last
arr[-1]                 # Access last element

# Common Operations - O(n)
arr.insert(i, x)        # Insert at index i
arr.remove(x)           # Remove first occurrence of x
arr.pop(i)              # Remove and return element at index i

# Slicing - O(k) where k is slice size
arr[start:end]          # Elements from start to end-1
arr[::-1]               # Reverse list
arr[::2]                # Every 2nd element

# List Comprehension
squares = [x**2 for x in range(10)]
evens = [x for x in arr if x % 2 == 0]
matrix = [[0] * cols for _ in range(rows)]  # 2D array

# Sorting
arr.sort()              # In-place, O(n log n)
arr.sort(reverse=True)  # Descending
arr.sort(key=lambda x: x[1])  # Sort by custom key
sorted_arr = sorted(arr)  # Returns new sorted list

# Common Methods
len(arr)                # Length
min(arr), max(arr)      # Min/max elements
sum(arr)                # Sum of elements
arr.count(x)            # Count occurrences
arr.index(x)            # First index of x
arr.reverse()           # Reverse in-place

# Example: Two Pointer Technique
def reverseString(s: List[str]) -> None:
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

Dictionaries (Hash Maps)

from typing import Dict

# Initialization
freq: Dict[str, int] = {}
freq: Dict[str, int] = {'a': 1, 'b': 2}
freq: Dict[str, int] = dict()

# Common Operations - O(1) average
freq[key] = value       # Set/update
val = freq[key]         # Get (raises KeyError if not found)
val = freq.get(key)     # Returns None if not found
val = freq.get(key, 0)  # Returns 0 if not found
del freq[key]           # Delete key
freq.pop(key)           # Remove and return value

# Checking existence
if key in freq:         # O(1)
    pass

# Iterating
for key in freq:                    # Iterate keys
    pass
for value in freq.values():         # Iterate values
    pass
for key, value in freq.items():     # Iterate key-value pairs
    pass

# Common Methods
len(freq)               # Number of key-value pairs
freq.keys()             # View of keys
freq.values()           # View of values
freq.items()            # View of (key, value) tuples
freq.clear()            # Remove all items

# Example: Two Sum
def twoSum(nums: List[int], target: int) -> List[int]:
    seen: Dict[int, int] = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Example: Group Anagrams
def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups: Dict[tuple, List[str]] = {}
    for s in strs:
        key = tuple(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    return list(groups.values())

Sets (Hash Sets)

from typing import Set

# Initialization
s: Set[int] = set()
s: Set[int] = {1, 2, 3, 4}
s: Set[int] = set([1, 2, 3])

# Common Operations - O(1) average
s.add(x)                # Add element
s.remove(x)             # Remove (raises KeyError if not found)
s.discard(x)            # Remove (no error if not found)
s.pop()                 # Remove and return arbitrary element

# Checking existence
if x in s:              # O(1)
    pass

# Set Operations
s1.union(s2)            # s1 | s2
s1.intersection(s2)     # s1 & s2
s1.difference(s2)       # s1 - s2
s1.symmetric_difference(s2)  # s1 ^ s2

# Common Methods
len(s)                  # Size
s.clear()               # Remove all elements

# Example: Longest Consecutive Sequence
def longestConsecutive(nums: List[int]) -> int:
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        if num - 1 not in num_set:  # Start of sequence
            current = num
            streak = 1
            
            while current + 1 in num_set:
                current += 1
                streak += 1
            
            longest = max(longest, streak)
    
    return longest

Tuples

from typing import Tuple

# Initialization (Immutable)
t: Tuple[int, int] = (1, 2)
t: Tuple[int, ...] = (1, 2, 3, 4)  # Variable length

# Accessing
first = t[0]
last = t[-1]

# Unpacking
x, y = (1, 2)
x, y, *rest = (1, 2, 3, 4, 5)  # rest = [3, 4, 5]

# Common use: Dictionary keys (immutable)
positions: Dict[Tuple[int, int], str] = {}
positions[(0, 0)] = "origin"

# Example: Using tuple as key
def isValidSudoku(board: List[List[str]]) -> bool:
    seen: Set[Tuple[str, int, int]] = set()
    
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                num = board[i][j]
                if (('row', i, num) in seen or
                    ('col', j, num) in seen or
                    ('box', i//3, j//3, num) in seen):
                    return False
                seen.add(('row', i, num))
                seen.add(('col', j, num))
                seen.add(('box', i//3, j//3, num))
    
    return True

Collections Module

deque (Double-ended Queue)

from collections import deque
from typing import Deque

# Initialization
dq: Deque[int] = deque()
dq: Deque[int] = deque([1, 2, 3])
dq: Deque[int] = deque(maxlen=5)  # Fixed size

# Operations - O(1) for both ends
dq.append(x)            # Add to right
dq.appendleft(x)        # Add to left
dq.pop()                # Remove from right
dq.popleft()            # Remove from left

# Other Operations
dq.extend([1, 2, 3])    # Extend right
dq.extendleft([1, 2])   # Extend left (reversed)
dq.rotate(n)            # Rotate n steps right

# Example: Sliding Window Maximum
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq: Deque[int] = deque()  # Store indices
    result: List[int] = []
    
    for i, num in enumerate(nums):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements
        while dq and nums[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

# Example: BFS Template
def bfs(start):
    queue: Deque = deque([start])
    visited: Set = {start}
    
    while queue:
        node = queue.popleft()
        
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Counter (Frequency Counter)

from collections import Counter
from typing import Counter as CounterType

# Initialization
counter: CounterType[str] = Counter()
counter: CounterType[str] = Counter("hello")  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
counter: CounterType[int] = Counter([1, 2, 2, 3, 3, 3])

# Common Operations
counter['a'] += 1       # Increment (works even if key doesn't exist)
counter.most_common(n)  # n most common elements as [(elem, count), ...]
counter.elements()      # Iterator over elements (repeating each count times)

# Arithmetic operations
c1 + c2                 # Add counts
c1 - c2                 # Subtract (keep only positive)
c1 & c2                 # Intersection: min(c1[x], c2[x])
c1 | c2                 # Union: max(c1[x], c2[x])

# Example: Top K Frequent Elements
def topKFrequent(nums: List[int], k: int) -> List[int]:
    counter = Counter(nums)
    return [num for num, _ in counter.most_common(k)]

# Example: Valid Anagram
def isAnagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

# Example: Find All Anagrams
def findAnagrams(s: str, p: str) -> List[int]:
    result: List[int] = []
    p_count = Counter(p)
    window_count: CounterType[str] = Counter()
    
    for i, char in enumerate(s):
        window_count[char] += 1
        
        if i >= len(p):
            left_char = s[i - len(p)]
            window_count[left_char] -= 1
            if window_count[left_char] == 0:
                del window_count[left_char]
        
        if window_count == p_count:
            result.append(i - len(p) + 1)
    
    return result

defaultdict

from collections import defaultdict
from typing import DefaultDict, List

# Initialization with default factory
graph: DefaultDict[int, List[int]] = defaultdict(list)
freq: DefaultDict[str, int] = defaultdict(int)
groups: DefaultDict[str, List[str]] = defaultdict(list)

# Usage - no need to check if key exists
graph[1].append(2)      # Automatically creates empty list
freq['a'] += 1          # Automatically creates 0

# Example: Group Anagrams
def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups: DefaultDict[str, List[str]] = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

# Example: Build Adjacency List
def buildGraph(edges: List[List[int]]) -> DefaultDict[int, List[int]]:
    graph: DefaultDict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # For undirected graph
    return graph

Heaps (Priority Queues)

import heapq
from typing import List

# Python uses MIN heap by default
# For max heap, negate values

# Initialization
heap: List[int] = []
heapq.heapify(arr)      # Convert list to heap in-place, O(n)

# Operations - O(log n)
heapq.heappush(heap, item)      # Add item
smallest = heapq.heappop(heap)  # Remove and return smallest

# Other Operations
smallest = heap[0]              # Peek at smallest, O(1)
heapq.heappushpop(heap, item)   # Push then pop (efficient)
smallest = heapq.heapreplace(heap, item)  # Pop then push (efficient)

# n largest/smallest - O(n log k)
heapq.nlargest(k, iterable)
heapq.nsmallest(k, iterable)
heapq.nlargest(k, iterable, key=lambda x: x[1])  # Custom key

# Example: Kth Largest Element
def findKthLargest(nums: List[int], k: int) -> int:
    # Min heap of size k
    heap = nums[:k]
    heapq.heapify(heap)
    
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    
    return heap[0]

# Example: Merge K Sorted Lists
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists: List[ListNode]) -> ListNode:
    heap: List[tuple] = []
    
    # Initialize heap with first node from each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    
    dummy = ListNode()
    current = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

# Example: Top K Frequent Elements (Min Heap)
def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    heap: List[tuple] = []
    
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    
    return [num for freq, num in heap]

# Example: Max Heap (negate values)
def findKthSmallest(nums: List[int], k: int) -> int:
    # Max heap of size k (negate to simulate max heap)
    heap = [-x for x in nums[:k]]
    heapq.heapify(heap)
    
    for num in nums[k:]:
        if num < -heap[0]:
            heapq.heapreplace(heap, -num)
    
    return -heap[0]

# Example: Median Finder (Two Heaps)
class MedianFinder:
    def __init__(self):
        self.small: List[int] = []  # Max heap (negated)
        self.large: List[int] = []  # Min heap
    
    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        
        # Balance: ensure all in small <= all in large
        heapq.heappush(self.large, -heapq.heappop(self.small))
        
        # Balance sizes
        if len(self.small) < len(self.large):
            heapq.heappush(self.small, -heapq.heappop(self.large))
    
    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Trees

Binary Tree Node

from typing import Optional

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

# DFS Traversals

# Pre-order: Root -> Left -> Right
def preorder(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# In-order: Left -> Root -> Right (sorted for BST)
def inorder(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Post-order: Left -> Right -> Root
def postorder(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative DFS (Pre-order)
def preorderIterative(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    
    result: List[int] = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

# BFS (Level Order)
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    
    result: List[List[int]] = []
    queue: Deque[TreeNode] = deque([root])
    
    while queue:
        level: List[int] = []
        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

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

# Example: Validate BST
def isValidBST(root: Optional[TreeNode]) -> bool:
    def validate(node: Optional[TreeNode], low: float, high: float) -> bool:
        if not node:
            return True
        
        if not (low < node.val < high):
            return False
        
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
    
    return validate(root, float('-inf'), float('inf'))

# Example: Lowest Common Ancestor
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    
    return left if left else right

# Example: Serialize and Deserialize
def serialize(root: Optional[TreeNode]) -> str:
    def dfs(node):
        if not node:
            vals.append('#')
            return
        vals.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    
    vals: List[str] = []
    dfs(root)
    return ','.join(vals)

def deserialize(data: str) -> Optional[TreeNode]:
    def dfs():
        val = next(vals)
        if val == '#':
            return None
        node = TreeNode(int(val))
        node.left = dfs()
        node.right = dfs()
        return node
    
    vals = iter(data.split(','))
    return dfs()

Trie (Prefix Tree)

from typing import Dict

class TrieNode:
    def __init__(self):
        self.children: Dict[str, TrieNode] = {}
        self.is_end_of_word: bool = False

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

# Example: Word Search II (Trie + Backtracking)
def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    result: Set[str] = set()
    rows, cols = len(board), len(board[0])
    
    def backtrack(r: int, c: int, node: TrieNode, path: str):
        if node.is_end_of_word:
            result.add(path)
        
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        
        char = board[r][c]
        if char not in node.children or char == '#':
            return
        
        board[r][c] = '#'  # Mark visited
        next_node = node.children[char]
        
        for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            backtrack(r + dr, c + dc, next_node, path + char)
        
        board[r][c] = char  # Restore
    
    for r in range(rows):
        for c in range(cols):
            backtrack(r, c, trie.root, "")
    
    return list(result)

Graphs

Representations

from typing import List, Dict, Set, DefaultDict
from collections import defaultdict, deque

# Adjacency List (most common)
graph: Dict[int, List[int]] = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# Or with defaultdict
graph: DefaultDict[int, List[int]] = defaultdict(list)
graph[0].append(1)
graph[0].append(2)

# Edge List
edges: List[List[int]] = [[0, 1], [0, 2], [1, 3], [2, 3]]

# Adjacency Matrix (for dense graphs)
n = 4
matrix: List[List[int]] = [[0] * n for _ in range(n)]
matrix[0][1] = 1  # Edge from 0 to 1

# Build graph from edges
def buildGraph(n: int, edges: List[List[int]]) -> DefaultDict[int, List[int]]:
    graph: DefaultDict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # For undirected graph
    return graph

DFS (Depth-First Search)

# Recursive DFS
def dfs(node: int, graph: Dict[int, List[int]], visited: Set[int]):
    if node in visited:
        return
    
    visited.add(node)
    # Process node
    
    for neighbor in graph[node]:
        dfs(neighbor, graph, visited)

# Iterative DFS
def dfsIterative(start: int, graph: Dict[int, List[int]]) -> List[int]:
    visited: Set[int] = set()
    stack = [start]
    result: List[int] = []
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
        
        visited.add(node)
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    
    return result

# Example: Number of Connected Components
def countComponents(n: int, edges: List[List[int]]) -> int:
    graph = buildGraph(n, edges)
    visited: Set[int] = set()
    count = 0
    
    def dfs(node: int):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)
    
    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    
    return count

# Example: Course Schedule (Cycle Detection)
def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph: DefaultDict[int, List[int]] = defaultdict(list)
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    
    visited: Set[int] = set()
    visiting: Set[int] = set()
    
    def hasCycle(course: int) -> bool:
        if course in visiting:
            return True
        if course in visited:
            return False
        
        visiting.add(course)
        for prereq in graph[course]:
            if hasCycle(prereq):
                return True
        
        visiting.remove(course)
        visited.add(course)
        return False
    
    for course in range(numCourses):
        if hasCycle(course):
            return False
    
    return True

BFS (Breadth-First Search)

# Standard BFS
def bfs(start: int, graph: Dict[int, List[int]]) -> List[int]:
    visited: Set[int] = {start}
    queue: Deque[int] = deque([start])
    result: List[int] = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# BFS with Level Tracking
def bfsLevels(start: int, graph: Dict[int, List[int]]) -> Dict[int, int]:
    visited: Set[int] = {start}
    queue: Deque[Tuple[int, int]] = deque([(start, 0)])
    levels: Dict[int, int] = {start: 0}
    
    while queue:
        node, level = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                levels[neighbor] = level + 1
                queue.append((neighbor, level + 1))
    
    return levels

# Example: Shortest Path in Unweighted Graph
def shortestPath(start: int, end: int, graph: Dict[int, List[int]]) -> int:
    if start == end:
        return 0
    
    visited: Set[int] = {start}
    queue: Deque[Tuple[int, int]] = deque([(start, 0)])
    
    while queue:
        node, dist = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # No path found

# Example: Rotten Oranges (Multi-source BFS)
def orangesRotting(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue: Deque[Tuple[int, int]] = deque()
    fresh = 0
    
    # Find all rotten oranges and count fresh ones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    
    if fresh == 0:
        return 0
    
    minutes = 0
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if (0 <= nr < rows and 0 <= nc < cols and 
                    grid[nr][nc] == 1):
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        
        minutes += 1
    
    return minutes - 1 if fresh == 0 else -1

Union Find (Disjoint Set)

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        root_x, root_y = self.find(x), self.find(y)
        
        if root_x == root_y:
            return False  # Already connected
        
        # Union by rank
        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: int, y: int) -> bool:
        return self.find(x) == self.find(y)

# Example: Number of Connected Components
def countComponents(n: int, edges: List[List[int]]) -> int:
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.components

# Example: Redundant Connection
def findRedundantConnection(edges: List[List[int]]) -> List[int]:
    uf = UnionFind(len(edges) + 1)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []

Topological Sort

# Kahn's Algorithm (BFS-based)
def topologicalSort(n: int, edges: List[List[int]]) -> List[int]:
    graph: DefaultDict[int, List[int]] = defaultdict(list)
    indegree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    
    queue: Deque[int] = deque([i for i in range(n) if indegree[i] == 0])
    result: List[int] = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == n else []  # Check for cycle

# DFS-based Topological Sort
def topologicalSortDFS(n: int, edges: List[List[int]]) -> List[int]:
    graph: DefaultDict[int, List[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    
    visited: Set[int] = set()
    result: List[int] = []
    
    def dfs(node: int):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)
    
    for i in range(n):
        if i not in visited:
            dfs(i)
    
    return result[::-1]  # Reverse for topological order

Strings

# Basic Operations
s = "hello"
s[0]                    # 'h' - indexing
s[-1]                   # 'o' - last char
s[1:4]                  # 'ell' - slicing
s[::-1]                 # 'olleh' - reverse

# Immutable - create new strings
s.upper()               # 'HELLO'
s.lower()               # 'hello'
s.strip()               # Remove whitespace
s.replace('l', 'L')     # 'heLLo'

# Checking
s.isalpha()             # All alphabetic
s.isdigit()             # All digits
s.isalnum()             # Alphanumeric
s.startswith('he')      # True
s.endswith('lo')        # True

# Splitting and Joining
words = s.split()       # Split by whitespace
words = s.split(',')    # Split by delimiter
''.join(['a', 'b'])     # 'ab'
','.join(['a', 'b'])    # 'a,b'

# Finding
s.find('l')             # 2 (first index, -1 if not found)
s.index('l')            # 2 (first index, raises ValueError)
s.count('l')            # 2 (count occurrences)

# String Builder Pattern (efficient concatenation)
chars: List[str] = []
for char in "hello":
    chars.append(char.upper())
result = ''.join(chars)

# Example: Valid Palindrome
def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# Example: Longest Substring Without Repeating Characters
def lengthOfLongestSubstring(s: str) -> int:
    seen: Dict[str, int] = {}
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        
        seen[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example: Group Anagrams
def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups: DefaultDict[str, List[str]] = defaultdict(list)
    
    for s in strs:
        # Use sorted string as key
        key = ''.join(sorted(s))
        groups[key].append(s)
    
    return list(groups.values())

# Character frequency pattern
def characterFrequency(s: str) -> List[int]:
    freq = [0] * 26
    for char in s:
        freq[ord(char) - ord('a')] += 1
    return freq

Common Patterns

Sliding Window

# Fixed Size Window
def maxSumSubarray(arr: List[int], k: int) -> int:
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Variable Size Window
def minSubArrayLen(target: int, nums: List[int]) -> int:
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

# String Sliding Window
def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    target_count = Counter(t)
    window_count: DefaultDict[str, int] = defaultdict(int)
    
    have, need = 0, len(target_count)
    result = [-1, -1]
    result_len = float('inf')
    left = 0
    
    for right, char in enumerate(s):
        window_count[char] += 1
        
        if char in target_count and window_count[char] == target_count[char]:
            have += 1
        
        while have == need:
            # Update result
            if (right - left + 1) < result_len:
                result = [left, right]
                result_len = right - left + 1
            
            # Shrink window
            window_count[s[left]] -= 1
            if s[left] in target_count and window_count[s[left]] < target_count[s[left]]:
                have -= 1
            left += 1
    
    l, r = result
    return s[l:r+1] if result_len != float('inf') else ""

Two Pointers

# Opposite Ends
def twoSumSorted(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

# Same Direction (Fast and Slow)
def removeDuplicates(nums: List[int]) -> int:
    if not nums:
        return 0
    
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1

# Cycle Detection (Floyd's Algorithm)
def hasCycle(head: Optional[ListNode]) -> bool:
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

Backtracking

# Subsets
def subsets(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    
    def backtrack(start: int, path: List[int]):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

# Permutations
def permute(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    
    def backtrack(path: List[int]):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for num in nums:
            if num not in path:
                path.append(num)
                backtrack(path)
                path.pop()
    
    backtrack([])
    return result

# Combinations
def combine(n: int, k: int) -> List[List[int]]:
    result: List[List[int]] = []
    
    def backtrack(start: int, path: List[int]):
        if len(path) == k:
            result.append(path[:])
            return
        
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(1, [])
    return result

# N-Queens
def solveNQueens(n: int) -> List[List[str]]:
    result: List[List[str]] = []
    board = [['.'] * n for _ in range(n)]
    
    cols: Set[int] = set()
    diag1: Set[int] = set()  # r - c
    diag2: Set[int] = set()  # r + c
    
    def backtrack(row: int):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            # Place queen
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            backtrack(row + 1)
            
            # Remove queen
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result

Dynamic Programming

# 1D DP: Fibonacci
def fib(n: int) -> int:
    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
def fibOptimized(n: int) -> int:
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1

# Climbing Stairs
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1

# House Robber
def rob(nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev2, prev1 = 0, 0
    
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2, prev1 = prev1, curr
    
    return prev1

# Coin Change
def coinChange(coins: List[int], amount: int) -> int:
    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

# Longest Increasing Subsequence
def lengthOfLIS(nums: List[int]) -> int:
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 2D DP: Unique Paths
def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

# Longest Common Subsequence
def longestCommonSubsequence(text1: str, text2: str) -> int:
    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]

Binary Search

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

# Find First Occurrence
def findFirst(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

# Find Last Occurrence
def findLast(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Continue searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

# Search in Rotated Sorted Array
def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

# Find Minimum in Rotated Sorted Array
def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    
    return nums[left]

Built-in Functions

# Essential Built-ins for LeetCode

# Math
abs(-5)                 # 5
pow(2, 3)               # 8
min(1, 2, 3)            # 1
max([1, 2, 3])          # 3
sum([1, 2, 3])          # 6
divmod(10, 3)           # (3, 1) - quotient and remainder

# Type Conversions
int("123")              # 123
int("1010", 2)          # 10 (binary to decimal)
str(123)                # "123"
list("abc")             # ['a', 'b', 'c']
tuple([1, 2])           # (1, 2)

# Itertools (Combinatorics)
from itertools import combinations, permutations, product

list(combinations([1, 2, 3], 2))    # [(1, 2), (1, 3), (2, 3)]
list(permutations([1, 2, 3], 2))    # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
list(product([1, 2], [3, 4]))       # [(1, 3), (1, 4), (2, 3), (2, 4)]

# Range and Enumerate
for i in range(5):              # 0, 1, 2, 3, 4
    pass
for i in range(1, 5):           # 1, 2, 3, 4
    pass
for i in range(0, 10, 2):       # 0, 2, 4, 6, 8
    pass

for i, val in enumerate([10, 20, 30]):
    print(f"{i}: {val}")        # 0: 10, 1: 20, 2: 30

# Zip (Parallel Iteration)
names = ['Alice', 'Bob']
ages = [25, 30]
for name, age in zip(names, ages):
    print(f"{name}: {age}")

# Any and All
any([False, True, False])       # True (at least one True)
all([True, True, False])        # False (not all True)

# Filter and Map
evens = list(filter(lambda x: x % 2 == 0, [1, 2, 3, 4]))  # [2, 4]
squares = list(map(lambda x: x**2, [1, 2, 3]))            # [1, 4, 9]

# Sorted with Key
sorted([3, 1, 2])                           # [1, 2, 3]
sorted(['ab', 'a', 'abc'], key=len)         # ['a', 'ab', 'abc']
sorted([(1, 2), (1, 1), (2, 0)])            # [(1, 1), (1, 2), (2, 0)]
sorted([(1, 2), (1, 1), (2, 0)], key=lambda x: x[1])  # [(2, 0), (1, 1), (1, 2)]

# Reversed
for x in reversed([1, 2, 3]):   # 3, 2, 1
    pass

# Ord and Chr (Character/ASCII conversion)
ord('a')                # 97
chr(97)                 # 'a'
ord('A')                # 65

# Bit Manipulation
bin(5)                  # '0b101'
hex(15)                 # '0xf'
5 & 3                   # 1 (AND)
5 | 3                   # 7 (OR)
5 ^ 3                   # 6 (XOR)
~5                      # -6 (NOT)
5 << 1                  # 10 (left shift)
5 >> 1                  # 2 (right shift)

# Check bit at position
def getBit(num: int, i: int) -> bool:
    return (num & (1 << i)) != 0

# Set bit at position
def setBit(num: int, i: int) -> int:
    return num | (1 << i)

# Clear bit at position
def clearBit(num: int, i: int) -> int:
    return num & ~(1 << i)

Type Hints Reference

from typing import (
    List, Dict, Set, Tuple, Optional, Union, Any,
    Deque, DefaultDict, Counter as CounterType
)

# Basic Types
x: int = 5
y: float = 3.14
name: str = "Alice"
flag: bool = True

# Collections
numbers: List[int] = [1, 2, 3]
matrix: List[List[int]] = [[1, 2], [3, 4]]

mapping: Dict[str, int] = {"a": 1, "b": 2}
graph: Dict[int, List[int]] = {0: [1, 2], 1: [3]}

unique: Set[int] = {1, 2, 3}
coordinates: Set[Tuple[int, int]] = {(0, 0), (1, 1)}

point: Tuple[int, int] = (5, 10)
record: Tuple[str, int, float] = ("Alice", 25, 5.8)

# Optional (can be None)
node: Optional[TreeNode] = None
result: Optional[int] = None

# Union (multiple types)
value: Union[int, str] = 5
value = "five"  # Also valid

# Any (any type)
data: Any = {"key": "value"}

# Collections module
from collections import deque, defaultdict, Counter

queue: Deque[int] = deque([1, 2, 3])
adj_list: DefaultDict[int, List[int]] = defaultdict(list)
freq: CounterType[str] = Counter("hello")

# Function signatures
def add(a: int, b: int) -> int:
    return a + b

def process(arr: List[int]) -> Optional[int]:
    return arr[0] if arr else None

def dfs(node: TreeNode, visited: Set[int]) -> None:
    pass  # No return value

# Class with type hints
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: Dict[int, int] = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []

Complexity Cheat Sheet

Data Structure Operations

Data Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)	O(n)
Queue	O(n)	O(n)	O(1)	O(1)	O(n)
Deque	O(n)	O(n)	O(1)	O(1)	O(n)
Hash Table	-	O(1)*	O(1)*	O(1)*	O(n)
Binary Search Tree	O(log n)*	O(log n)*	O(log n)*	O(log n)*	O(n)
Heap	-	O(n)	O(log n)	O(log n)	O(n)

*Average case

Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Tim Sort (Python)	O(n)	O(n log n)	O(n log n)	O(n)	Yes

Common Operations

# String Operations
s.find(sub)             # O(n)
s.replace(old, new)     # O(n)
s.split()               # O(n)
''.join(list)           # O(n)

# List Operations
arr.append(x)           # O(1) amortized
arr.insert(i, x)        # O(n)
arr.pop()               # O(1)
arr.pop(i)              # O(n)
arr.remove(x)           # O(n)
arr.sort()              # O(n log n)
sorted(arr)             # O(n log n)
min(arr), max(arr)      # O(n)

# Dictionary Operations
d[key] = value          # O(1) average
d.get(key)              # O(1) average
del d[key]              # O(1) average
key in d                # O(1) average

# Set Operations
s.add(x)                # O(1) average
s.remove(x)             # O(1) average
x in s                  # O(1) average
s1.union(s2)            # O(len(s1) + len(s2))
s1.intersection(s2)     # O(min(len(s1), len(s2)))

Space Complexity Patterns

# O(1) - Constant space
def reverseArray(arr: List[int]) -> None:
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# O(n) - Linear space
def createCopy(arr: List[int]) -> List[int]:
    return arr[:]

# O(n²) - Quadratic space
def create2DArray(n: int) -> List[List[int]]:
    return [[0] * n for _ in range(n)]

# O(log n) - Logarithmic space (recursion depth)
def binarySearch(arr: List[int], target: int, left: int, right: int) -> int:
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binarySearch(arr, target, mid + 1, right)
    else:
        return binarySearch(arr, target, left, mid - 1)

Quick Tips

Always initialize with correct types: Use type hints to catch errors early
Use collections.Counter for frequency counting: More efficient than manual dict
Use deque for queues: Much faster than list for popleft operations
String concatenation: Use ''.join(list) instead of += in loops
Check if list is empty: Use if not arr: instead of if len(arr) == 0:
Dictionary get with default: Use dict.get(key, default) to avoid KeyError
List slicing creates copy: arr[:] creates a new list
Binary search template: Remember mid = left + (right - left) // 2
Two pointers: Common for sorted arrays and palindromes
Sliding window: For subarray/substring problems
DFS vs BFS: DFS for path finding, BFS for shortest path
Union Find: For connectivity and disjoint set problems
Backtracking: For combinatorial problems (subsets, permutations)
DP: When problem has overlapping subproblems
Heaps: For K-th largest/smallest problems

Common Pitfalls

# ❌ Wrong: Shallow copy of 2D array
matrix = [[0] * 3] * 3  # All rows reference same list!

# ✅ Correct: Deep copy
matrix = [[0] * 3 for _ in range(3)]

# ❌ Wrong: Modifying list while iterating
for x in arr:
    arr.remove(x)  # Skips elements!

# ✅ Correct: Iterate over copy or use list comprehension
arr = [x for x in arr if x != target]

# ❌ Wrong: Default mutable argument
def func(arr=[]):
    arr.append(1)
    return arr

# ✅ Correct: Use None as default
def func(arr=None):
    if arr is None:
        arr = []
    arr.append(1)
    return arr

# ❌ Wrong: Float division in indices
mid = (left + right) / 2  # Returns float!

# ✅ Correct: Integer division
mid = (left + right) // 2

# ❌ Wrong: Checking None with ==
if node == None:
    pass

# ✅ Correct: Use 'is' for None
if node is None:
    pass

This wiki covers all essential Python3 concepts for LeetCode. Practice these patterns and you'll be well-prepared for any coding interview!

sandeepkv93/python3-leetcode-wiki.md

Python3 LeetCode Complete Wiki

Table of Contents

Basic Data Structures

Lists (Arrays)

Dictionaries (Hash Maps)

Sets (Hash Sets)

Tuples

Collections Module

deque (Double-ended Queue)

Counter (Frequency Counter)

defaultdict

Heaps (Priority Queues)

Trees

Binary Tree Node

Trie (Prefix Tree)

Graphs

Representations

DFS (Depth-First Search)

BFS (Breadth-First Search)

Union Find (Disjoint Set)

Topological Sort

Strings

Common Patterns

Sliding Window

Two Pointers

Backtracking

Dynamic Programming

Binary Search

Built-in Functions

Type Hints Reference

Complexity Cheat Sheet

Data Structure Operations

Sorting Algorithms

Common Operations

Space Complexity Patterns

Quick Tips

Common Pitfalls