Mastering Algorithms in Python to Write Efficient Code

Algorithms in Python: In today’s tech-driven world, writing efficient code is not just about making your program run—it’s about making it fast, scalable, and maintainable. Python, a language loved for its simplicity, can be incredibly powerful when combined with algorithmic thinking.

This guide will walk you through mastering algorithms in Python—from understanding the basics to optimizing complex problems.

Whether you’re a beginner learning to translate problem statements into code, or an experienced developer aiming to improve performance, this guide is for you.

✅ What is an Algorithm?

An algorithm is a step-by-step procedure to solve a problem. It’s like a recipe in cooking — a finite set of instructions you follow to achieve a desired result.

🧠 Why Algorithms Matter in Python

Algorithms are at the core of programming – they define the logic and steps needed to solve problems efficiently.

Python is easy to read but not the fastest language out there. Writing poor algorithms in Python can make your programs slow and memory-hungry.

Knowing the right algorithm:

• Reduces runtime
  
• Minimizes memory usage
  
• Improves scalability
  
• Makes debugging easier
  

In Python, which is known for its simplicity and readability, understanding algorithms is especially important. Here is why:

🚀 1. Efficiency

• Algorithms determine how fast and memory efficient your code is.
• Python is slower than lower level languages, so using different algorithms offset performance costs.
• Example: Choosing a binary search (O(log n)) instead of a linear search (O(n)) significantly boosts performance in large datasets.

🧩 2. Problem Solving

• Most real world coding involves solving complex problems.
• Algorithms provide structured, reusable patterns(like searching, sorting, graph traversal etc)
• Knowing the right algorithm can turn a complicated problem into a manageable one.

🛠️ 3. Python Makes Algorithms Accessible

• Python syntax allows you to implement and understand algorithms easily.
• Libraries like heapq, isect, and collections implement algorithms under the hood.
• Focus on the logic, not the boilerplate code.

💼 4. Career and Interviews

• Tech-interviews are algorithm heavy.
• Python is favourite for whiteboard interviews because of its clean syntax.
• Practicing algorithms in Python helps you ace coding challenges on platforms like Leetcode, HackerRank etc.

🌍 5. Real-world Applications

• Whether you are working in data science, AI, web development, or automation, algorithms power your tools.
• Examples:
  • In AI- Backpropagation(an algorithm) for training neural networks.
  • In web – PageRank algorithm for search engine.
  • In finance – Algorithmic trading strategies.

etc.

---

📝 Step-by-Step: Turning Statements into Code

When you’re given a problem, use this roadmap:

1. Understand the problem.
   
   • What are the inputs and outputs?
     
   • Are there constraints (e.g., time, memory)?
     
   • Example:
     
     “Find the first non-repeating character in a string.”
     
     
2. Break it down.
   
   • Convert the problem into smaller steps.
     
   • Think of possible edge cases.
     
3. Choose the right data structure.
   
   • Lists, sets, dictionaries, heaps, etc.
     
4. Write pseudocode.
   
   • Helps organize your thoughts.
     
5. Code in Python.
   
   • Use meaningful variable names, comments, and built-in functions.
     
6. Test and Optimize.
   

---

🧰 Beginner’s Toolkit: Core Algorithms

1. Searching Algorithms

Searching algorithms are used to find the location of a target element within a data structure.

• Linear Search
  
• Binary Search
  

Linear Search

🧠 What Is Linear Search?

Linear search(also called sequential search) is a simple algorithm used to find a specific value in a list or array by checking each element one by one from start to end.

📦 When to Use It:

• The list is unsorted.
• The list is small or you don’t need optimal performance.
• You want a simple solution quickly.

🔧 How It Works:

1. Start at Index 0
2. Compare the target value with the current element.
3. If it’s a match, return the index.
4. If not, move to the next element.
5. If you reach the end of the list without finding the value, return -1 or (None).

🧪 Python Implementation:

def linear_search(arr, target):

    for index in range(len(arr)):

        if arr[index] == target:

            return index  # Target found

    return -1  # Target not found

🧾 Example:

numbers = [10, 25, 30, 45, 50]

target = 30

result = linear_search(numbers, target)

if result != -1:

    print(f"Element found at index {result}")

else:

    print("Element not found")

📈 Time Complexity:

• Best case: O(1) — if the item is at the beginning
  
• Worst case: O(n) — if the item is at the end or not in the list
  
• Space complexity: O(1)

Binary Search

🧠 What Is Binary Search?

Binary Search is an efficient algorithm to find a target value in a sorted list. It works by repeatedly dividing the search space in half, eliminating half of the elements each time.

📦 When to Use It:

• The list must be sorted (ascending or descending)
• You need fast lookup on large datasets.
• Performance is critical – binary search is much faster than linear search for large lists.

🔧 How It Works:

1. Find the middle element.
2. If it’s the target, return its index.
3. If the target is less than the middle, search the left half.
4. If it is greater, search the right half.
5. Repeat until the target is found or the range is empty.

