Skip to content

Algorithms

Common algorithms implemented in pure Python.

Sorting

heap_sort(arr)

Perform an O(n log n) Heap Sort on a list. Returns a new sorted list.

Source code in pure_python_ds/algorithms/sorting.py 
77
78
79
80
81
82
83
84
def heap_sort(arr: List[T]) -> List[T]:
    """
    Perform an O(n log n) Heap Sort on a list.
    Returns a new sorted list.
    """
    heap = arr.copy()
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]

insertion_sort(arr)

Perform an O(n^2) Insertion Sort on a list. Efficient for small or nearly sorted arrays. Returns a new sorted list.

Source code in pure_python_ds/algorithms/sorting.py 
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def insertion_sort(arr: List[T]) -> List[T]:
    """
    Perform an O(n^2) Insertion Sort on a list.
    Efficient for small or nearly sorted arrays.
    Returns a new sorted list.
    """
    result = arr.copy()
    for i in range(1, len(result)):
        key = result[i]
        j = i - 1
        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    return result

merge_sort(arr)

Perform an O(n log n) Merge Sort on a list. Returns a new sorted list.

Source code in pure_python_ds/algorithms/sorting.py 
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(arr: List[T]) -> List[T]:
    """
    Perform an O(n log n) Merge Sort on a list.
    Returns a new sorted list.
    """
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # Recursive split
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return _merge(left, right)

quick_sort(arr)

Perform an O(n log n) expected Quick Sort on a list. Returns a new sorted list.

Source code in pure_python_ds/algorithms/sorting.py 
46
47
48
49
50
51
52
53
54
55
56
57
def quick_sort(arr: List[T]) -> List[T]:
    """
    Perform an O(n log n) expected Quick Sort on a list.
    Returns a new sorted list.
    """
    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)

radix_sort(arr)

Perform an O(nk) Radix Sort on a list of non-negative integers. Returns a new sorted list.

Source code in pure_python_ds/algorithms/sorting.py 
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
def radix_sort(arr: List[int]) -> List[int]:
    """
    Perform an O(nk) Radix Sort on a list of non-negative integers.
    Returns a new sorted list.
    """
    if not arr:
        return []

    max_val = max(arr)
    exp = 1
    result = arr.copy()

    while max_val // exp > 0:
        _counting_sort_by_digit(result, exp)
        exp *= 10

    return result

Searching

Performs an iterative binary search on a sorted list. Returns the index of the target if found, else -1.

Source code in pure_python_ds/algorithms/searching.py 
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binary_search(arr: List[Any], target: Any) -> int:
    """
    Performs an iterative binary search on a sorted list.
    Returns the index of the target if found, else -1.
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Performs an O(log i) exponential search on a sorted list. Returns the index of the target if found, else -1.

Source code in pure_python_ds/algorithms/searching.py 
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
def exponential_search(arr: List[Any], target: Any) -> int:
    """
    Performs an O(log i) exponential search on a sorted list.
    Returns the index of the target if found, else -1.
    """
    if not arr:
        return -1

    if arr[0] == target:
        return 0

    n = len(arr)
    i = 1
    while i < n and arr[i] <= target:
        i = i * 2

    # Perform binary search on the found range
    low = i // 2
    high = min(i, n - 1)

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Performs an O(sqrt(n)) jump search on a sorted list. Returns the index of the target if found, else -1.

Source code in pure_python_ds/algorithms/searching.py 
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def jump_search(arr: List[Any], target: Any) -> int:
    """
    Performs an O(sqrt(n)) jump search on a sorted list.
    Returns the index of the target if found, else -1.
    """
    n = len(arr)
    if n == 0:
        return -1

    step = int(math.sqrt(n))
    prev = 0

    while prev < n and arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

    while prev < min(step, n) and arr[prev] < target:
        prev += 1

    if prev < min(step, n) and arr[prev] == target:
        return prev

    return -1

Performs an O(n) linear search on a list. Returns the index of the target if found, else -1.

Source code in pure_python_ds/algorithms/searching.py 
27
28
29
30
31
32
33
34
35
def linear_search(arr: List[Any], target: Any) -> int:
    """
    Performs an O(n) linear search on a list.
    Returns the index of the target if found, else -1.
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Dynamic Programming

