Complete DSA Course in Python: Master Data Structures & Algorithms from Beginner to Pro

🐍 Latest Edition
📖 Beginner to Advanced
⏱️ 60 min read
🎯 20+ Sections

⏱️ Estimated reading time: 55-60 minutes

📋 Quick Summary: Data Structures & Algorithms are the foundation of every interview at FAANG and every serious software engineering role. This course teaches you DSA from scratch using Python — arrays, linked lists, stacks, queues, trees, graphs, hash tables, sorting, searching, dynamic programming, and more — with real code examples and LeetCode-style problems.

🐍 Why DSA in Python?

Python is the best language for learning DSA because:

• Readable syntax — You focus on the algorithm, not language quirks
• Built-in data structures — Lists, dicts, sets, tuples are already optimized
• Used in FAANG interviews — Google, Meta, Amazon all allow Python
• Huge ecosystem — LeetCode, HackerRank, CodeSignal all support it well

📈 Big O Notation — The Language of Efficiency

Big O describes how an algorithm’s runtime or memory grows as input size increases. It’s the most important concept in DSA.

Common Complexities

Calculating Big O — Rules of Thumb

# 1. Drop constants
#   O(2n) → O(n)   O(n/2) → O(n)

# 2. Drop non-dominant terms
#   O(n + n²) → O(n²)   O(n + log n) → O(n)

# 3. Different inputs → different variables
#   O(a * b) — not O(n²)!

# Example: calculating complexity
def example(arr1, arr2):
    for x in arr1:           # O(a)
        print(x)
    for x in arr1:           # O(a)
        for y in arr2:       # O(b)
            print(x, y)
# Total: O(a + a*b) → O(a*b)

📊 Arrays & Lists

Arrays are the most fundamental data structure. In Python, lists serve as dynamic arrays.

Python List Operations

arr = [1, 2, 3, 4, 5]

# Access — O(1)
print(arr[0])        # 1
print(arr[-1])       # 5

# Search — O(n)
print(arr.index(3))  # 2

# Insert at end — O(1) amortized
arr.append(6)

# Insert at position — O(n)
arr.insert(0, 0)     # [0, 1, 2, 3, 4, 5, 6]

# Remove — O(n)
arr.remove(3)        # Remove by value
popped = arr.pop()   # Remove last — O(1)
popped = arr.pop(0)  # Remove first — O(n)

# Slice — O(k)
sub = arr[1:4]       # Elements at index 1,2,3

# List comprehension (fast!)
squares = [x**2 for x in range(10)]