🧪 Python Implementation:

def binary_search(arr, target):

    low = 0

    high = len(arr) - 1

    while low <= high:

        mid = (low + high) // 2

        if arr[mid] == target:

            return mid  # Target found

        elif arr[mid] < target:

            low = mid + 1  # Search right half

        else:

            high = mid - 1  # Search left half

    return -1  # Target not found

🧾 Example:

numbers = [10, 20, 30, 40, 50, 60]

target = 40

result = binary_search(numbers, target)

if result != -1:

    print(f"Element found at index {result}")

else:

    print("Element not found")

✅ Output:

Element found at index 3

📈 Time Complexity:

• Best case: O(1) — if the item is in the middle
  
• Average/Worst case: O(log n)
  
• Space complexity: O(1) (iterative version)

⚠️ Important Note:

Binary Search only works on sorted lists.
If your data isn’t sorted, sort it first (which takes O(n log n)) before applying binary search.

2. Sorting Algorithms

Sorting algorithms arrange elements of a list for an array in specific order, for example ascending or descending. 

Common sorting algorithms and their Python implementation includes:

• Bubble Sort
  
• Insertion Sort
  
• Merge Sort
  
• Quick Sort (Recursion!)
  

🔃 Bubble Sort in Python

🧠 What Is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

📦 When to Use It:

• For educational purposes to understand sorting basics.
• When working with very small datasets.
• When code simplicity is more important than performance.
• Not recommended for large datasets – it is one of the least efficient sorting algorithms.

🔧 How It Works:

1. Start at the beginning of the list.
2. Compare the current element with the next one.
3. If they are out of order, swap them.
4. Repeat the process for each pair in the list.
5. Continue iterating through the list until no swaps are needed.

🧪 Python Implementation:

def bubble_sort(arr):

    n = len(arr)

    for i in range(n):

        # Track whether a swap was made

        swapped = False

        for j in range(0, n - i - 1):

            if arr[j] > arr[j + 1]:

                # Swap if elements are in wrong order

                arr[j], arr[j + 1] = arr[j + 1], arr[j]

                swapped = True

        # If no swaps occurred, the list is sorted

        if not swapped:

            break

🧾 Example:

numbers = [64, 34, 25, 12, 22, 11, 90]

bubble_sort(numbers)

print("Sorted array:", numbers)

✅ Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

📈 Time Complexity:

Best case: O(n) — if the list is already sorted (with optimization)

Average case: O(n²)

Worst case: O(n²) — for reverse-sorted list

Space complexity: O(1) — in-place sorting

🔁 Visual Analogy:

Like bubbles rising in water — larger elements “bubble up” to the end with each pass.

📥 Insertion Sort in Python

🧠 What Is Insertion Sort?

Inserting sort is a simple sorting algorithm that builds the final sorted list one element at a  time by taking each element and inserting it into its correct position among the previously sorted elements.

📦 When to Use It:

For small datasets.

When the list is already nearly sorted.

In scenarios where stability (Preserving original order of equal items) is important 

It’s also commonly used in educational settings to teach sorting logic.

🔧 How It Works:

1. Start from the second element.
2. Compare it with the element before.
3. Shift elements that are greater than the current element one position to the right.
4. Insert the current element into the correct position.
5. Repeat until the list is sorted.

🧪 Python Implementation:

def insertion_sort(arr):

    for i in range(1, len(arr)):

        key = arr[i]

        j = i - 1

        # Move elements of arr[0..i-1] that are greater than key

        while j >= 0 and arr[j] > key:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key

🧾 Example:

numbers = [12, 11, 13, 5, 6]

insertion_sort(numbers)

print("Sorted array:", numbers)

✅ Output:

Sorted array: [5, 6, 11, 12, 13]

📈 Time Complexity:

• Best case: O(n) — when the list is already sorted
• Average case: O(n²)
• Worst case: O(n²) — when the list is reverse sorted
• Space complexity: O(1) — sorts in-place

🧠 Why It’s Called “Insertion” Sort:

Each element is “inserted” into the right place within the sorted portion of the array.

🆚 Bubble vs Insertion:

• Insertion Sort is usually faster than Bubble Sort in practice.
  
• Both are O(n²) algorithms, but Insertion Sort performs fewer swaps.

🔀 Merge Sort in Python

🧠 What Is Merge Sort?

Merge sort is a divide and conquer sorting algorithm. It works by dividing the list into smaller sublists, sorting those recursively, and then merging them back together in sorted order.

📦 When to Use It:

• When you need a stable and predictable sorting algorithm.
• For large datasets where performance matters.
• In scenarios where O(n log n) time complexity is ideal(e.g ., external sorting, linked lists).

⚠️ Merge sort is not an in-place sort – it requires additional memory.

🔧 How It Works:

1. Divide the list into halves until each sublist contains a single element.
2. Recursively sort each half.
3. Merge the sorted halves back together.