edit_distance(word1, word2)

Computes the Levenshtein minimum edit distance between two strings.

Source code in pure_python_ds/algorithms/dp.py 
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def edit_distance(word1: str, word2: str) -> int:
    """
    Computes the Levenshtein minimum edit distance between two strings.
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],  # delete
                    dp[i][j - 1],  # insert
                    dp[i - 1][j - 1],  # replace
                )

    return dp[m][n]

fibonacci(n, memo=None)

Computes the nth Fibonacci number using Top-Down DP (Memoization). O(n) time complexity vs O(2^n) recursive complexity.

Source code in pure_python_ds/algorithms/dp.py 
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def fibonacci(n: int, memo: Optional[Dict[int, int]] = None) -> int:
    """
    Computes the nth Fibonacci number using Top-Down DP (Memoization).
    O(n) time complexity vs O(2^n) recursive complexity.
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

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

knapsack(weights, values, capacity)

Solves the 0-1 Knapsack problem. Returns the maximum value that can be put in a knapsack of capacity W.

Source code in pure_python_ds/algorithms/dp.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def knapsack(weights: List[int], values: List[int], capacity: int) -> int:
    """
    Solves the 0-1 Knapsack problem.
    Returns the maximum value that can be put in a knapsack of capacity W.
    """
    n = len(values)
    dp = [[0 for _ in range(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_common_subsequence(text1, text2)

Finds the length of the longest common subsequence of two strings.

Source code in pure_python_ds/algorithms/dp.py 
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def longest_common_subsequence(text1: str, text2: str) -> int:
    """
    Finds the length of the longest common subsequence of two strings.
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

longest_increasing_subsequence(arr)

Finds the length of the longest increasing subsequence.

Source code in pure_python_ds/algorithms/dp.py 
57
58
59
60
61
62
63
64
65
66
67
68
69
70
def longest_increasing_subsequence(arr: List[int]) -> int:
    """
    Finds the length of the longest increasing subsequence.
    """
    if not arr:
        return 0

    dp = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(0, i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Strings

Knuth-Morris-Pratt (KMP) Algorithm. Returns all starting indices of the pattern in the text.

Source code in pure_python_ds/algorithms/strings.py 
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def kmp_search(text: str, pattern: str) -> List[int]:
    """
    Knuth-Morris-Pratt (KMP) Algorithm.
    Returns all starting indices of the pattern in the text.
    """
    if not pattern:
        return [0] * (len(text) + 1)

    n, m = len(text), len(pattern)
    lps = [0] * m
    j = 0
    _compute_lps(pattern, m, lps)

    indices = []
    i = 0
    while i < n:
        if pattern[j] == text[i]:
            j += 1
            i += 1

        if j == m:
            indices.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return indices

rabin_karp(text, pattern)

Rabin-Karp Algorithm for string matching. Returns all starting indices of the pattern in the text. Uses rolling hash to verify match candidates in expected O(N+M) time.

Source code in pure_python_ds/algorithms/strings.py 
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
def rabin_karp(text: str, pattern: str) -> List[int]:
    """
    Rabin-Karp Algorithm for string matching.
    Returns all starting indices of the pattern in the text.
    Uses rolling hash to verify match candidates in expected O(N+M) time.
    """
    if not pattern:
        return [0] * (len(text) + 1)

    n, m = len(text), len(pattern)
    if m > n:
        return []

    d = 256  # No. of characters in the input alphabet
    q = 101  # A prime number for modulo
    h = 1

    for i in range(m - 1):
        h = (h * d) % q

    p = 0
    t = 0

    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q

    indices = []

    for i in range(n - m + 1):
        if p == t:
            match = True
            for j in range(m):
                if text[i + j] != pattern[j]:
                    match = False
                    break
            if match:
                indices.append(i)

        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q

            if t < 0:
                t += q

    return indices