# Two-pointer technique
def reverse(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Common Array Problems

# Two Sum — O(n)
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Max Subarray (Kadane's Algorithm) — O(n)
def max_subarray(nums):
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum

# Contains Duplicate — O(n)
def has_duplicate(nums):
    return len(nums) != len(set(nums))

# Rotate Array — O(n)
def rotate(arr, k):
    k %= len(arr)
    arr[:] = arr[-k:] + arr[:-k]

# Product of Array Except Self — O(n)
def product_except_self(nums):
    n = len(nums)
    output = [1] * n
    left = right = 1
    for i in range(n):
        output[i] *= left
        left *= nums[i]
        output[n-1-i] *= right
        right *= nums[n-1-i]
    return output

🔗 Linked Lists

Linked lists are linear data structures where elements (nodes) are connected via pointers. Unlike arrays, they're dynamic and don't require contiguous memory.

Singly Linked List

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):         # O(n)
        if not self.head:
            self.head = ListNode(val)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = ListNode(val)

    def prepend(self, val):        # O(1)
        node = ListNode(val)
        node.next = self.head
        self.head = node

    def delete(self, val):         # O(n)
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            return
        curr = self.head
        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
                return
            curr = curr.next

    def print(self):
        values = []
        curr = self.head
        while curr:
            values.append(str(curr.val))
            curr = curr.next
        print(' -> '.join(values))

Common Linked List Problems

# Reverse Linked List — O(n)
def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

# Detect Cycle (Floyd's Algorithm) — O(n)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Merge Two Sorted Lists — O(n+m)
def merge_two(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

# Find Middle — O(n)
def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# Remove Nth from End — O(n)
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

🥞 Stacks & Queues

Stack (LIFO — Last In, First Out)

# Python list works as a stack — O(1) for push/pop
stack = []
stack.append(1)        # Push — O(1)
stack.append(2)
stack.append(3)
top = stack.pop()      # Pop — O(1)  → 3
top = stack[-1]        # Peek — O(1) → 2

# Common stack problems
# Valid Parentheses — O(n)
def is_valid(s):
    pairs = {')': '(', '}': '{', ']': '['}
    stack = []
    for c in s:
        if c in '({[':
            stack.append(c)
        else:
            if not stack or stack.pop() != pairs:
                return False
    return len(stack) == 0

# Min Stack (O(1) getMin)
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

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

    def get_min(self):
        return self.min_stack[-1]

Queue (FIFO — First In, First Out)

# collections.deque — O(1) for both ends
from collections import deque

queue = deque()
queue.append(1)         # Enqueue right — O(1)
queue.append(2)
queue.append(3)
first = queue.popleft() # Dequeue left — O(1) → 1
first = queue[0]        # Peek — O(1) → 2

# deque can also push/pop from both sides
queue.appendleft(0)     # Push left — O(1)
last = queue.pop()      # Pop right — O(1)

# Queue via two stacks
class QueueViaStacks:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, x):
        self.in_stack.append(x)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

🔑 Hash Tables (Dictionaries & Sets)

Hash tables are the most versatile data structure. Python's dict and set are both hash-table-based with O(1) average operations.

# Dict — key-value store
d = {}
d['name'] = 'Alice'      # Insert O(1)
d['age'] = 25
print(d['name'])          # Access O(1)
print(d.get('city', 'N/A'))  # Safe access
del d['age']              # Delete O(1)

# Common dict patterns
# Frequency counter
from collections import Counter
freq = Counter('aabbbcc')  # {'a': 2, 'b': 3, 'c': 2}

# Default dict (no KeyError)
from collections import defaultdict
groups = defaultdict(list)
groups['even'].append(2)   # No need to check if key exists

# Ordered dict (preserves insertion order in Python 3.7+)
from collections import OrderedDict

# Set — unique values
s = set()
s.add(1)                  # O(1)
s.add(2)
print(1 in s)             # O(1) → True
s.remove(1)               # O(1)

# Set operations — very fast
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a | b)              # Union: {1,2,3,4,5,6}
print(a & b)              # Intersection: {3,4}
print(a - b)              # Difference: {1,2}
print(a ^ b)              # Symmetric diff: {1,2,5,6}

Common Hash Table Problems

# Group Anagrams — O(n * k log k)
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

# Top K Frequent Elements — O(n)
def top_k_frequent(nums, k):
    from collections import Counter
    freq = Counter(nums)
    return [num for num, _ in freq.most_common(k)]

# Longest Consecutive Sequence — O(n)
def longest_consecutive(nums):
    nums_set = set(nums)
    longest = 0
    for num in nums_set:
        if num - 1 not in nums_set:  # Start of a sequence
            length = 1
            while num + length in nums_set:
                length += 1
            longest = max(longest, length)
    return longest

🔄 Recursion

Recursion is when a function calls itself. It's the foundation for trees, graphs, and divide-and-conquer algorithms.

# Anatomy of recursion: base case + recursive case
def factorial(n):
    if n <= 1:          # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

# Fibonacci
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
# ⚠️ O(2ⁿ) — terrible! Use memoization:

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]
# Now O(n)

# Recursion vs iteration — both work
# Recurse until base case, then unwind the stack
# Each recursive call adds a frame to the call stack

# Backtracking template
def backtrack(path, choices, result):
    if goal_reached:
        result.append(path[:])
        return
    for choice in choices:
        make_choice(path, choice)
        backtrack(path, remaining, result)
        undo_choice(path, choice)

🔀 Sorting Algorithms

Comparison Sort — O(n log n)

# Python's built-in sort — Timsort, O(n log n)
arr.sort()                  # In-place
sorted_arr = sorted(arr)    # Returns new list

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

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