🧪 Python Implementation:

def merge_sort(arr):

    if len(arr) > 1:

        mid = len(arr) // 2

        left_half = arr[:mid]

        right_half = arr[mid:]

        merge_sort(left_half)

        merge_sort(right_half)

        # Merge two sorted halves

        i = j = k = 0

        # Copy data to temp arrays

        while i < len(left_half) and j < len(right_half):

            if left_half[i] < right_half[j]:

                arr[k] = left_half[i]

                i += 1

            else:

                arr[k] = right_half[j]

                j += 1

            k += 1

        # Checking for any remaining elements

        while i < len(left_half):

            arr[k] = left_half[i]

            i += 1

            k += 1

        while j < len(right_half):

            arr[k] = right_half[j]

            j += 1

            k += 1

🧾 Example:

numbers = [38, 27, 43, 3, 9, 82, 10]

merge_sort(numbers)

print("Sorted array:", numbers)

✅ Output:

Sorted array: [3, 9, 10, 27, 38, 43, 82]

📈 Time Complexity:

• Best case: O(n log n)
  
• Average case: O(n log n)
  
• Worst case: O(n log n)
  
• Space complexity: O(n) — due to use of temporary arrays

⚙️ Why Use Merge Sort?

Merge sort offers consistent performance, even on worst case input.

It’s preferred in multi-threaded and parallel environments because of its divide and conquer nature.

🧠 Merge vs Quick Sort:

Feature	Merge Sort	Quick Sort
Time (avg)	O(n log n)	O(n log n)
Time (worst)	O(n log n)	O(n²)
Space	O(n)	O(log n)
Stable Sort	✅ Yes	❌ No (by default)
In-place	❌ No	✅ Yes

⚡ Quick Sort (Recursive) in Python

🧠 What Is Quick Sort?

Quick sort is a highly effective divide and conquer sorting algorithm that works by selecting a pivot, partitioning the lists into elements less than and greater than the pivot, and recursively sorting the sublists.

📦 When to Use It:

• When you use fast sorting on average.
• For large datasets where in-place sorting is preferred.
• In environments where space is limited compared to merge sort.

🔧 How It Works (Recursive):

1. Choose a pivot element (commonly the last, first, or random element)
2. Partitions the array into:
   1. Elements less than the pivot.
   2. Elements greater than or equal to pivot.
3. Recursively apply Quick Sort to the subilists.
4. Combine the results.

🧪 Python Implementation (Recursive):

def quick_sort(arr):

    if len(arr) <= 1:

        return arr  # Base case: already sorted

    pivot = arr[-1]  # Choosing the last element as pivot

    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)

🧾 Example:

numbers = [10, 7, 8, 9, 1, 5]

sorted_numbers = quick_sort(numbers)

print("Sorted array:", sorted_numbers)

✅ Output:

Sorted array: [1, 5, 7, 8, 9, 10]

📈 Time Complexity:

• Best case: O(n log n) — balanced partitions
  
• Average case: O(n log n)
  
• Worst case: O(n²) — when pivot is always the smallest or largest element
  
• Space complexity: O(log n) for recursive call stack (in-place version)

🔁 Why It’s Called “Quick” Sort:

Despite the worst-case, it often outperforms other sorting algorithms in real-world use due to excellent cache performance and in-place sorting.

⚔️ Merge Sort vs Quick Sort:

Feature	Quick Sort	Merge Sort
Time (avg)	O(n log n)	O(n log n)
Time (worst)	O(n²)	O(n log n)
Space	O(log n)	O(n)
In-place	✅ Yes	❌ No
Stable	❌ No (by default)	✅ Yes
Real-world use	⭐ High	⭐⭐ Medium

3. Basic Recursion

• Factorial
  
• Fibonacci (inefficient, but a learning tool)

🧮 Factorial (Recursive) in Python

🧠 What Is Factorial?

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n.

Mathematically:

n! = n × (n – 1) × (n – 2) × … × 1  

0! = 1 (by definition)

Factorial is often used in combinatorics, permutations, probability, and mathematical algorithms.

📦 When to Use It:

• When solving problems related to combinations (nCr) or permutations (nPr).
  
• In recursion practice — it’s one of the best beginner examples.
  
• As part of mathematical problems in data science, statistics, or theory of computation.

🔧 How It Works (Recursive):

1. If n == 0, return 1 (base case).
   
2. Otherwise, return n * factorial(n – 1).
   

This repeats until it reaches the base case.

🧪 Python Implementation (Recursive):

def factorial(n):

    if n == 0 or n == 1:

        return 1  # Base case

    else:

        return n * factorial(n - 1)  # Recursive call

🧾 Example:

print(factorial(5))  # Output: 120

print(factorial(0))  # Output: 1

✅ Output:

120

1

📈 Time & Space Complexity:

• Time complexity: O(n) — one recursive call per number
  
