Algorithm Basics: Problem-Solving Patterns

Why Algorithms Matter

Algorithms are step-by-step procedures for solving problems. Understanding them helps:

• Solve problems efficiently


• Understand code behavior


• Choose right approaches


• Write better solutions

Big O Notation

How performance scales with input size:

Notation

Name

Example

O(1)	Constant	Array access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Good sorting
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Brute force

What It Means

For n = 1000:

• O(1): 1 operation


• O(log n): ~10 operations


• O(n): 1,000 operations


• O(n log n): ~10,000 operations


• O(n²): 1,000,000 operations

Searching

Linear Search

Check each element:

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

Time: O(n)
When: Unsorted data, small lists

Binary Search

Divide and conquer (sorted data):

def binary_search(items, target):
    left, right = 0, len(items) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Time: O(log n)
When: Sorted data

Sorting

Built-in Sorting

Usually best choice:

# Python (Timsort)
sorted_list = sorted(items)
items.sort()  # In-place

# With key
sorted_users = sorted(users, key=lambda u: u["age"])

Common Algorithms

Algorithm

Time (avg)

Time (worst)

Space

Quicksort	O(n log n)	O(n²)	O(log n)
Mergesort	O(n log n)	O(n log n)	O(n)
Heapsort	O(n log n)	O(n log n)	O(1)

When to Think About Sorting

• Need ordered output
• Enables binary search
• Finding duplicates
• Grouping similar items

Common Patterns

Two Pointers

For sorted arrays or linked lists:

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1
    
    return None

Sliding Window

For contiguous subarrays:

def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Hash Map

For O(1) lookups:

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 None

Frequency Counting

def most_common(items):
    counts = {}
    for item in items:
        counts[item] = counts.get(item, 0) + 1
    
    return max(counts, key=counts.get)

Recursion

Functions that call themselves:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Key Elements

Base case: When to stop

Recursive case: Call with smaller input

Progress: Move toward base case

Tree Traversal

def traverse(node):
    if node is None:
        return
    
    # Pre-order: process before children
    print(node.value)
    
    traverse(node.left)
    traverse(node.right)
    
    # Post-order: process after children

Practical Algorithms

Removing Duplicates

# Using set
unique = list(set(items))

# Preserving order
seen = set()
unique = []
for item in items:
    if item not in seen:
        seen.add(item)
        unique.append(item)

Finding Intersection

set_a = set(list_a)
set_b = set(list_b)
intersection = set_a & set_b

Grouping

from collections import defaultdict

grouped = defaultdict(list)
for item in items:
    key = item["category"]
    grouped[key].append(item)

Top K Elements

import heapq

# Top k largest
top_k = heapq.nlargest(k, items)

# Top k by key
top_k = heapq.nlargest(k, items, key=lambda x: x["score"])

String Algorithms

Pattern Matching

# Built-in (sufficient for most cases)
"pattern" in text
text.find("pattern")
text.count("pattern")

Anagram Check

def is_anagram(s1, s2):
    return sorted(s1) == sorted(s2)

# Or with counting
from collections import Counter
def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

Palindrome Check

def is_palindrome(s):
    return s == s[::-1]

# Ignoring case and non-alphanumeric
def is_palindrome_clean(s):
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

When to Optimize

Don't Prematurely Optimize

Start with readable code. Optimize only if:

• Performance is actually a problem


• You've measured and identified bottleneck


• The optimization is worth the complexity

Quick Wins

• Use sets for membership testing
• Use dicts for lookups
• Use built-in functions (often faster)
• Avoid nested loops when possible

Big Gains

• Change algorithm (O(n²) → O(n log n))
• Use appropriate data structure
• Add caching/memoization

Conclusion

Core algorithmic concepts:

• Big O for understanding scale


• Searching: linear vs binary


• Sorting: use built-ins usually


• Patterns: two pointers, sliding window, hash maps


• Recursion for tree/hierarchical problems

Choose algorithms based on data size and access patterns.

---

Next: SQL Basics - Database querying fundamentals