Complete DSA in Python: From Beginner to Advanced learning roadmap with Real Examples
Imagine you’re organizing your closet. You could throw everything in randomly, or you could arrange clothes by type, season, and color. Data Structures and Algorithms (DSA) is exactly that—organizing
Why Learn DSA with Python?
Think of Python as your friendly translator. While other programming languages make you worry about memory management and complex syntax, Python lets you focus on solving problems. When you go for interviews at Google, Amazon, or any tech company, they care more about how you think than which language you use—and Python’s clean syntax makes your thinking crystal clear.
Foundations - Understanding the Basics
What is a Data Structure?
A data structure is simply a way to store and organize data. Think of it like containers in your kitchen—you use jars for cookies, bottles for liquids, and boxes for snacks. Each container serves a specific purpose.
Real Example:
# Storing student marks - we use a list (like a row of boxes)
marks = [85, 90, 78, 92]
# Getting first student’s marks
print(marks[0]) # Output: 85
Just like you can quickly grab the first jar on your shelf, accessing marks[0] instantly gives you the first student’s marks. This is your first data structure—the list!
What is an Algorithm?
An algorithm is a recipe for solving a problem. Just like a cooking recipe has steps (chop onions, heat oil, add spices), an algorithm has clear steps to achieve a result.
Real Example:
# Algorithm: Find the highest marks in class
marks = [85, 90, 78, 92]
highest = marks[0] # Start by assuming first is highest
for score in marks:
if score > highest:
highest = score # Found someone with higher marks!
print(f”Highest marks: {highest}”) # Output: 92
This algorithm works like checking each student’s paper one by one, remembering the highest score you’ve seen so far.
How Python Handles Memory
When you create a list in Python, it’s like Python grabs a row of boxes in memory and labels them. Unlike languages like C where you need to say “I need 4 boxes,” Python automatically manages this. When your list grows, Python finds a bigger space and moves everything—like upgrading from a small basket to a big box.
Part 1: Python Essentials - Your Toolbox
Variables and Data Types
Variables are like labeled containers holding different types of items.
age = 25 # Integer (whole number)
height = 5.9 # Float (decimal number)
name = “Abhishek” # String (text)
is_student = True # Boolean (True/False)
print(f”{name} is {age} years old”)
Think of it this way: age is a box labeled “age” containing the number 25. You can look inside anytime by using the label.
Conditional Statements - Making Decisions
Life is full of decisions: “If it’s raining, take an umbrella.” Code works the same way.
temperature = 30
if temperature > 25:
print(”It’s hot! Wear light clothes”)
elif temperature > 15:
print(”Pleasant weather”)
else:
print(”It’s cold! Wear a jacket”)
The program checks each condition like you checking the weather before dressing up.
Loops - Repeating Tasks
Why do something 100 times manually when you can write it once?
For Loop - When you know how many times:
# Print “Hello” 5 times
for i in range(5):
print(f”Hello {i}”)
# Output: Hello 0, Hello 1, Hello 2, Hello 3, Hello 4
While Loop - When you don’t know how many times:
# Keep asking until user says “yes”
answer = “”
while answer != “yes”:
answer = input(”Do you understand loops? (yes/no): “)
print(”Great! Let’s continue”)
Think of for as “do this 5 times” and while as “keep doing until condition is met.”
Functions - Reusable Code Blocks
Functions are like mini-machines. You give them input, they process it, and give you output.
def greet(name):
return f”Hello, {name}!”
print(greet(”Abhishek”)) # Output: Hello, Abhishek!
print(greet(”Sarah”)) # Output: Hello, Sarah!
Instead of writing greeting code repeatedly, you created a greeting machine—use it anywhere!
Recursion - Functions Calling Themselves
Recursion is like looking in mirrors facing each other—each reflection contains another reflection. It’s a function calling itself with simpler inputs.
def factorial(n):
# Base case: stop the recursion
if n == 0:
return 1
# Recursive case: call itself with smaller number
return n * factorial(n-1)
print(factorial(5)) # 5 * 4 * 3 * 2 * 1 = 120
When you call factorial(5), it thinks: “5 times factorial of 4.” Then factorial(4) thinks: “4 times factorial of 3,” and so on until reaching 0. Then all results multiply back up!
Collections Module - Special Tools
Python’s collections module gives you specialized containers for specific jobs.
from collections import deque, Counter, defaultdict
# deque - efficient for adding/removing from both ends
playlist = deque([’Song1’, ‘Song2’, ‘Song3’])
playlist.append(’Song4’) # Add to end
playlist.appendleft(’Song0’) # Add to beginning
print(playlist)
# Counter - count occurrences automatically
word = “banana”
letter_count = Counter(word)
print(letter_count) # Counter({’a’: 3, ‘n’: 2, ‘b’: 1})
# defaultdict - never get KeyError
scores = defaultdict(int) # default value is 0
scores[’player1’] += 10 # No need to check if exists!
print(scores[’player1’]) # 10
Think of deque as a queue at a theater where people can join from front or back. Counter is like a tally sheet that automatically counts. defaultdict is like a notebook that creates pages as you need them.
Part 2: Time and Space Complexity - Measuring Efficiency
Why Complexity Matters
Imagine two ways to find a word in a dictionary:
Check every single page from start (slow!)
Open middle, decide if word is before or after, repeat (fast!)
Both find the word, but method 2 is dramatically faster. That’s what complexity analysis tells us.
Big O Notation - The Speed Measurement
O(1) - Constant Time (Lightning Fast):
# Getting first element - always same time regardless of list size
marks = [85, 90, 78, 92, 88, 95]
first = marks[0] # Same speed for 10 items or 1 million!
O(n) - Linear Time (Scales with Size):
# Finding a specific mark - might need to check all
def find_mark(marks, target):
for mark in marks: # Check each one
if mark == target:
return True
return False
If list doubles in size, time doubles. Like checking each book on a shelf.
O(log n) - Logarithmic Time (Very Efficient):
# Binary search on sorted list
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
sorted_marks = [70, 75, 80, 85, 90, 95]
print(binary_search(sorted_marks, 85)) # Output: 3
Each step cuts remaining items in half—like that dictionary example!
O(n²) - Quadratic Time (Slow for Large Data):
# Nested loops - checking every pair
def find_duplicates(arr):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
print(f”Duplicate found: {arr[i]}”)
If 10 items take 100 operations, 100 items take 10,000 operations! Like comparing every person with every other person in a room.
Space Complexity - Memory Usage
Some algorithms use extra memory to run faster. It’s like using more bowls while cooking to work faster versus washing one bowl repeatedly.
# O(1) space - using same variables
def sum_array(arr):
total = 0 # Just one extra variable
for num in arr:
total += num
return total
# O(n) space - creating new list
def double_values(arr):
result = [] # New list same size as input
for num in arr:
result.append(num * 2)
return result
Part 3: Arrays and Lists - The Foundation
Python Lists as Dynamic Arrays
A list is like a row of lockers, each numbered starting from 0. Python calls them “lists,” but they work like arrays in other languages.
fruits = [’apple’, ‘banana’, ‘orange’, ‘grape’]
# Access by index (locker number)
print(fruits[0]) # apple (first item)
print(fruits[-1]) # grape (last item)
print(fruits[1:3]) # [’banana’, ‘orange’] (slice from index 1 to 3)
Basic Operations
Insert:
fruits = [’apple’, ‘banana’]
fruits.append(’orange’) # Add to end: O(1)
fruits.insert(1, ‘mango’) # Insert at index 1: O(n)
print(fruits) # [’apple’, ‘mango’, ‘banana’, ‘orange’]
Adding to end is instant. Inserting in middle is slow because everything after needs to shift—like people in a queue making space for someone.
Delete:
fruits = [’apple’, ‘banana’, ‘orange’, ‘grape’]
fruits.remove(’banana’) # Remove by value: O(n)
fruits.pop() # Remove last: O(1)
fruits.pop(0) # Remove first: O(n)
print(fruits)
Traverse:
for fruit in fruits:
print(f”I like {fruit}”)
Common Array Problems
Reverse Array:
# Method 1: Built-in
arr = [1, 2, 3, 4, 5]
reversed_arr = arr[::-1] # [5, 4, 3, 2, 1]
# Method 2: Two pointers
def reverse_array(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left] # Swap
left += 1
right -= 1
return arr
The two-pointer method is like two people walking from opposite ends, swapping items as they meet.
Rotate Array:
# Rotate right by k positions
def rotate_array(arr, k):
k = k % len(arr) # Handle k > array length
return arr[-k:] + arr[:-k]
arr = [1, 2, 3, 4, 5]
print(rotate_array(arr, 2)) # [4, 5, 1, 2, 3]
Imagine people in a circle shifting positions—last k people move to front.
Find Missing Number:
# Array should have numbers 1 to n, find missing one
def find_missing(arr, n):
expected_sum = n * (n + 1) // 2 # Sum formula
actual_sum = sum(arr)
return expected_sum - actual_sum
arr = [1, 2, 4, 5, 6] # 3 is missing
print(find_missing(arr, 6)) # Output: 3
Clever! Instead of checking each number, we use math—like counting money and noticing the shortfall.
Two Sum Problem:
# Find two numbers that add up to target
def two_sum(arr, target):
seen = {} # Store numbers we’ve seen
for i, num in enumerate(arr):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
arr = [2, 7, 11, 15]
print(two_sum(arr, 9)) # [0, 1] because arr[0] + arr[1] = 9
This is brilliant—as we check each number, we remember it. If we need 9 and see 4, we look for 5 in our memory.
Kadane’s Algorithm (Maximum Subarray Sum):
def max_subarray_sum(arr):
max_sum = current_sum = arr[0]
for num in arr[1:]:
# Either extend current subarray or start fresh
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr)) # 6 (subarray [4,-1,2,1])
The genius: at each number, decide “Should I continue adding to previous sum or start fresh from here?”
Part 4: Strings - Working with Text
String Basics
Strings are sequences of characters—immutable means you can’t change them, only create new ones.
message = “Hello DSA”
# Access characters
print(message[0]) # ‘H’
print(message[-1]) # ‘A’ (last character)
# Slicing
print(message[0:5]) # ‘Hello’
print(message[6:]) # ‘DSA’
# Strings are immutable
# message[0] = ‘h’ # This would cause an error!
message = message.lower() # Creates new string instead
String Operations
text = “ Python DSA “
# Common operations
print(text.strip()) # “Python DSA” (remove spaces)
print(text.upper()) # “ PYTHON DSA “
print(text.replace(”DSA”, “Programming”))
print(text.split()) # [’Python’, ‘DSA’] (split by spaces)
# Join strings efficiently
words = [’Learn’, ‘Python’, ‘DSA’]
sentence = ‘ ‘.join(words) # “Learn Python DSA”
Why join matters:
# Bad - creates new string each time (slow!)
result = “”
for word in words:
result += word + “ “ # Creates n new strings
# Good - creates string once (fast!)
result = ‘ ‘.join(words)
Common String Problems
Reverse String:
def reverse_string(s):
return s[::-1]
print(reverse_string(”hello”)) # “olleh”
# Two-pointer method
def reverse_string_manual(s):
chars = list(s) # Convert to list (strings immutable)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return ‘’.join(chars)
Palindrome Check:
def is_palindrome(s):
# Remove spaces and convert to lowercase
s = s.replace(” “, “”).lower()
return s == s[::-1]
print(is_palindrome(”A man a plan a canal Panama”)) # True
print(is_palindrome(”hello”)) # False
A palindrome reads the same forwards and backwards—like “racecar” or “mom.”
Anagram Check:
def is_anagram(s1, s2):
# Anagrams have same letters, different order
return sorted(s1) == sorted(s2)
print(is_anagram(”listen”, “silent”)) # True
print(is_anagram(”hello”, “world”)) # False
# Better method using Counter
from collections import Counter
def is_anagram_better(s1, s2):
return Counter(s1) == Counter(s2)
Anagrams are like scrambled words—”listen” becomes “silent.”
First Non-Repeating Character:
def first_non_repeating(s):
# Count each character
count = Counter(s)
# Find first with count 1
for i, char in enumerate(s):
if count[char] == 1:
return i
return -1
print(first_non_repeating(”aabbccdef”)) # 6 (index of ‘d’)
Like finding the first person in a group who came alone!
Count Vowels:
def count_vowels(s):
vowels = “aeiouAEIOU”
count = 0
for char in s:
if char in vowels:
count += 1
return count
# One-liner
def count_vowels_short(s):
return sum(1 for char in s if char.lower() in ‘aeiou’)
print(count_vowels(”Hello World”)) # 3
Part 5: Linked Lists - Chain of Nodes
Understanding Linked Lists
Imagine a treasure hunt where each clue points to the next location. That’s a linked list—each node contains data and a reference to the next node.
class Node:
def __init__(self, data):
self.data = data
self.next = None # Points to next node
# Creating nodes
head = Node(10)
second = Node(20)
third = Node(30)
# Linking them
head.next = second
second.next = third
# Now we have: 10 -> 20 -> 30
Why Use Linked Lists?
Arrays need continuous memory—like parking cars in a row. Linked lists scatter nodes anywhere—like a scavenger hunt. This makes insertion/deletion at beginning super fast!
Comparison:
Array: Insert at start = O(n) (shift everything)
Linked List: Insert at start = O(1) (just change pointer)
Singly Linked List Operations
Insert at Beginning:
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head # New node points to old head
return new_node # New node becomes head
# Before: 10 -> 20 -> 30
head = insert_at_beginning(head, 5)
# After: 5 -> 10 -> 20 -> 30
Insert at End:
def insert_at_end(head, data):
new_node = Node(data)
if not head:
return new_node
# Traverse to last node
current = head
while current.next:
current = current.next
current.next = new_node
return head
Like finding the last person in a chain to add someone new.
Delete Node:
def delete_node(head, key):
# If head needs deletion
if head and head.data == key:
return head.next
current = head
while current.next:
if current.next.data == key:
current.next = current.next.next # Skip the node
break
current = current.next
return head
Print List:
def print_list(head):
current = head
while current:
print(current.data, end=” -> “)
current = current.next
print(”None”)
Reverse Linked List
This is a classic interview problem!
def reverse_linked_list(head):
prev = None
current = head
while current:
next_node = current.next # Save next
current.next = prev # Reverse pointer
prev = current # Move prev forward
current = next_node # Move current forward
return prev # New head
# Before: 1 -> 2 -> 3 -> None
# After: 3 -> 2 -> 1 -> None
Imagine people in a line turning around to face the opposite direction!
Detect Loop (Floyd’s Cycle Detection)
The Tortoise and Hare Algorithm:
def has_cycle(head):
if not head:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next # Move 1 step
fast = fast.next.next # Move 2 steps
if slow == fast: # They meet? Loop exists!
return True
return False
Why this works: If there’s a loop, the fast pointer will eventually lap the slow pointer—like two runners on a circular track!
Part 6: Stacks and Queues - Order Matters
Stack - Last In, First Out (LIFO)
Think of a stack of plates—you add to top, remove from top.
# Using Python list as stack
stack = []
# Push (add)
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) # [10, 20, 30]
# Pop (remove from top)
top = stack.pop() # Gets 30
print(top)
print(stack) # [10, 20]
# Peek (look at top without removing)
if stack:
print(stack[-1]) # 20
Better Stack using deque:
from collections import deque
stack = deque()
stack.append(10)
stack.append(20)
top = stack.pop()
Stack Applications
Balanced Parentheses:
def is_balanced(s):
stack = []
matching = {’(’: ‘)’, ‘[’: ‘]’, ‘{’: ‘}’}
for char in s:
if char in matching: # Opening bracket
stack.append(char)
else: # Closing bracket
if not stack:
return False
if matching[stack.pop()] != char:
return False
return len(stack) == 0
print(is_balanced(”({[]})”)) # True
print(is_balanced(”({[}])”)) # False
Like checking if every door you open gets closed properly!
Undo Feature Simulation:
class TextEditor:
def __init__(self):
self.text = “”
self.undo_stack = []
def write(self, text):
self.undo_stack.append(self.text)
self.text += text
def undo(self):
if self.undo_stack:
self.text = self.undo_stack.pop()
editor = TextEditor()
editor.write(”Hello”)
editor.write(” World”)
print(editor.text) # “Hello World”
editor.undo()
print(editor.text) # “Hello”
Queue - First In, First Out (FIFO)
Think of a queue at a ticket counter—first person in line gets served first.
from collections import deque
# Queue using deque (efficient)
queue = deque()
# Enqueue (add to back)
queue.append(10)
queue.append(20)
queue.append(30)
# Dequeue (remove from front)
first = queue.popleft() # Gets 10
print(first)
print(queue) # deque([20, 30])
Queue Applications
BFS (Breadth-First Search) Preview:
def bfs_level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Priority Queue (Heap)
Not all queues are equal—sometimes VIPs skip ahead!
import heapq
# Min heap (smallest first)
pq = []
heapq.heappush(pq, (3, “Low priority task”))
heapq.heappush(pq, (1, “High priority task”))
heapq.heappush(pq, (2, “Medium priority task”))
while pq:
priority, task = heapq.heappop(pq)
print(f”{task} (priority: {priority})”)
# Output:
# High priority task (priority: 1)
# Medium priority task (priority: 2)
# Low priority task (priority: 3)
Part 7: Recursion and Backtracking - Elegant Solutions
Understanding Recursion
Recursion is a function calling itself—like Russian nesting dolls, each containing a smaller version.
Factorial:
def factorial(n):
# Base case - stop recursion
if n == 0 or n == 1:
return 1
# Recursive case
return n * factorial(n - 1)
# factorial(5) calls factorial(4)
# factorial(4) calls factorial(3)
# ... until factorial(1) returns 1
# Then multiply back: 5*4*3*2*1 = 120
Fibonacci:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
# Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13...
print([fibonacci(i) for i in range(8)])
Problem with naive Fibonacci: It recalculates same values many times! fibonacci(5) calculates fibonacci(3) twice!
Backtracking - Exploring Possibilities
Backtracking tries options, abandons dead ends, and backtracks to try other paths.
Generate All Subsets:
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # Add current subset
for i in range(start, len(nums)):
path.append(nums[i]) # Choose
backtrack(i + 1, path) # Explore
path.pop() # Un-choose (backtrack)
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
Think of it as: “Should I include this element or not?” Try both possibilities!
N-Queens Problem:
def solve_n_queens(n):
def is_safe(board, row, col):
# Check column
for i in range(row):
if board[i] == col:
return False
# Check diagonal
for i in range(row):
if abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(row, board):
if row == n:
result.append(board[:])
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
backtrack(row + 1, board)
board[row] = -1 # Backtrack
result = []
backtrack(0, [-1] * n)
return result
Place queens one row at a time, backtrack if they attack each other!
Part 8: Trees - Hierarchical Data
Binary Tree Basics
A tree is like a family tree—one root, parents with children.
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
# Creating a simple tree:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
Tree Traversals
Inorder (Left-Root-Right):
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=’ ‘)
inorder(root.right)
inorder(root) # Output: 4 2 5 1 3
Preorder (Root-Left-Right):
def preorder(root):
if root:
print(root.val, end=’ ‘)
preorder(root.left)
preorder(root.right)
preorder(root) # Output: 1 2 4 5 3
Postorder (Left-Right-Root):
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=’ ‘)
postorder(root) # Output: 4 5 2 3 1
Level Order (BFS):
from collections import deque
def level_order(root):
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
print(level_order(root)) # [[1], [2, 3], [4, 5]]
Tree Problems
Height of Tree:
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
print(height(root)) # 3
Think: “How many levels deep is this tree?”
Diameter of Tree:
def diameter(root):
diameter_value = [0] # Use list to modify in nested function
def depth(node):
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
# Update diameter if path through this node is longer
diameter_value[0] = max(diameter_value[0], left + right)
return 1 + max(left, right)
depth(root)
return diameter_value[0]
Binary Search Tree (BST):
In BST: left children < parent < right children
def insert_bst(root, value):
if not root:
return TreeNode(value)
if value < root.val:
root.left = insert_bst(root.left, value)
else:
root.right = insert_bst(root.right, value)
return root
def search_bst(root, value):
if not root or root.val == value:
return root
if value < root.val:
return search_bst(root.left, value)
return search_bst(root.right, value)
BST enables fast search—like binary search on a tree!
Part 9: Heaps - Priority Access
Understanding Heaps
A heap is a special tree where parents are always larger (max-heap) or smaller (min-heap) than children. Think of it as a tournament bracket where winners bubble up!
import heapq
# Python heapq creates min-heap by default
heap = []
# Adding elements
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
print(heap) # [1, 3, 7, 5] - smallest is first
# Removing smallest
smallest = heapq.heappop(heap)
print(smallest) # 1
Convert List to Heap:
numbers = [5, 3, 7, 1, 9, 2]
heapq.heapify(numbers) # Rearrange in-place
print(numbers) # [1, 3, 2, 5, 9, 7]
Heap Applications
Find Kth Largest Element:
def kth_largest(nums, k):
# Keep heap of size k, smallest of k largest will be at top
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# Or use built-in
def kth_largest_simple(nums, k):
return heapq.nlargest(k, nums)[-1]
print(kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5
Maximum Sum Subarray of Size K (Sliding Window):
def max_sum_subarray(arr, k):
if len(arr) < k:
return None
# Calculate first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window
for i in range(k, len(arr)):
window_sum = window_sum - arr[i-k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
arr = [2, 1, 5, 1, 3, 2]
print(max_sum_subarray(arr, 3)) # 9 (subarray [5,1,3])
Part 10: Graphs - Connected Networks
Graph Representation
Graphs model relationships—social networks, road maps, web links.
Adjacency List (Most Common):
# Dictionary where key is node, value is list of neighbors
graph = {
‘A’: [’B’, ‘C’],
‘B’: [’A’, ‘D’, ‘E’],
‘C’: [’A’, ‘F’],
‘D’: [’B’],
‘E’: [’B’, ‘F’],
‘F’: [’C’, ‘E’]
}
Like a phone directory showing who knows whom!
Adjacency Matrix:
# For graph with nodes 0, 1, 2, 3
# Edge exists if matrix[i][j] = 1
graph_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
]
Breadth-First Search (BFS)
BFS explores level by level—like ripples in water.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
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
print(bfs(graph, ‘A’)) # [’A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]
Finding Shortest Path:
def shortest_path_bfs(graph, start, goal):
if start == goal:
return [start]
visited = {start}
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
if neighbor == goal:
return path + [neighbor]
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # No path found
print(shortest_path_bfs(graph, ‘A’, ‘F’)) # [’A’, ‘C’, ‘F’]
Depth-First Search (DFS)
DFS explores as deep as possible before backtracking—like exploring a maze.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs(graph, neighbor, visited))
return result
print(dfs(graph, ‘A’)) # [’A’, ‘B’, ‘D’, ‘E’, ‘F’, ‘C’]
Detect Cycle in Undirected Graph:
def has_cycle(graph):
visited = set()
def dfs_cycle(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs_cycle(neighbor, node):
return True
elif neighbor != parent: # Found visited node that’s not parent
return True
return False
# Check all components
for node in graph:
if node not in visited:
if dfs_cycle(node, None):
return True
return False
Part 11: Searching and Sorting - Fundamental Algorithms
Searching Algorithms
Linear Search:
def linear_search(arr, target):
for i, num in enumerate(arr):
if num == target:
return i
return -1
arr = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(arr, 22)) # 4
Check each element—simple but slow for large data.
Binary Search (Iterative):
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 # Search right half
else:
right = mid - 1 # Search left half
return -1
sorted_arr = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(sorted_arr, 22)) # 2
Binary Search (Recursive):
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
print(binary_search_recursive(sorted_arr, 22, 0, len(sorted_arr)-1))
Sorting Algorithms
Bubble Sort:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # Already sorted
break
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr.copy()))
Like bubbles rising—larger elements bubble to the end!
Selection Sort:
def selection_sort(arr):
n = len(arr)
for i in range(n):
# Find minimum in remaining unsorted array
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap minimum with first unsorted element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort(arr.copy()))
Select smallest, move to front, repeat!
Insertion Sort:
def insertion_sort(arr):
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
print(insertion_sort(arr.copy()))
Like sorting cards in your hand—pick one, insert in right position!
Merge Sort:
def merge_sort(arr):
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Conquer
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# Merge sorted halves
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
print(merge_sort([64, 34, 25, 12, 22, 11, 90]))
Divide array in half, sort each half, merge sorted halves!
Quick Sort:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([64, 34, 25, 12, 22, 11, 90]))
Pick a pivot, partition around it, repeat!
Using Python’s Built-in Sort:
arr = [64, 34, 25, 12, 22, 11, 90]
# sorted() creates new sorted list
sorted_arr = sorted(arr)
# list.sort() sorts in-place
arr.sort()
# Sort with custom key
students = [(’Alice’, 85), (’Bob’, 75), (’Charlie’, 90)]
students.sort(key=lambda x: x[1]) # Sort by marks
print(students) # [(’Bob’, 75), (’Alice’, 85), (’Charlie’, 90)]
Part 12: Dynamic Programming - Optimized Recursion
Understanding DP
Dynamic Programming is recursion + memory. Instead of recalculating, we remember!
Fibonacci - The Classic Example:
# Naive recursion - SLOW (exponential time)
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Memoization (Top-down DP)
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]
# Tabulation (Bottom-up DP)
def fib_tab(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]
print(fib_tab(10)) # 55
0/1 Knapsack Problem:
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = max value with first i items and capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Don’t include item i
dp[i][w] = dp[i-1][w]
# Include item i if it fits
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
values[i-1] + dp[i-1][w - weights[i-1]]
)
return dp[n][capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 9
Longest Common Subsequence:
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[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]
print(lcs(”ABCDGH”, “AEDFHR”)) # 3 (ADH)
Coin Change Problem:
def coin_change(coins, amount):
dp = [float(’inf’)] * (amount + 1)
dp[0] = 0 # 0 coins needed for amount 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float(’inf’) else -1
coins = [1, 2, 5]
print(coin_change(coins, 11)) # 3 (5+5+1)
Part 13: Bit Manipulation - Working with Bits
Basic Operations
# Check if even or odd
def is_even(n):
return (n & 1) == 0
print(is_even(4)) # True
print(is_even(7)) # False
# Count set bits (1s in binary)
def count_set_bits(n):
count = 0
while n:
n &= (n - 1) # Remove rightmost set bit
count += 1
return count
print(count_set_bits(7)) # 3 (binary: 111)
# Or simply
print(bin(7).count(’1’)) # 3
# Check if power of 2
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
print(is_power_of_two(16)) # True
print(is_power_of_two(18)) # False
# Swap two numbers without temp variable
a, b = 5, 10
a = a ^ b
b = a ^ b
a = a ^ b
print(a, b) # 10, 5
Generate All Subsets Using Bits
def subsets_using_bits(nums):
n = len(nums)
result = []
# 2^n possible subsets
for i in range(2 ** n):
subset = []
for j in range(n):
# Check if j-th bit is set
if i & (1 << j):
subset.append(nums[j])
result.append(subset)
return result
print(subsets_using_bits([1, 2, 3]))
# [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Part 14: Hashing - Fast Lookups
Hash Maps (Dictionaries)
# Frequency counter
def frequency_count(arr):
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
return freq
# Or using Counter
from collections import Counter
freq = Counter([1, 2, 2, 3, 3, 3])
print(freq) # Counter({3: 3, 2: 2, 1: 1})
# Two Sum Problem
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 []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
Subarray Sum Equals K
def subarray_sum(nums, k):
count = 0
curr_sum = 0
sum_freq = {0: 1} # Handle subarrays starting from index 0
for num in nums:
curr_sum += num
# If curr_sum - k exists, we found subarrays
if curr_sum - k in sum_freq:
count += sum_freq[curr_sum - k]
sum_freq[curr_sum] = sum_freq.get(curr_sum, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2)) # 2 ([1,1] appears twice)
Part 15: Trie - Prefix Tree
Trie Implementation
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
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):
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 starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Usage
trie = Trie()
trie.insert(”apple”)
trie.insert(”app”)
print(trie.search(”app”)) # True
print(trie.search(”appl”)) # False
print(trie.starts_with(”app”)) # True
Autocomplete System
def autocomplete(trie_root, prefix):
node = trie_root
# Navigate to prefix
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
# Find all words from this node
results = []
def dfs(node, current_word):
if node.is_end_of_word:
results.append(current_word)
for char, child_node in node.children.items():
dfs(child_node, current_word + char)
dfs(node, prefix)
return results
Part 16: Union-Find (Disjoint Set)
Basic Implementation
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# 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
return True
# Detect cycle in undirected graph
def has_cycle_union_find(edges, n):
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v): # Already connected = cycle!
return True
return False
Part 17: Advanced Problem-Solving Patterns
Sliding Window
Longest Substring Without Repeating Characters:
def longest_unique_substring(s):
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
print(longest_unique_substring(”abcabcbb”)) # 3 (”abc”)
Two Pointer Technique
Container With Most Water:
def max_area(height):
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
water = min(height[left], height[right]) * width
max_water = max(max_water, water)
# Move pointer at shorter height
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
print(max_area([1,8,6,2,5,4,8,3,7])) # 49
Binary Search on Answer
Minimum Capacity to Ship Packages:
def ship_within_days(weights, days):
def can_ship(capacity):
ships = 1
current_weight = 0
for weight in weights:
if current_weight + weight > capacity:
ships += 1
current_weight = 0
current_weight += weight
return ships <= days
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
Real-World Applications
Autocomplete System (Trie)
class AutocompleteSystem:
def __init__(self):
self.trie = Trie()
def add_word(self, word):
self.trie.insert(word)
def get_suggestions(self, prefix):
return autocomplete(self.trie.root, prefix)
# Usage
ac = AutocompleteSystem()
ac.add_word(”apple”)
ac.add_word(”application”)
ac.add_word(”apply”)
print(ac.get_suggestions(”app”)) # [’apple’, ‘application’, ‘apply’]
Task Scheduler (Heap)
def task_scheduler(tasks, priorities):
import heapq
heap = []
for task, priority in zip(tasks, priorities):
heapq.heappush(heap, (-priority, task)) # Negative for max-heap
schedule = []
while heap:
priority, task = heapq.heappop(heap)
schedule.append(task)
return schedule
Cache Implementation (HashMap)
class LRUCache:
def __init__(self, capacity):
self.cache = {}
self.capacity = capacity
self.order = []
def get(self, key):
if key in self.cache:
self.order.remove(key)
self.order.append(key)
return self.cache[key]
return -1
def put(self, key, value):
if key in self.cache:
self.order.remove(key)
elif len(self.cache) >= self.capacity:
oldest = self.order.pop(0)
del self.cache[oldest]
self.cache[key] = value
self.order.append(key)
Your Journey Begins Now
You now have a complete roadmap from zero to hero in Data Structures and Algorithms with Python. Every concept has been explained with examples you can run and modify.
Next Steps:
Practice Daily: Solve one problem every day on LeetCode or similar platforms
Visualize: Use tools like VisuAlgo.net to see algorithms in action
Build Projects: Create real applications using these concepts
Teach Others: Explaining concepts solidifies your understanding
Review Regularly: Revisit topics to maintain and deepen knowledge
Remember: mastery comes through consistent practice, not overnight. Every expert was once a beginner who refused to give up. Start simple, build gradually, and celebrate small wins. The skills you develop will serve your entire programming career.
Happy coding, and welcome to the world of Data Structures and Algorithms!