• Space complexity: O(n) — due to the recursion call stack

⚠️ Limitations:

• For large values of n, recursion may hit the maximum recursion depth in Python.
  
• Consider using iteration or math.factorial() for safer production-level code.

🔁 Iterative Alternative:

def factorial_iterative(n):

    result = 1

    for i in range(2, n + 1):

        result *= i

    return result

🧠 Why Learn This?

Understanding the recursive factorial concept is the gateway to recursion, and lays the foundation for more complex problems like Fibonacci, tree traversal, and dynamic programming.

🔢 Fibonacci Sequence (Recursive, Inefficient) in Python

🧠 What Is the Fibonacci Sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

Mathematically:

F(0) = 0  

F(1) = 1  

F(n) = F(n-1) + F(n-2)  for n > 1

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, …

📦 When to Use It:

• As a classic recursion example to teach problem-solving.
  
• To illustrate overlapping subproblems and inefficiency, paving the way to Dynamic Programming.
  
• Used in mathematical models, nature, data structures, and algorithm design.
  

⚠️ The basic recursive version is not efficient — it’s meant for learning recursion, not for performance.

🔧 How It Works (Recursive):

1. Define the base cases: F(0) = 0, F(1) = 1.
   
2. Recursively compute: F(n) = F(n-1) + F(n-2).
   

🧪 Python Implementation (Recursive):

def fibonacci(n):

    if n == 0:

        return 0

    elif n == 1:

        return 1

    else:

        return fibonacci(n - 1) + fibonacci(n - 2)

🧾 Example:

print(fibonacci(5))  # Output: 5

print(fibonacci(7))  # Output: 13

✅ Output:

5

13

📈 Time & Space Complexity:

• Time complexity: O(2ⁿ) — exponential time due to repeated calculations.
  
• Space complexity: O(n) — due to the recursion stack.

🛑 Why It’s Inefficient:

• Recalculates the same values multiple times.
  
• For example, fibonacci(5) will compute fibonacci(3) twice, and fibonacci(2) three times, etc.

💡 Optimized Alternatives:

def fibonacci_memo(n, memo={}):

    if n in memo:

        return memo[n]

    if n <= 1:

        return n

    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)

    return memo[n]

✅ Iterative (Bottom-Up DP):

def fibonacci_iter(n):

    if n == 0:

        return 0

    a, b = 0, 1

    for _ in range(2, n + 1):

        a, b = b, a + b

    return b

🌱 Why Learn This?

Fibonacci is a rite of passage into understanding recursion, and a perfect example to show why optimization (like memoization and dynamic programming) matters.

4. Mathematical Algorithms

• GCD/LCM
  
• Prime Number Checks
  
• Modular Arithmetic
  

1️⃣ GCD (Greatest Common Divisor)

🧠 What Is GCD?

GCD (also called HCF – Highest Common Factor) of two integers is the largest number that divides both without leaving a remainder.

Example:

GCD(12, 18) = 6

📦 When to Use It:

• Simplifying fractions (e.g., 8/12 → 2/3).
  
• Calculating LCM.
  
• Common in number theory, modular arithmetic, and cryptography.

🔧 How It Works (Euclidean Algorithm):

1. If b == 0, return a.
   
2. Otherwise, compute gcd(b, a % b).
   

This continues until the remainder becomes 0.

🧪 Python Implementation (Recursive):

def gcd(a, b):

    if b == 0:

        return a

    else:

        return gcd(b, a % b)

🧾 Example:

print(gcd(48, 18))  # Output: 6

✅ Output:

6

📈 Time & Space Complexity (GCD):

• Time complexity: O(log(min(a, b)))
  
• Space complexity: O(log(min(a, b))) due to recursion

2️⃣ LCM (Least Common Multiple)

🧠 What Is LCM?

LCM of two numbers is the smallest number that is a multiple of both.

Example:

LCM(4, 6) = 12

📦 When to Use It:

• Scheduling problems (e.g., when two cycles need to align).
  
• Calculations involving fractions, modular math, and simultaneous events.

🔧 How It Works:

You can compute LCM using GCD:

LCM(a, b) = abs(a * b) // GCD(a, b)

🧪 Python Implementation:

def lcm(a, b):

    return abs(a * b) // gcd(a, b)

🧾 Example:

print(lcm(4, 6))   # Output: 12

print(lcm(21, 6))  # Output: 42

✅ Output:

12

42

📈 Time & Space Complexity (LCM):

• Time complexity: O(log(min(a, b))) — depends on GCD
  
• Space complexity: O(log(min(a, b))) — due to recursive GCD

🔁 Real-World Use Case:

Suppose two traffic lights blink every 12s and 18s. They blink together every LCM(12, 18) = 36 seconds.

🔍 Bonus: Using Python’s Built-in Functions

import math

print(math.gcd(48, 18))   # 6

print(math.lcm(4, 6))     # 12 (Python 3.9+)

🔎 Prime Number Checks in Python