# Quick Sort — O(n log n) avg, O(n²) worst
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

Non-Comparison Sort — O(n)

# Counting Sort — O(n+k) — only for integers in range
def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    result = []
    for i, c in enumerate(count):
        result.extend([i] * c)
    return result

🔍 Searching Algorithms

Binary Search — O(log n)

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

# Recursive version
def binary_search_rec(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid+1, right)
    else:
        return binary_search_rec(arr, target, left, mid-1)

# Find insertion point (bisect)
import bisect
idx = bisect.bisect_left(arr, target)  # First index where target could be inserted
idx = bisect.bisect_right(arr, target) # Last + 1

# Common binary search variants
def first_occurrence(arr, 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

# Search in rotated sorted array
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # Left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

🌳 Trees

Binary Tree & Tree Traversals

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

# DFS Traversals — O(n)
def inorder(root):        # Left → Root → Right
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):       # Root → Left → Right
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):      # Left → Right → Root
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# BFS (Level Order) — O(n)
from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

Binary Search Tree (BST)

# BST Property: left.val < root.val < right.val
# Average O(log n) for insert/search/delete

class BST:
    def search(self, root, val):
        if not root or root.val == val:
            return root
        if val < root.val:
            return self.search(root.left, val)
        return self.search(root.right, val)

    def insert(self, root, val):
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root

    def min_value(self, root):
        while root.left:
            root = root.left
        return root.val

    def delete(self, root, val):
        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:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            # Node has two children
            root.val = self.min_value(root.right)
            root.right = self.delete(root.right, root.val)
        return root

    # Validate BST — O(n)
    def is_valid(self, root, low=float('-inf'), high=float('inf')):
        if not root:
            return True
        if root.val <= low or root.val >= high:
            return False
        return (self.is_valid(root.left, low, root.val) and
                self.is_valid(root.right, root.val, high))

    # Kth smallest element — O(n)
    def kth_smallest(self, root, k):
        stack = []
        curr = root
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right

Tree Problems

# Max Depth — O(n)
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Same Tree — O(n)
def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

# Diameter of Tree — O(n)
def diameter_of_tree(root):
    diameter = 0
    def depth(node):
        nonlocal diameter
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)
    depth(root)
    return diameter

# Path Sum — O(n)
def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    return (has_path_sum(root.left, target - root.val) or
            has_path_sum(root.right, target - root.val))

📚 Heaps (Priority Queues)

A heap is a complete binary tree where parent nodes are always smaller (min-heap) or larger (max-heap) than children.

import heapq

# Python's heapq is a MIN-HEAP by default
# To get a MAX-HEAP, insert negative values

heap = []
heapq.heappush(heap, 3)   # Push — O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # Pop min — O(log n) → 1
print(heap[0])              # Peek min — O(1) → 2

# Convert list to heap in O(n)
arr = [5, 2, 3, 1, 4]
heapq.heapify(arr)

# Common heap problems
# Kth Largest Element — O(n log k)
def find_kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]  # kth largest = top of min-heap of size k

# Merge K Sorted Lists — O(n log k)
def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    dummy = ListNode(0)
    curr = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = ListNode(val)
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# Find Median from Data Stream — O(log n) per insert
class MedianFinder:
    def __init__(self):
        self.small = []  # Max-heap (store negatives)
        self.large = []  # Min-heap

    def add_num(self, num):
        heapq.heappush(self.small, -num)
        if (self.small and self.large and -self.small[0] > self.large[0]):
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

🕸️ Graphs

Graph Representation

# Adjacency List — most common
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1]
}

# Adjacency Matrix — O(V²) space
# matrix[i][j] = 1 if edge exists
matrix = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 1],
    [1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0]
]

DFS & BFS on Graphs

# DFS (iterative) — O(V + E)
def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

# DFS (recursive)
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

# BFS — O(V + E)
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

Common Graph Problems

# Number of Islands (2D Grid) — O(m*n)
def num_islands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
            dfs(i+di, j+dj)
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