🧠 What Is a Prime Number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Examples:

• ✅ Prime: 2, 3, 5, 7, 11, 13, …
  

📦 When to Use It:

• Cryptography (RSA encryption depends on primes)
  
• Number theory problems
  
• Competitive programming and algorithm puzzles
  

🔧 How It Works (Basic Trial Division):

1. If n <= 1, it’s not prime.
   
2. Check divisibility from 2 up to √n.
   
3. If divisible by any number in that range, it’s not prime.
   

Why √n?

If n has a factor larger than √n, the corresponding smaller factor must already have been found.

🧪 Python Implementation:

import math

def is_prime(n):

    if n <= 1:

        return False

    if n == 2:

        return True

    if n % 2 == 0:

        return False

    for i in range(3, int(math.sqrt(n)) + 1, 2):

        if n % i == 0:

            return False

    return True

🧾 Example:

print(is_prime(11))  # Output: True

print(is_prime(20))  # Output: False

print(is_prime(2))   # Output: True

✅ Output:

True

False

True

📈 Time & Space Complexity:

• Time complexity: O(√n)
  
• Space complexity: O(1)

🔎 Edge Cases:

Input	Result
0	❌ False
1	❌ False
2	✅ True
Negative numbers	❌ False

⚡ Optimizations & Variants:

• Use Sieve of Eratosthenes for checking multiple primes up to n.
  
• For large primes (e.g., cryptography), use Miller–Rabin or Fermat primality tests (probabilistic).
  

📘 Real-World Use Case:

Prime numbers are used to generate public-private keys in encryption algorithms (e.g., RSA), because factoring large primes is computationally hard.

➗ Modular Arithmetic in Python

🧠 What Is Modular Arithmetic?

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” after reaching a certain value — called the modulus.

Formally:

a mod n = remainder when a is divided by n

Examples:

• 10 % 3 = 1 → 10 divided by 3 leaves remainder 1
  
• 17 % 5 = 2

📦 When to Use It:

• Cryptography (RSA, hashing, digital signatures)
  
• Computer graphics (circular motion, angle wrapping)
  
• Competitive programming (handling large numbers)
  

🔧 How It Works:

The modulo operation finds the remainder after division.

Key properties:

Property	Example
(a + b) % n = (a % n + b % n) % n	(7 + 5) % 4 = 12 % 4 = 0
(a × b) % n = (a % n × b % n) % n	(3 × 4) % 5 = 12 % 5 = 2
(a – b) % n = (a % n – b % n + n) % n	Safe from negatives

🧪 Python Examples:

print(10 % 3)        # 1

print((7 + 5) % 4)   # 0

print((3 * 4) % 5)   # 2

print((10 - 3) % 7)  # 7 % 7 = 0

✅ Output:

1

0

2

0

⚠️ Negative Modulo in Python:

Python handles negative numbers differently from some other languages:

print(-5 % 3)   # Output: 1

Python always returns a non-negative remainder, which aligns with most mathematical conventions.

💡 Modular Inverse (Advanced Concept):

When dividing under mod, we use a modular inverse:

To compute:

a / b mod m  ⟶  a × b⁻¹ mod m

Where b⁻¹ is the modular inverse of b modulo m.

In Python (using Fermat’s little theorem for prime m):

def mod_inverse(b, m):

    return pow(b, m - 2, m)

⏰ Real-World Example (Clock Math):

def add_hours(current_hour, hours_to_add):

    return (current_hour + hours_to_add) % 12

print(add_hours(9, 5))  # Output: 2

🧠 Why It Matters:

Modular arithmetic is the backbone of many secure systems, competitive programming tricks, and efficient numeric algorithms.

📚 Must-Know Data Structures (Tightly Connected with Algorithms)

Make sure you’re also comfortable with:

• Arrays / Lists
  
• Strings & pattern matching (sliding window)
  
• HashMaps (dicts in Python)
  
• Stacks & Queues
  
• Trees & Binary Trees
  
• Graphs (BFS / DFS)
  

✅ Algorithms are often tested through these structures, not in isolation.

🧠 Final Recommended Focus Set

For Interview Prep + Real-World Usage, prioritize:

✅ Must-Know	⏳ Good to Know (Optional/Low Priority)
Binary Search	Linear Search (basic only)
Merge Sort & Quick Sort	Bubble / Insertion Sort (theory only)
Recursion basics	Recursive Fibonacci (inefficient)
Backtracking	Selection Sort
GCD & LCM	Extended Euclidean Algorithm (advanced)
Prime Check	Sieve of Eratosthenes (only if needed)
Modular Arithmetic	Modular Inverse (if doing cryptography)

✅ Final Summary:

✅ Master For Interviews & Work

Binary Search & Variants

Quick Sort / Merge Sort

Recursion & Backtracking

Hash Maps (dict) usage

GCD / LCM

Modular Arithmetic (especially mod % 1e9+7)