# Clone Graph — O(V+E)
def clone_graph(node):
    if not node:
        return None
    clones = {}
    def dfs(node):
        if node in clones:
            return clones[node]
        clone = Node(node.val)
        clones[node] = clone
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone
    return dfs(node)

# Course Schedule (Topological Sort) — O(V+E)
def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    completed = 0
    while queue:
        node = queue.popleft()
        completed += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return completed == num_courses

🧩 Dynamic Programming

DP is solving problems by breaking them into overlapping subproblems and storing results to avoid recomputation.

Two Approaches

# 1. Top-Down (Memoization) — recursion + cache
def fib(n):
    memo = {}
    def dp(i):
        if i <= 1:
            return i
        if i not in memo:
            memo[i] = dp(i-1) + dp(i-2)
        return memo[i]
    return dp(n)

# 2. Bottom-Up (Tabulation) — iterative array
def fib(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
def fib(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

Classic DP Problems

# Climbing Stairs — O(n)
def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# Coin Change (minimum coins) — O(amount * coins)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

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

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

# Longest Increasing Subsequence — O(n²)
def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# LIS — optimized O(n log n)
def length_of_lis_fast(nums):
    import bisect
    tails = []
    for num in nums:
        idx = bisect.bisect_left(tails, num)
        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num
    return len(tails)

❌ Common Mistakes & How to Avoid Them

🔴 Mistake #1: Not Analyzing Complexity First

What happens: You write a solution with nested loops that passes small test cases but fails on large inputs with TLE (Time Limit Exceeded).

How to fix: Always ask: "What's the input size?" If n=10⁵, O(n²) is dead. Think about complexity before writing code.

🔴 Mistake #2: Forgetting Edge Cases

What happens: Your code crashes on empty arrays, single elements, negative numbers, or duplicates.

How to fix: Before coding, list edge cases: empty input, single element, already sorted, all same value, negative numbers, max constraints.

🔴 Mistake #3: Not Using the Right Data Structure

What happens: You use a list where a set would give O(1) lookup. You nest loops when a hash map would solve it in one pass.

How to fix: Build a mental cheat sheet: "Need fast lookup? Use a set/dict. Need order? Use stack/queue. Need min/max fast? Use heap."

🔴 Mistake #4: No Base Case in Recursion

What happens: Infinite recursion → StackOverflow. Your recursive function never terminates.

How to fix: Always define the base case first before writing the recursive case. Check null/empty at the top of every recursive function.

🔴 Mistake #5: Modifying While Iterating

# BAD — modifying list while iterating
for i, x in enumerate(arr):
    if x == 2:
        arr.remove(x)  # Skips next element!

# GOOD — collect indices first, remove after
to_remove = [i for i, x in enumerate(arr) if x == 2]
for i in reversed(to_remove):
    arr.pop(i)

# Or use list comprehension
arr = [x for x in arr if x != 2]

🧠 Test Your Knowledge

1. What's the time complexity of accessing an element in a Python list?
   
   A) O(n)
   
   B) O(log n)
   
   C) O(1)
   
   D) O(n log n)
   
   Answer: C — Array access by index is O(1) in Python lists (dynamic arrays).
2. Which data structure would you use for a "First In, First Out" order?
   
   A) Stack
   
   B) Queue
   
   C) Hash table
   
   D) Heap
   
   Answer: B — Queue follows FIFO. deque is the Python implementation.
3. What's the worst-case time complexity of Quick Sort?
   
   A) O(n log n)
   
   B) O(n²)
   
   C) O(n)
   
   D) O(log n)
   
   Answer: B — Quick Sort is O(n²) worst case (pivot is always smallest/largest). O(n log n) average.
4. Which traversal visits node, then left subtree, then right subtree?
   
   A) Inorder
   
   B) Preorder
   
   C) Postorder
   
   D) Level order
   
   Answer: B — Preorder: Root → Left → Right.
5. What's the space complexity of BFS on a graph?
   
   A) O(1)
   
   B) O(V + E)
   
   C) O(V)
   
   D) O(log V)
   
   Answer: C — BFS uses a queue that can hold up to V vertices in worst case.

❓ Frequently Asked Questions (FAQ)

📖 Glossary