Prime Checks (basic efficient version)

Sliding Window / Two Pointers

---

📦 Intermediate: Data Structures + Algorithms

🔹 1. Hashing (Dictionaries & Sets)

Hashing is a technique used to store and retrieve data quickly. It’s the foundation behind two important data structures: dictionaries and sets.

A dictionary (also known as a hash map) stores data in key-value pairs. Think of it like a phone book — you look up a name (key) to find a phone number (value). This allows for very fast lookups.

A set is a collection of unique items — it automatically removes duplicates. Sets are great when you want to check if something exists or ensure every item is only stored once.

What makes both of these fast is how they use a hash function to figure out where to store or find data. In most cases, this means you can access data in constant time, or O(1).

Hashing is extremely useful in problems like:

• Checking for duplicates in a list
  
• Counting how many times something appears
  
• Building fast lookup tables
  

As you move forward with algorithms, dictionaries and sets will become some of your most-used tools.

Use cases:

• Finding duplicates
  
• Counting frequency
  

Here we are counting frequency, and doing it using Python’s collections.Counter.

from collections import Counter

def first_unique_char(s):

    freq = Counter(s)

    for i, char in enumerate(s):

        if freq[char] == 1:

            return i

    return -1

🔹 2. Stacks and Queues

Stacks and queues are simple but powerful data structures that help manage data in specific orders.

🥞 What is a Stack?

A stack works just like a stack of plates — the last plate you put on top is the first one you take off.
This is called LIFO: Last In, First Out.

You can:

• Push an item (add to the top)
  
• Pop an item (remove from the top)
  
• Peek at the top item without removing it
  

📌 Real-world examples:

• Undo/redo buttons in text editors
  
• Back button in a browser
  

🚌 What is a Queue?

A queue works like a line at a checkout counter — the first person in line is the first one served.
This is called FIFO: First In, First Out.

You can:

• Enqueue an item (add to the back)
  
• Dequeue an item (remove from the front)
  
• Peek at the front item
  

📌 Real-world examples:

• Print jobs in a printer queue
  
• Task scheduling in operating systems
  

💡 Why Are They Important?

Stacks and queues are essential for solving problems like:

• Reversing data
  
• Traversing trees or graphs
  
• Managing order in asynchronous tasks
  

They’re also fundamental building blocks for more complex data structures and algorithms.

Use list, deque from collections.

from collections import deque

stack = []

stack.append(1)

stack.pop()

queue = deque()

queue.append(1)

queue.popleft()

🔹 3. Linked Lists

A linked list is a data structure used to store a sequence of elements, just like an array — but with a twist.

🔗 What Is a Linked List?

Unlike arrays, where elements are stored side by side in memory, a linked list connects elements using pointers.

Each element (called a node) contains:

• The data (the actual value)
  
• A reference (or pointer) to the next node in the list
  

So it looks something like:
[Data | Next] → [Data | Next] → [Data | None]

🔄 Types of Linked Lists

1. Singly Linked List
   
   • Each node points to the next node only.
     
2. Doubly Linked List
   
   • Each node points to both the next and previous node.
     
3. Circular Linked List
   
   • The last node connects back to the first node, forming a loop.
     

⚙️ Common Operations

• Insert a new node (at the beginning, middle, or end)
  
• Delete a node
  
• Traverse (go through) the list
  
• Search for a value
  

These operations often take O(n) time, since you may need to walk through the list to find a specific node.

📌 Real-World Uses

• Building stacks and queues internally
  
• Browser history (back and forward)
  
• Music playlists or navigation systems
  

💡 Why Use Linked Lists?

• Great when you need flexible memory usage — unlike arrays, you don’t need to define a fixed size.
  
• Easy to insert or delete elements without shifting the whole structure (unlike arrays).
  
• Slightly more complex to work with, but essential for understanding how memory and pointers work.

Useful for:

• Dynamic memory usage
  
• Reversing in-place
  

🔹 4. Graphs and Trees

Graphs and trees are advanced data structures that help us model relationships and connections between data.

They’re essential for solving real-world problems like network routing, social media, maps, and file systems.

🌳 What Is a Tree?

A tree is a special type of graph with a hierarchical structure. It starts with a root node and branches out to child nodes.

Each node can have:

• One parent
  
• Zero or more children
  

A binary tree is a common type where each node has at most two children (left and right).

🌲 Common Tree Types:

• Binary Tree – Each node has up to 2 children
  
• Binary Search Tree (BST) – A sorted binary tree (left < root < right)
  
• Trie – Special tree for string searching (used in autocomplete)
  
• Heap – Used in priority queues and efficient sorting
  

📈 What Is a Graph?

A graph is a collection of nodes (also called vertices) connected by edges.
Unlike trees, graphs can have cycles (paths that loop back) and more complex connections.

Graphs can be:

• Directed (edges have a direction, like one-way streets)
  
• Undirected (edges go both ways)
  
• Weighted (edges have costs, like distances or time)
  

🔁 Common Graph Uses:

• GPS navigation systems (shortest path)
  
• Social networks (friend/follow relationships)
  
• Web page ranking (Google uses a graph algorithm!)
  

⚙️ Why Are Trees and Graphs Important?

• Trees allow fast searching, insertion, and sorting
  
• Graphs model complex, real-world systems with many connections
  
• They’re used in AI, networking, search engines, and more
  

💡 Beginner Tip:

Graphs and trees may seem complicated at first, but once you start visualizing them, they become much easier to understand. Start by drawing them out and learning basic traversal methods like DFS (Depth-First Search) and BFS (Breadth-First Search).

Explore:

• BFS (Breadth-First Search)
  
• DFS (Depth-First Search)
  
• Tree Traversals (in-order, pre-order, post-order)
  

🔹 5. Dynamic Programming

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into smaller subproblems and storing the results to avoid repeating the same work.

🧠 What Is Dynamic Programming?

Imagine solving a problem where some parts repeat over and over. Instead of solving them again every time, DP lets you solve once, remember it, and reuse it.

This technique is especially helpful in problems that have:

• Overlapping subproblems
  
• Optimal substructure (the solution can be built from smaller solutions)
  

🧮 Classic Example

Fibonacci Sequence
Without DP: You recalculate the same numbers again and again (slow!).
With DP: You store results in a list or table and reuse them — much faster!

🧰 Two Main Approaches

1. Top-Down (Memoization)
   
   • Use recursion + store results in a dictionary or array.
     
   • You solve the problem from the top and “remember” answers as you go.
     
2. Bottom-Up (Tabulation)
   
   • Use a loop and table to build up the solution from the smallest subproblem.
     
   • Often more efficient and avoids recursion.
     

📌 Real-World Problems Solved by DP

• Fibonacci numbers
  
• Knapsack problem (packing with limited space)
  
• Coin change (minimum coins to make a total)
  
• Longest common subsequence (used in diff tools, DNA matching)
  

💡 Why Learn Dynamic Programming?

Dynamic Programming is one of the most common and challenging topics in coding interviews.
It teaches you to think efficiently, avoid unnecessary work, and solve big problems with smart strategies.

🔓 Pro Tip: Start with simple DP problems like Fibonacci or climbing stairs, and gradually move to tougher ones. Once you get the hang of identifying overlapping subproblems, DP becomes much easier (and even fun!).

Used when:

• Overlapping subproblems
  
• Optimal substructure
  

Example: Fibonacci with memorization

def fib(n, memo={}):

    if n in memo: return memo[n]

    if n <= 1: return n

    memo[n] = fib(n-1, memo) + fib(n-2, memo)

    return memo[n]

Also Read:

• Python Data Structures: A Complete Guide for Beginners and Beyond
• Big O Notation Tutorial: A Complete Guide

Understanding Time & Space Complexity: A Beginner’s Guide to Big O Notation

⏳ What is Time Complexity?

Time complexity measures how the running time of an algorithm increases as the size of input data grows.

• Imagine you have a list of 10 items to search.
  
• If it takes 1 second to search for 10 items, what happens if you have 100 items?
  
• Does the time increase a little? a lot? or stay the same?
  

Time complexity tells you how quickly the time needed grows as input size (usually called n) grows.

💾 What is Space Complexity?

Space complexity measures how much extra memory (space) an algorithm needs as the input size grows.

• For example, does the algorithm need to create new lists or data structures that grow as the input grows?
  
• Or does it just use a fixed amount of space regardless of input size?
  

🧮 What is Big O Notation (O(…))?

Big O notation is a way to express time or space complexity in a simplified form — focusing only on the largest factor that affects growth.

• It tells you the worst-case scenario (maximum time or space).
  
• It ignores smaller constants and lower order terms because they become insignificant for very large inputs.
  

Common Big O complexities explained with examples:

Big O Notation	What it means	Real-life Example	Time taken if input doubles (n → 2n)
O(1)	Constant time — does NOT grow with input size	Checking the first item in a list	Same time
O(log n)	Logarithmic — grows slowly	Binary search (cutting search space in half)	Increases slightly
O(n)	Linear — grows proportionally	Checking every item in a list	Doubles
O(n log n)	Linearithmic — grows faster than linear, slower than quadratic	Efficient sorting algorithms like Merge Sort	More than doubles but less than quadruples
O(n²)	Quadratic — grows very fast	Nested loops (checking all pairs)	Quadruples

Visual Example with Searching:

• Linear Search: Check each item one by one → O(n) time
  If 10 items take 1 second, 100 items take ~10 seconds.
  
• Binary Search: Split the list in half each time → O(log n) time
  If 10 items take 1 second, 100 items take ~3.3 seconds (log base 2 of 100 ≈ 6.6 steps, much less than 100).
  

Why Does It Matters?

• It helps you choose efficient algorithms.
  