✅ Do's & Don'ts

💡 10 Pro Tips Learned the Hard Way

1. Always draw before you code. For trees, graphs, DP — draw the structure. The solution often becomes obvious once you visualize the problem.
2. Master the two-pointer technique. It solves 70% of array problems: palindrome checking, container with most water, three-sum, removing duplicates. Learn it well.
3. Use collections.defaultdict and Counter. They eliminate 90% of boilerplate code for hash map problems. defaultdict(list) for grouping, Counter for frequencies.
4. Know your built-in sort. Python's Timsort is O(n log n) and incredibly fast. You almost never need to implement your own sort — use sorted() or arr.sort().
5. BFS vs DFS decision: BFS for shortest path in unweighted graphs. DFS for exploring all paths, detecting cycles, topological order. BFS uses queue, DFS uses stack (or recursion).
6. DP is just recursion + memoization. Start with the recursive solution, add a cache. If it works, optimize to bottom-up. This mental model makes DP approachable.
7. Use LeetCode's discussion section. After solving a problem, read the top 3 solutions. Different approaches teach you patterns you'll use on other problems.
8. The 5-minute rule. If you're stuck for 5 minutes on a problem, peek at the solution. Understand it deeply. Close it and re-solve from scratch. This is more effective than staring at a blank screen.
9. Learn to write Pythonic code. List comprehensions, slicing, zip(), enumerate(), reversed(), * unpacking — they make solutions shorter and clearer. But never sacrifice readability for cleverness.
10. Consistency beats intensity. 1 problem per day for 6 months beats 50 problems in a weekend. Spaced repetition builds neural pathways. Make DSA a daily habit.

🗺️ Learning Roadmap

🔍 Troubleshooting

💬 What's Your DSA Journey?

What's your story with DSA? First LeetCode problem? FAANG interview story? The problem that finally made DP click? Drop a comment — I read every one.

Quick questions:

• What topic took you the longest to master?
• What's your favorite LeetCode problem?
• How many problems have you solved?
• Which interview was your toughest?

📌 TL;DR: If You Learn Nothing Else, Learn These 5

1. Big O — Understand time and space complexity. It's how you know if your solution is good enough. O(n²) fails at n=10⁵. Always think: "What's my complexity?"
2. Hash Maps — dict and set solve most problems in O(n). Two Sum, frequency counters, caching — if you need fast lookup, use a hash map.
3. Binary Search — O(log n) on sorted data. Learn the three variants: basic, first/last occurrence, and search in rotated array.
4. Two Pointers — O(n) on arrays. Reverse, palindrome, three-sum, container with most water. Master this and 30% of array problems become trivial.
5. Dynamic Programming — The hardest and most rewarding. Start with recursion + memoization. Add a cache. Convert to tabulation. The more you practice, the more patterns you'll see.

More Free Courses on TricksPage

• Git & GitHub Course — Master version control.
• Linux Commands Course — Master the command line.
• Docker & Swarm Course — Containers, Compose, Swarm.
• Python Course — Master Python from scratch.
• Agentic AI Course — Build intelligent AI agents.

💭 Final Thoughts

Data Structures and Algorithms isn't just about passing interviews. It's about learning to think like a computer scientist — breaking problems down, recognizing patterns, and designing efficient solutions. These skills will make you a better developer regardless of where you work.

The path is hard but straightforward: learn the theory, practice daily, review solutions, and iterate. Every FAANG engineer started exactly where you are now. The only difference is they didn't give up.

🔥 Final Word: "The impediment to action advances the action. What stands in the way becomes the way." — Marcus Aurelius

Now go solve a LeetCode problem. 🐍

More Free Courses on TricksPage

• Git & GitHub Course — Master version control.
• Linux Commands Course — Master the command line.
• Docker & Swarm Course — Containers, Compose, Swarm.
• Python Course — Master Python from scratch.
• Agentic AI Course — Build intelligent AI agents.

If this course helped you:

• 📌 Bookmark this page for future reference
• 📤 Share it with someone preparing for interviews
• 💬 Leave a comment — I read every one
• ⭐ Follow the blog for more deep courses