• Improves your program’s speed and memory usage.
  
• Essential for handling large inputs without crashing or timing out.
  

Summary Table:

Concept	Meaning	Example
Time Complexity	How fast an algorithm runs	Searching a list
Space Complexity	How much memory it uses	Creating new lists or arrays
O(1)	Constant time	Accessing array element by index
O(n)	Linear time	Looping through list elements
O(log n)	Logarithmic time	Binary search
O(n²)	Quadratic time	Nested loops

🧠 1. What is O?

• O stands for “Order of”.
  
• It’s like saying: “This is the general shape of how the algorithm grows.”
• It tells us the growth rate of an algorithm as the input size increases.
• It focuses on the worst-case scenario.
  

Think of it as a label we put on a function to describe its speed or efficiency.

🔢 2. What is n?

• n is the size of the input.
  
  • Example: If you have a list with 10 items, n = 10.
    

So:

• O(n) means: As n increases, the time increases linearly.
  
  • 10 items → 10 steps
    
  • 100 items → 100 steps
    

3. log — Logarithm

• log n means: “How many times can you divide n by 2 before you get to 1?”
  

For example:

n	log₂(n) (rounded)
8	3 → (8 → 4 → 2 → 1)
16	4 → (16 → 8 → 4 → 2 → 1)
32	5 → (32 → 16 → 8 → 4 → 2 → 1)

So:

• log n grows much slower than n
  
• That’s what makes O(log n) algorithms super efficient

📈 4. What is log n?

• log n (logarithmic) grows very slowly as n increases.
  
• It’s used when algorithms cut the problem in half repeatedly (like binary search).
  

n	log₂(n) (rounded)
8	3
16	4
32	5
1,000,000	~20

So:

• O(log n) means the algorithm gets only a little slower, even when input grows a lot.
  
• Super efficient!

🧠 5. Other Common Big O Terms

Big O	Name	Growth Type	Example Problem
O(1)	Constant time	🚀 Fastest	Accessing an array element
O(log n)	Logarithmic time	⚡ Very fast	Binary search
O(n)	Linear time	🔁 Grows with input size	Looping through a list
O(n log n)	Linearithmic time	⏳ Efficient sorting	Merge Sort, Quick Sort
O(n²)	Quadratic time	🐌 Slow on large input	Nested loops (e.g., Bubble Sort)

---

🧪 Example: Searching in a List

Let’s say you’re looking for a number in a list of 1,000 items.

• Linear Search → O(n)
  Check one by one. Worst case: 1,000 steps.
  
• Binary Search → O(log n)
  Cut the list in half each time. Worst case: ~10 steps!
  

---

✅ Summary (Cheat Sheet):

Symbol	Meaning
O(…)	“Order of…” — how fast/slow it grows
n	Size of the input
log n	Logarithmic growth (very slow)
n²	Squared growth (very fast increase!)

---

🚀 Advanced: Optimization & Performance

🧠 1. Time Complexity Analysis (Big O)

Learn to estimate:

• Constant: O(1)
  
• Logarithmic: O(log n)
  
• Linear: O(n)
  
• Quadratic: O(n^2)
  
• Etc.
  

Use time module to test execution time.

import time

start = time.time()

# your code

print("Execution time:", time.time() - start)

🧮 2. Space Complexity

• Avoid creating unnecessary data structures.
  
• Reuse variables.
  

⚡ 3. Use Pythonic Functions

• any(), all(), zip(), enumerate(), map(), filter(), sum() — often faster and cleaner.
  

🧰 4. Built-in Libraries

• heapq for priority queues
  
• bisect for binary search
  
• functools.lru_cache for memoization
  
• collections.defaultdict, Counter, deque
  

🧪 5. Profiling Tools

• cProfile (standard profiler)
  
• line_profiler (line-by-line analysis)
  

---

✅ Best Practices to Write Efficient Python Code

Practice	Why it matters
Write clean, readable code	Easier to debug and optimize
Use list comprehensions	More concise and faster
Avoid unnecessary loops	Reduce time complexity
Cache/memoize results	Improve performance in recursion
Use appropriate data structures	Right tool = better performance
Always test with large inputs	Ensure scalability

---

📚 Resources to Go Deeper

• 📘 “Grokking Algorithms” by Aditya Bhargava
  
• 📘 “Introduction to Algorithms” by Cormen (CLRS)
  
• 🔗 LeetCode
  
• 🔗 HackerRank
  
• 🔗 Real Python
  
• 🔗 GeeksforGeeks
  

---

🔚 Conclusion Algorithms in Python

Mastering algorithms in Python is a journey. Start with basic logic, gradually learn to use Pythonic tools, and optimize based on problem needs. Remember, writing efficient code is not just about passing test cases—it’s about writing code that scales, performs, and lasts.

“First, solve the problem. Then, write the code.” — John Johnson

❓ Frequently Asked Questions (FAQ) on Algorithms in Python