DEV Community: Matteo

Sorting Algorithms Part 3: Linear-Time Sorting, Counting, Radix, and Bucket

Matteo — Tue, 11 Nov 2025 01:48:34 +0000

1. Introduction. The hook of today

In Part 2 we reached n log n time with divide and conquer. Today we go even further. When the data satisfies certain numeric assumptions, we can sort in time that is linear in the number of elements. The key is to stop comparing pairs and instead use structure in the input space.

We will cover three classics:

Counting Sort, a frequency based method that places values directly.
Radix Sort, a digit by digit method that uses a stable inner routine.
Bucket Sort, a distribution method for real values that are spread roughly uniformly.

As always, you can experiment with every algorithm in the Sorting Algorithms Playground.

2. Why linear sorts are possible

Comparison sorts must make enough decisions to distinguish among n factorial permutations, which leads to a lower bound of n * log n comparisons.
Linear sorts avoid pairwise comparisons and instead map values to positions by arithmetic.
This works when keys fall in a limited integer range, or when numbers have a bounded number of digits, or when real values are distributed well across an interval.

3. Counting Sort

3.1 Properties

Time: O(n + k)
Space: O(n + k)
Stable: yes
In place: no

3.2 Intuition

We count how many times each value appears, then we transform counts into cumulative counts so that each value knows where its block ends in the output.
By scanning the input from right to left we place elements into their final positions and preserve the relative order of equals, which makes the algorithm stable.

3.3 Implementation

def counting_sort(arr):
    if not arr:
        return []

    min_val, max_val = min(arr), max(arr)
    k = max_val - min_val + 1
    count = [0] * k

    for num in arr:
        count[num-min_val] += 1

    for i in range(1, k):
        count[i] += count[i-1]

    output = [0] * len(arr)

    for i in range(len(arr)-1, -1, -1):
        count[arr[i]-min_val] -= 1
        output[count[arr[i]-min_val]] = arr[i]

    return output

3.4 Notes and trade offs

This version handles any contiguous integer range by shifting indices by the minimum value.
It is stable because we insert elements from right to left.

Space grows with the value range, so it is best when the range k is of the same order as n.

4. Radix Sort

4.1 Properties

Time: O(d × (n + b)), where d is the number of digits and b is the base
Space: O(n + b)
Stable: yes when the inner pass is stable
In place: no

4.2 Intuition

Sort by the least significant digit first, then by the next digit, and so on.
If each digit pass is stable, the ordering created by earlier passes is preserved.
For signed integers we split into negative and non negative groups, sort magnitudes, then merge with the negatives reversed.

4.3 Implementation

def radix_sort(nums, base=10):
    if len(nums) <= 1:
        return nums[:]

    non_neg = [x for x in nums if x >= 0]
    neg = [-x for x in nums if x < 0]

    def lsd(nums):
        if not nums:
            return nums

        max_v = max(nums)
        exp = 1
        out = [0] * len(nums)

        while max_v // exp > 0:
            count = [0] * base

            for num in nums:
                digit = (num // exp) % base
                count[digit] += 1

            for idx in range(1, base):
                count[idx] += count[idx-1]

            for i in range(len(nums)-1, -1, -1):
                digit = (nums[i] // exp) % base
                count[digit] -= 1
                out[count[digit]] = nums[i]

            exp *= base
            nums, out = out, nums

        return nums

    ordered_neg = lsd(neg)
    neg_again = [-x for x in reversed(ordered_neg)]

    ordered_non_neg = lsd(non_neg)

    return neg_again + ordered_non_neg

4.4 Notes and trade offs

The inner pass is a stable counting sort on a single digit.

Work is proportional to the number of digits times the array length, plus the base.
This is excellent when the number of digits is small, for example fixed width integers.

5. Bucket Sort

5.1 Properties

Time: O(n + k) on uniform data, worst case can degrade to quadratic when data clusters
Space: O(n + k)
Stable: yes when intra bucket sorts are stable
In place: no in the usual form

5.2 Intuition

Divide the numeric interval into k buckets.
Place each value into its bucket according to a mapping function.
Sort each bucket, often with insertion sort for small buckets, then concatenate the buckets in order.
When values are spread uniformly the buckets remain small and total work is linear.

5.3 Implementation

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return []

    buckets = [[] for _ in range(bucket_count)]

    for x in arr:
        # ensure the last value falls into the last bucket
        idx = min(bucket_count - 1, int(x * bucket_count))
        buckets[idx].append(x)

    for b in buckets:
        b.sort()

    out = []
    for b in buckets:
        out.extend(b)
    return out

5.4 Notes and trade offs

The mapping from value to bucket index is the heart of the method.
If the data range is not [0, 1), apply an affine transform or adapt the index function.
When distribution is even, each bucket holds about n over k items and the total work is near linear.
When many values fall into one bucket the method slows down to the cost of the bucket sort, which is often n squared for insertion sort.

6. Comparing the three

Counting Sort: O(n + k), integer keys from a bounded range, stable, extra memory proportional to the range.
Radix Sort: O(d × (n + b)), works by digits, relies on stability, ideal for fixed width integers.
Bucket Sort: O(n + k) on uniform data, depends on a good bucket mapping, natural for real values in a known interval.

7. Quick comprehension check

Questions

Why do linear sorts not violate the n log n lower bound for comparison sorts?
When would you choose Counting Sort over Radix Sort?
What is the role of stability in Radix Sort?

Answers

Because they do not perform pairwise comparisons to order elements, they use arithmetic indexing or digit passes instead.
When the integer range is small relative to n and you need a single stable pass without digit logic.
It preserves the order created by earlier digit passes so that after the final pass the global order is correct.

8. Final summary and review

Linear sorting works by replacing comparisons with direct placement.
Counting Sort uses cumulative counts to compute positions.
Radix Sort applies a stable pass per digit and supports negatives by splitting and recombining.
Bucket Sort distributes values into subranges and sorts locally.
Together with the quadratic and the n log n families, these complete the classic map of sorting techniques.

Sorting Algorithms Part 2: Divide and Conquer — Merge, Quick, and Heap Sort

Matteo — Tue, 11 Nov 2025 01:21:41 +0000

1. Introduction. The hook of today

In Part 1, we saw the world of O(n²) sorts: simple, intuitive, but inefficient for large data. Now we step into a higher league: algorithms that use divide and conquer to reach O(n log n) time.

Today we’ll explore:

Merge Sort: stable and elegant, built on recursive merging.
Quick Sort: practical and blazing fast on average.
Heap Sort: in-place and guaranteed O(n log n).

These three mark the foundation of modern sorting.
Like in the previous blog, you can experiment interactively with all sorting algorithms in the Sorting Algorithms Playground.

2. Divide and Conquer (from Latin, "Divide et Impera") at its core

The key idea behind all O(n log n) sorts is simple:

Divide the array into smaller parts.
Conquer by sorting each part recursively.
Combine the results efficiently.

Each split halves the array (log n divisions), and each merge or partition touches all elements (n work). Hence, n × log n.

3. Merge Sort

3.1 Idea

Merge Sort recursively splits an array into halves until single elements remain, then merges them in sorted order.

It’s:

Stable: equal elements preserve order.
Not in-place: needs extra memory for merging.
Deterministic: always O(n log n), best to worst.

3.2 Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

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

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:] or right[j:])
    return result

3.3 Step-by-step explanation

Split recursively until subarrays of size 1.
Merge pairs of sorted lists by comparing the smallest elements from each.
Repeat merging bottom-up until the whole array is sorted.

3.4 Complexity

3.5 Why it matters

Merge Sort’s structure inspires Timsort, Python’s default sort, which combines Merge and Insertion Sort for optimal performance on real-world data.

4. Quick Sort

4.1 Idea

Quick Sort partitions the array around a pivot, placing smaller elements on one side and larger on the other, then sorts both sides recursively.

It’s fast in practice, especially with good pivot selection, but unstable.

Performance depends on partitioning:

Balanced splits → O(n log n)
Worst case (already sorted) → O(n²)

4.2 The simple recursive version (Pythonic)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[-1]
    left = quick_sort([x for x in arr[:-1] if x <= pivot])
    right = quick_sort([x for x in arr[:-1] if x > pivot])

    return left + [pivot] + right

Readable and expressive, but not memory efficient, since it creates new lists each time.

4.3 In-place quicksort (Lomuto partition)

def partition_lomuto(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort_in_place_lomuto(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition_lomuto(arr, low, high)
        quick_sort_in_place_lomuto(arr, low, p - 1)
        quick_sort_in_place_lomuto(arr, p + 1, high)
    return arr

4.4 Step By Step

The Lomuto scheme always chooses the last element as the pivot. It scans the array once, keeping a boundary i for the last element smaller than the pivot.
Every time we find an element smaller than the pivot, it’s swapped forward. In the end, we place the pivot right after that boundary, which ensures that everything to its left is smaller and everything to its right is larger.
The method is elegant but can suffer if the pivot ends up at the extremes (like already sorted input), producing highly unbalanced partitions.

4.5 Hoare partition (fewer swaps)

def partition_hoare(arr, low, high):
    pivot = arr[(low + high) // 2]
    i, j = low - 1, high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_in_place_hoare(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition_hoare(arr, low, high)
        quick_sort_in_place_hoare(arr, low, p)
        quick_sort_in_place_hoare(arr, p + 1, high)
    return arr

4.6 Step By Step

Hoare’s scheme uses two pointers moving inward from both ends of the array. The pivot is typically the middle element, and the loop continues swapping out-of-place values until the pointers cross.
Unlike Lomuto, Hoare’s version does fewer swaps and keeps partitions tighter, but the pivot itself may remain in the middle rather than moving to its final position.

The two approaches illustrate how small structural differences affect both stability and efficiency.

4.7 Variants worth knowing

Randomized pivot: avoids worst-case scenarios by choosing a random pivot.
Median-of-three: pivot = median(first, middle, last).
Three-way partition: groups <, =, and > pivot values separately (useful for arrays with duplicates).

4.8 Complexity summary

4.9 Why it matters

Quick Sort is the default choice in practice (e.g., C’s qsort, Java’s Arrays.sort for primitives) thanks to its cache efficiency and low overhead.
With randomized pivots and tail recursion elimination, it becomes extremely robust.

5. Heap Sort

5.1 Idea

Heap Sort uses a binary heap to repeatedly extract the maximum element and place it at the end.

A heap is a specialized binary tree stored in an array, where each parent satisfies a specific order property with respect to its children:

In a max-heap, every parent is greater than or equal to its children.
In a min-heap, every parent is less than or equal to its children.

Because the tree is complete (all levels filled except possibly the last), a heap can be represented in-place: for a node at index i, its children live at 2*i+1 and 2*i+2.

The first for loop in heap_sort starts from n // 2 - 1, the index of the last non-leaf node. All nodes after that index are leaves and already satisfy the heap property. Starting from there and moving upward ensures every subtree is heapified before the parent is adjusted.

It’s fully in-place and guarantees O(n log n) performance.

5.2 Implementation

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        heapify(arr, end, 0)

    return arr

5.3 Step-by-step

The algorithm first builds a max-heap, guaranteeing that the largest element is at the root. It then repeatedly swaps that root with the last element, effectively placing it in its correct final position, and reduces the heap size by one. Each call to heapify restores the heap structure for the remaining elements. In the end, the array becomes sorted in ascending order.

5.4 Complexity

5.5 Trade-offs

Always O(n log n), but more comparisons than Quick Sort.
Useful when guaranteed upper bounds are needed (e.g., real-time systems).

6. Comparing all log-linear sorts

7. Quick comprehension check

Questions

Which of these algorithms is stable by default?
Which is the fastest on average in practice?
Which is guaranteed O(n log n) and in-place?

Answers

Merge Sort.
Quick Sort (randomized).
Heap Sort.

8. Final summary and review

Log-linear sorting algorithms are where theory meets practice.
Merge Sort: perfect stability and predictability, but extra memory.
Quick Sort: elegant recursion and outstanding average speed.
Heap Sort: reliable and space-efficient, ideal when guarantees matter.

Together, they form the foundation for hybrid sorts like Timsort (Merge + Insertion) and IntroSort (Quick + Heap).

9. Hook for tomorrow

Next, we’ll enter the realm of linear-time sorting, when comparisons aren’t needed at all.
We’ll explore Counting Sort, Radix Sort, and Bucket Sort, showing how data properties can unlock sub-logarithmic performance.

Searching Algorithms Part 2: Pattern Matching in Strings with Z, KMP, and Rabin-Karp

Matteo — Tue, 11 Nov 2025 00:38:14 +0000

1. Introduction. The hook of today

In part 1, array search taught us to keep cutting the space of possibilities.

String search asks a similar question. Where in this text does a pattern occur.
The naive approach tries every starting index and checks character by character. It works, but it repeats work that we could reuse.
Today we learn how to avoid that repetition with three classic tools: Z algorithm, KMP, and Rabin-Karp. By the end you will recognize which tool fits which shape of problem and you will know how to code each one quickly.

2. The naive idea

Given text s and pattern p, try every index i and compare s[i : i + len(p)] to p.

def find_all_naive(s: str, p: str):
    n, m = len(s), len(p)
    out = []
    for i in range(n - m + 1):
        # character by character to avoid creating a slice
        ok = True
        for j in range(m):
            if s[i + j] != p[j]:
                ok = False
                break
        if ok:
            out.append(i)
    return out

Complexity

Time: O(n m).
Space: O(1).

If you build the slice s[i : i + m] and compare whole strings, each slice copy costs O(m). That leads to O(n m) with larger constants. The rest of this post shows how to do better by reusing information across positions.

3. Z algorithm

3.1 Principle

The Z array for a string x records, for each position i, the length of the longest substring starting at i that matches the prefix of x.
If we compute Z on p#s where # is a separator that does not appear in either string, any Z value equal to len(p) marks a match of p inside s.

The algorithm maintains a window [L, R] called the Z box that represents the rightmost segment that matches a prefix. Inside the box we reuse previous values by mirroring positions. When we fall outside the box we match characters from scratch and extend the box.

3.2 Tradeoffs and assumptions

Pros
• Simple linear scan once you know the template
• Great for prefix based queries such as longest prefix that is also a suffix

Cons
• Slightly less familiar to many engineers than KMP
• Requires a safe separator when you concatenate pattern and text

Assumptions
• Input is indexable characters. For byte data the logic is identical.

Complexity

Time: O(n) for the combined string
Space: O(n) for the Z array.

3.3 Standard implementation

Building the Z array

def z_array(x: str):
    n = len(x)
    Z = [0] * n
    L = R = 0
    for i in range(1, n):
        if i <= R:
            Z[i] = min(R - i + 1, Z[i - L])
        while i + Z[i] < n and x[Z[i]] == x[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] - 1 > R:
            L, R = i, i + Z[i] - 1
    return Z

Pattern search with Z

def find_with_z(s: str, p: str):
    if not p:
        return list(range(len(s) + 1))
    combo = p + "#" + s
    Z = z_array(combo)
    m = len(p)
    hits = []
    for i in range(m + 1, len(combo)):
        if Z[i] == m:
            hits.append(i - m - 1)
    return hits

3.4 Example. Longest Happy Prefix

Goal. Find the longest prefix of s that is also a suffix and not equal to the whole string.

Why Z fits
Z stores lengths of segments that match the prefix. The answer equals the largest Z value that ends at the last index.

def longest_prefix(s: str) -> str:
    Z = z_array(s) # previously built function
    n = len(s)
    for i in range(1, n):
        if i + Z[i] == n:
            return s[:Z[i]]
    return ""

4. KMP

4.1 Principle

KMP uses a prefix function called LPS that records the length of the longest proper prefix that is also a suffix for each prefix of the pattern.

When a mismatch occurs after matching k characters, KMP uses the LPS of k to jump the pattern to the next viable alignment, without moving the text backward. The text pointer never retreats. That is the key efficiency.

4.2 Tradeoffs and assumptions

Pros
• Deterministic linear time for search
• No hashing and no collision concerns
• Works well when there are many partial matches

Cons
• The LPS table is conceptually tricky for beginners
• Slightly more code than Z if you only need prefix queries

Assumptions
• Same as Z. Operates on indexable characters

Complexity

Time: O(n + m).
Space: O(m) for the LPS table.

4.3 Standard implementation

Build LPS

def build_lps(p: str):
    m = len(p)
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and p[i] != p[k]:
            k = lps[k - 1]
        if p[i] == p[k]:
            k += 1
            lps[i] = k
    return lps

Pattern search with LPS

def kmp_search(s: str, p: str):
    if not p:
        return list(range(len(s) + 1))
    lps = build_lps(p)
    i = j = 0
    hits = []
    while i < len(s):
        if s[i] == p[j]:
            i += 1
            j += 1
            if j == len(p):
                hits.append(i - j)
                j = lps[j - 1]
        else:
            if j > 0:
                j = lps[j - 1]
            else:
                i += 1
    return hits

4.4 Example. Find the index of the first occurrence.

Use KMP to return the first match or minus one when absent.

def str_str(haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)

    if not m or n < m:
        return -1

    lps = build_lps(needle) # previously built function
    i = j = 0 # over haystack and needle

    while i < n:
        if haystack[i] == needle[j]:
            i += 1
            j +=1
            if j == m:
                return i - j
        else:
            if j > 0:
                j = lps[j-1]
            else:
                i += 1

    return -1

5. Rabin Karp with binary search on length

5.1 Principle

The Rabin–Karp algorithm transforms substrings into numeric hashes so they can be compared in constant time.
Instead of comparing every character of a pattern with every substring, we slide a rolling hash window over the text and only verify characters when the hash values match.

It is one of the earliest practical examples of using hashing for pattern matching.

5.2 Best Practices

Choose a good base.
A common choice is a prime number slightly larger than your alphabet size (for lowercase letters 26 → base ≈ 31, for ASCII 256).
Using a base that spreads digits well reduces collisions.

Choose a large prime modulus.
It keeps hash values small while minimizing collisions. Popular moduli are 10*9 + 7, 109 + 9, or 2*61 - 1 for 64-bit arithmetic.

Use modular arithmetic.
Hash updates must be done modulo mod to avoid overflow and to ensure a stable range.

Optional: double hashing.
Using two different moduli and storing hash pairs nearly eliminates collisions.

5.3 Tradeoffs and assumptions

Pros
• Very fast in practice for fixed length checks
• Simple to combine with binary search on the answer

Cons
• Hash collisions are possible
• Requires careful choice of base and modulus
• For full robustness many solutions use two moduli

Assumptions
• Treat the string as integer codes. For Unicode consider normalizing or limiting to bytes

5.4 Standard implementation

Below is the clean, general Rabin–Karp search function, exactly what you’d use to find all occurrences of a substring in a larger text.

def rabin_karp(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if not m or n < m:
        return []

    base = 256            # or 31 for lowercase letters
    mod = 10**9 + 7       # large prime modulus
    power = pow(base, m - 1, mod)

    # compute initial hashes
    hp = 0  # hash of pattern
    hs = 0  # rolling hash of current window
    for i in range(m):
        hp = (hp * base + ord(pattern[i])) % mod
        hs = (hs * base + ord(text[i])) % mod

    res = []

    for i in range(n - m + 1):
        # if hashes match, verify characters
        if hp == hs and text[i:i + m] == pattern:
            res.append(i)

        # roll the hash window
        if i < n - m:
            hs = (hs - ord(text[i]) * power) % mod
            hs = (hs * base + ord(text[i + m])) % mod
            hs = (hs + mod) % mod  # avoid negatives

    return res

5.4 How It Works

Compute the hash of the pattern and the first window of the text.
Slide the window one character at a time.
Update the hash in constant time:
remove the leftmost character and add the new rightmost character.
When hashes match, verify characters to avoid false positives.

Complexity
Each step is O(1), so the overall average complexity is O(n + m), though in the worst case (many hash collisions) it can degrade to O(n m).
With good parameters, this almost never happens.

5.5 Example: Repeated DNA Sequences

We can apply the same logic to find all 10-letter substrings that appear more than once.

def findRepeatedDnaSequences(self, s: str) -> List[str]:
    n = len(s)
    m = 10
    if n <= m:
        return []

    base = 131           # good spread for ASCII range
    mod = 10**9 + 7
    power = pow(base, m - 1, mod)

    hs = 0
    seen = {}
    res = set()

    # initial hash for first window
    for i in range(m):
        hs = (hs * base + ord(s[i])) % mod
    seen[hs] = 0

    # slide the window
    for i in range(n - m):
        hs = (hs - ord(s[i]) * power) % mod
        hs = (hs * base + ord(s[i + m])) % mod
        hs = (hs + mod) % mod

        if hs in seen:
            if s[seen[hs] : seen[hs] + m] == s[i + 1 : i + 1 + m]:
                res.add(s[i + 1 : i + 1 + m])
        seen[hs] = i + 1

    return list(res)

5.6 Advanced: Binary Search + Rabin–Karp

For problems like Longest Duplicate Substring or Longest Repeated Substring, we can combine Rabin–Karp with binary search on substring length:

Binary search determines the candidate length L.
Rabin–Karp checks whether any duplicate substring of length L exists.
If yes, try a longer length; otherwise, shorter.

This hybrid approach runs in O(n log n) and is one of the cleanest ways to solve those problems efficiently.

Complexity Summary

6. Quick comprehension check

Question
You have to find every position where pattern p occurs inside text s. Which method would you choose if you want deterministic linear time and you do not want to deal with hashing.

Answer
Use KMP. Build the LPS table for p and scan s once while reusing prefix information.

7. Final summary and review

All three methods avoid recomputing work that naive scanning repeats.

Z algorithm
Records how much the prefix matches from every position. Excellent for prefix queries and for fast detection of pattern matches by computing Z on pattern, separator, text.

KMP
Uses the prefix function to jump the pattern forward after mismatches. Deterministic linear time. A reliable default when hashing is not desirable.

Rabin Karp
Uses rolling hashes to compare substrings by numbers. Very natural to combine with binary search on length for longest duplicate or longest repeated tasks.

8. Hook for tomorrow

We searched inside arrays and inside strings. Next we switch to structures that are not linear. Trees and graphs. We will learn how BFS and DFS explore state spaces, how to encode visited sets, and how to graft searching on top of traversal to solve pathfinding and many classic interview problems.

Sorting Algorithms Part 1: The Quadratic Sorts — Bubble, Selection, and Insertion

Matteo — Tue, 11 Nov 2025 00:21:17 +0000

1. Introduction. The hook of today

If searching tells you where something is, sorting tells you how to arrange everything else around it.

Sorting is one of the oldest and most fundamental problems in computer science. Every database, browser, and spreadsheet performs sorting millions of times a day.

Today we start from the ground up, the intuitive quadratic sorting algorithms.

They are slow for large data but perfect for learning how comparisons and swaps interact, and for seeing how more advanced algorithms improve on them later.

Pro Tip: follow along and try it yourself! You can experiment with all sorting algorithms directly here:

👉 Open Sorting Algorithms Playground

2. The naive idea

The most direct way to sort is to repeatedly look for items that are out of order and swap them until everything is sorted.

This leads to the three fundamental O(n²) sorting algorithms:

Bubble Sort: repeatedly swap adjacent out-of-order elements.
Selection Sort: repeatedly find the smallest element and move it to its position.
Insertion Sort: grow a sorted prefix by inserting one element at a time.

All three rely on nested loops and simple comparison logic.

Let’s walk through each.

3. Bubble Sort

3.1 Idea

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

After each pass, the largest unsorted element “bubbles up” to its correct position at the end of the list.

3.2 Implementation

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:
            break
    return arr

3.3 Step-by-step

Inner loop compares adjacent pairs and swaps if necessary.
After the first pass, the largest element is at the end.
Each subsequent pass ignores the sorted tail (n - i - 1).
If no swaps happen in a full pass, the list is already sorted.

3.4 Complexity

3.5 Why keep it around

Great for teaching because the swap logic is visible.
Easy to implement for very small lists.
Provides a foundation for optimized hybrid sorts.

4. Selection Sort

4.1 Idea

Selection sort divides the list into a sorted and unsorted section. At each step it selects the smallest remaining element and places it at the beginning of the unsorted section.

4.2 Implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

4.3 Step-by-step

Find the smallest element in the unsorted region [i, n).
Swap it with the element at index i.
Increment i and repeat until the end.

4.4 Complexity

4.5 Why it matters

Simple, predictable number of comparisons (always n(n−1)/2).
Not stable because equal elements can be swapped out of order.
Rarely used in practice, but conceptually introduces the idea of finding minima efficiently.

5. Insertion Sort

5.1 Idea

Insertion sort builds the sorted array one element at a time.
For each new element, it shifts larger elements one position to the right until the correct place is found, then inserts it.

This is how most people sort playing cards in their hand.

5.2 Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

5.3 Step-by-step

Start with the second element as the first “unsorted” value.
Compare it with previous elements, shifting larger ones right.
Insert it where it belongs.
Repeat until the list is sorted.

5.4 Complexity

5.5 Why it’s special

Adaptive: faster on nearly sorted data.
Stable: equal elements preserve their relative order.
Used inside advanced algorithms like Timsort and IntroSort for small partitions.

6. Comparing all three

Pro Tip: If you want to watch these algorithms in motion, the free tool Visualgo is perfect.
You can choose Bubble, Selection, or Insertion Sort, adjust the array size and animation speed, and observe how swaps and comparisons happen step by step.
Visualgo lets you slow down or speed up the animation, highlight comparisons, and even switch to other algorithms like Merge or Quick Sort when you move on to Part 2.

7. Quick comprehension check

Which of the three sorts is stable and adaptive?
→ Insertion sort.
Why does bubble sort’s early-exit optimization improve the best case?
→ Because it stops after one pass when no swaps occur, giving O(n).
Why is selection sort not stable?
→ Because it can swap equal elements from different positions, reversing their order.

8. Final summary and review

Bubble, Selection, and Insertion Sort share the same big-O performance, but they teach different lessons about algorithmic design.

Bubble Sort shows how repeated local swaps lead to global order.
Selection Sort teaches how to find minima systematically.
Insertion Sort demonstrates adaptivity and the value of shifting instead of swapping.

They all run in O(n²) time but form the mental foundation for divide-and-conquer sorts like Merge Sort and Quick Sort, where comparisons and movement are organized more efficiently.

9. Hook for tomorrow

Next time we leave the quadratic world behind. We will learn how divide and conquer reduces comparisons from n² to n log n.

You will see how Merge Sort builds order from merging halves, and how Quick Sort partitions the array around pivots to achieve the same speed in place.

Searching Algorithms Part 3: Exploring Trees and Graphs with BFS and DFS

Matteo — Mon, 10 Nov 2025 23:02:39 +0000

1. Introduction. The hook of today

In arrays (part 1) and strings (part 2) we searched through ordered sequences. Now we step into structures that have connections: trees and graphs.

These structures describe maps, networks, social links, game states, file systems, and almost anything with relationships.

When we say “search” in this context, we no longer move left or right; we move outward or deeper along edges. Two classical strategies dominate this world: Breadth-First Search (BFS) and Depth-First Search (DFS). Both visit every reachable node, but they explore in completely different orders.

2. The building blocks: stacks and queues

Before we write any BFS or DFS code, we need to understand how the order of exploration depends on two simple data structures.

2.1 Stacks

A stack follows Last In, First Out (LIFO) order.

Think of a pile of books: you always remove the top one first.

Operation	Description	Time
`push(x)`	add an element on top	O(1)
`pop()`	remove the top element	O(1)
`peek()`	look at the top element	O(1)

In Python, a list already works as a stack:

stack = []
stack.append(1)   # push
top = stack.pop() # pop

2.2 Queues

A queue follows First In, First Out (FIFO) order.
Imagine people in a line: the first to enter is the first to leave.

Operation	Description	Time
enqueue(x)	add to back	O(1)
dequeue()	remove from front	O(1)

In Python, use collections.deque for efficient O(1) pops from both ends:

from collections import deque

queue = deque()
queue.append(1)       # enqueue
front = queue.popleft()  # dequeue

2.3 Why they matter

DFS uses a stack (explicitly or implicitly through recursion).
BFS uses a queue.
These two small choices completely change the order in which nodes are visited.

3. Breadth-First Search (BFS)

3.1 Idea

BFS explores level by level.
Starting from a node, it visits all immediate neighbors, then their neighbors, and so on.
It is the natural algorithm for finding shortest paths in unweighted graphs.

3.2 Implementation

from collections import deque

def bfs(graph, start):
    if start not in graph:
        return []
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                queue.append(nei)

    return order

3.3 Explanation step by step

Begin with a queue containing only the start node.
Repeatedly remove the front element.
For each neighbor that hasn’t been visited, mark it and enqueue it.
Continue until the queue is empty.

3.4 Complexity

Time O(V + E) — each vertex and edge visited once
Space O(V) for the queue and visited set

3.5 Applications

Shortest path in unweighted graphs
Level order traversal of trees
Finding connected components
Topological sorting (with in-degree counts)
Word ladder / transformation sequences

3.6 Example. Shortest path in an unweighted graph

def shortest_path(graph, start, goal):
    from collections import deque
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                queue.append((nei, path + [nei]))
    return None

What just happened

We kept a queue of pairs, each pair holds the current node and the path taken to reach it.
We popped from the front, which guarantees that we expand nodes in order of increasing distance from the start.
The first time we see the goal, the path we carry is the shortest possible in an unweighted graph.
We marked nodes as visited when we enqueued them so that each node enters the queue at most once.

Invariant

Every node in the queue has a path whose length equals its distance from the start.
No shorter path to any queued node exists, since any shorter path would have been discovered and enqueued earlier.

Why BFS yields the shortest path

The queue explores level by level.
All paths of length L are generated and tested before any path of length L plus 1.
The first time the goal appears, it must be via a shortest path.

Complexity

Time is O(V + E), each vertex and edge is processed at most once.
Space is O(V) for the queue and the visited set.

Common pitfalls

Forgetting to mark neighbors when enqueuing lets the same node enter the queue many times.
Building new lists with path plus neighbor for very large graphs can be memory heavy. If that matters, keep a parent map and reconstruct the path only once at the end.

4. Depth-First Search (DFS)

4.1 Idea

DFS explores as far as possible before backtracking.
It dives deep along one branch until it cannot go further, then backtracks to explore remaining branches.
Where BFS is like ripples spreading on water, DFS is like digging a single tunnel until it ends.

4.2 Recursive version (cleanest)

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for nei in graph[node]:
        if nei not in visited:
            dfs_recursive(graph, nei, visited, order)
    return order

Recursion uses the call stack as the implicit stack.

4.3 Iterative version (explicit stack)

def dfs_iterative(graph, start):
    if start not in graph:
        return []
    stack = [start]
    visited = set()
    order = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nei in reversed(list(graph.get(node, []))):
            if nei not in visited:
                stack.append(nei)
    return order

4.4 Complexity

Time O(V + E)
Space O(V) (recursion stack or explicit stack)

4.5 Applications

Detecting cycles
Topological sorting (directed acyclic graphs)
Generating mazes and puzzles
Solving backtracking problems (permutations, Sudoku, N-Queens)
Connected components in undirected graphs
Tree traversals (preorder, inorder, postorder)

4.6 Example. Detecting a cycle in a directed graph

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in graph}

    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    return False

What just happened

We colored nodes to track the recursion state. White means unvisited, gray means currently in the recursion stack, black means fully explored.
When DFS sees an edge from the current node to a gray node, that edge goes back into the active recursion path, which proves a directed cycle.
On return, the node becomes black so that future traversals do not revisit it.

Invariant

All gray nodes form the current recursion stack, which is exactly the path from the DFS root to the current node.
No black node has any white descendants left to discover.

Why this detects cycles

A back edge to any gray node connects the current node to an ancestor in the recursion stack.
In directed graphs that is the definition of a cycle.

Complexity

Time is O(V + E), each vertex and edge is examined at most once.
Space is O(V) for the color map and the recursion stack.

Common pitfalls

Not adding missing vertices from adjacency lists into the color map can cause a KeyError. Ensure every referenced neighbor exists in the color map, even if it has an empty adjacency list.
Using recursion on very deep graphs can hit the recursion limit in Python. Switch to an explicit stack if depth may be large.

5. BFS vs DFS at a glance

6. Iterative vs recursive DFS

Recursion is concise and readable, but may hit Python’s recursion limit on very deep graphs.
The iterative version avoids that by managing the stack manually.
They have identical complexity; only the memory layout differs.

When to choose which:

Use recursion for trees or small graphs.
Use an explicit stack for large or potentially cyclic graphs.

7. When and why to combine them

Sometimes the best strategy is a hybrid:

Run BFS first to find shortest paths or levels.
Use DFS later to reconstruct or explore within a specific layer.
Combine DFS with backtracking to enumerate all possible paths, but prune branches early using BFS distances.

8. Quick comprehension check

Questions

Why does BFS guarantee the shortest path in unweighted graphs?
What happens if we replace the queue in BFS with a stack?
In DFS, when is recursion less safe than an explicit stack?

Answers

Because it visits nodes in increasing distance order from the start node.
It becomes DFS.
On deep or cyclic graphs that can exceed recursion depth.

9. Final summary and review

Both BFS and DFS are fundamental graph traversal patterns.
They share the same O(V + E) complexity but explore in opposite directions:

BFS spreads outward using a queue. It is best when distance matters.
DFS dives inward using a stack. It is best when exploring all configurations or detecting cycles.

Stacks and queues are their silent engines.
Understand how those two structures control the order of exploration, and you understand how every graph search works, from maze solvers to web crawlers to AI pathfinding.

10. Hook for tomorrow

With traversal mastered, we can now build on top of it.
Next we will look at graph algorithms that use BFS and DFS as building blocks: shortest-path algorithms such as Dijkstra’s and Bellman-Ford, and graph properties like connected components, topological ordering, and strongly connected components.

These complete the classic toolkit of graph searching.

Searching Algorithms Part 1: Binary Search and the Art of Cutting the Search Space

Matteo — Mon, 10 Nov 2025 20:41:23 +0000

1. Introduction: The Hook of Today

If the two-pointer technique taught us how to traverse data efficiently, searching algorithms teach us how to find efficiently.

When you need to locate something in a sorted structure, your first instinct might be to scan linearly. But that wastes information. If the data is sorted, we can always ask smarter questions than “is it here?”.

Think of it as playing a guessing game with someone who says higher or lower. Instead of checking every number one by one, you can halve the range of possibilities each time. That is the power of binary search.

Today we begin our three-part exploration of searching algorithms. We start from the simplest form of reasoning on ordered data, build up to flexible patterns like search on answer, and finish with mountain arrays and bitonic sequences.

2. The Naive Idea

Before diving into binary search, it helps to remember what the linear approach does.

A linear search scans each element until it finds the target or reaches the end.

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

It is simple, clear, and terrible for large inputs.

Complexity
Time: O(N)
Space: O(1)

This brute-force approach ignores a crucial fact: in sorted data, every comparison tells you whether you can discard half of the array. That means you can cut your work in half each time instead of checking everything.

3. Core Concept: Binary Search

Binary search relies on the idea of halving the search interval until the target is found. It is one of the most fundamental algorithmic patterns in computer science.

Example: Classic Binary Search

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

How It Works

Choose the middle element.
Compare it to the target.
Depending on the result, discard half of the array.
Repeat until the interval becomes empty.

Complexity
Time: O(log N)
Space: O(1)

Binary search is not limited to finding a specific value. Once you understand how to manipulate the condition, you can adapt it to a wide range of optimization and boundary problems.

4. Beyond Finding a Value: Searching on a Condition

Many problems ask for the smallest or largest value that satisfies a condition rather than an exact match. This is called searching on the answer.

The idea is to perform binary search over the solution space rather than over the array itself.

Example: Minimum Capacity to Ship Packages Within D Days

def ship_within_days(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if can_ship(weights, days, mid):
            right = mid
        else:
            left = mid + 1
    return left

def can_ship(weights, days, capacity):
    days_needed = 1
    current = 0
    for w in weights:
        if current + w > capacity:
            days_needed += 1
            current = 0
        current += w
    return days_needed <= days

How It Works
We are not searching for a number inside an array. We are searching for the minimum feasible capacity that meets a condition.

The smallest possible capacity (left) must be at least the heaviest package, because we cannot split a single item.
The largest possible capacity (right) is the sum of all packages, meaning we could ship everything in one day.
We test a middle value (mid) as a candidate capacity.
The helper function can_ship simulates the loading process:
- It fills the current ship until adding another package would exceed the capacity.
- When that happens, it increments days_needed and resets the load counter.
- In the end, it checks whether the number of days used is less than or equal to the limit.

If we can successfully ship within the allowed number of days, the capacity might be reduced further, so we move right down. Otherwise, we increase left to test larger capacities.

Complexity
Time: O(N log S), where S is the numeric search range.
Space: O(1)

5. Lower Bound and Upper Bound

Binary search can also locate positions relative to a target even if the target itself does not exist.
These are known as lower bound and upper bound searches.

Lower bound: first index where the element is greater than or equal to the target.
Upper bound: first index where the element is strictly greater than the target.

def lower_bound(arr, target):
    low, high = 0, len(arr)

    while low < high:
        mid = (low+high) // 2

        if arr[mid] < target:
            low = mid+1
        else:
            high = mid

    return low

def upper_bound(arr, target):
    low, high = 0, len(arr)

    while low < high:
        mid = (low+high) // 2

        if arr[mid] <= target:
            low = mid+1
        else:
            high = mid

    return low

Why It Matters
These patterns appear everywhere:

Finding insertion positions
Counting elements less than a value
Solving “k-th smallest” problems
Handling duplicates in sorted arrays

6. Bitonic and Rotated Arrays

Some problems involve arrays that are almost sorted, such as rotated or bitonic arrays. Binary search still works but requires conditional logic.

Example 1: Search in Rotated Sorted Array

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

Key Idea

At every step, at least one side of the array is sorted.
We first check which side is sorted by comparing nums[left] and nums[mid].
If the target lies within that sorted range, we restrict our search to that side by moving the appropriate pointer. Otherwise, we move to the other side.

This approach keeps halving the search space even when the array has been rotated.

Example 2: Find the Peak in a Bitonic Array

A bitonic array increases and then decreases. The peak can be found by comparing neighbors.

def find_peak(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid
    return left

Key Idea
We compare the middle element to its next neighbor:

If nums[mid] is smaller than nums[mid + 1], we are on the increasing slope, so the peak lies to the right.
If nums[mid] is greater than or equal to nums[mid + 1], we are on the decreasing slope, so the peak lies to the left or at mid.

This continues until left and right meet at the highest point.

Complexity
Time: O(log N)
Space: O(1)

7. Quick Comprehension Check

Question
You are given an ascending array of positive integers and a value x. How would you find the smallest number in the array that is greater than or equal to x?

Answer
Use a lower-bound binary search to find the first index where nums[mid] >= x.

8. Final Summary and Review

Binary search is not only about finding numbers. It is about thinking in terms of ranges and conditions. Once you understand that every comparison halves your possibilities, you can apply the same logic to scheduling, geometry, optimization, and even model tuning.

9. Hook for Tomorrow

Today we saw how binary search and its variations help us explore numeric and ordered data.

Next, we move to searching in strings. You will learn how algorithms such as Z, KMP, and Rabin–Karp detect patterns efficiently, and how they can combine with binary search to find repeated substrings or the longest common prefix.

In Part 2, we will uncover how strings can be searched not by brute force, but through clever preprocessing and pattern recognition.

The Two-Pointer Technique: From Naive Loops to Elegant O(N) Solutions

Matteo — Mon, 10 Nov 2025 20:18:44 +0000

1. The Hook: Two Friends on a Number Line

Imagine two friends walking along a line of numbers. Sometimes they walk together toward the same direction, sometimes they start at opposite ends and meet in the middle, and other times one runs faster than the other to check what’s ahead.

That’s the essence of the two-pointer technique, one of the simplest yet most powerful tools in algorithm design.
When we face problems involving pairs, ranges, or sequences (like substrings or subarrays), our first instinct is often brute force: two nested loops scanning every possible combination. It works, but it’s slow. The two-pointer approach is a smarter way to explore the same search space without redundancy, often turning an O(N²) problem into O(N).

Today’s post will guide you through the concept, show real-world algorithmic applications, and end with a quick review that helps you recognize when and how to use each variant.

2. The Naive Approach: Nested Loops Everywhere

Let’s start with the naive way we typically approach “pair” or “window” problems.
Take a simple example: finding the longest substring without repeating characters in a given string.

The straightforward way is to try all possible substrings and check each one for duplicates.

def longest_unique_substring(s):
    n = len(s)
    best = 0
    for i in range(n):
        seen = set()
        for j in range(i, n):
            ch = s[j]
            if ch in seen:
                break
            seen.add(ch)
            best = max(best, j - i + 1)
    return best

This double loop checks every substring and re-examines most of the same characters multiple times.

The time complexity? O(N²). The space complexity? O(min(n, charset size)).
It works, but it’s inefficient for large inputs.

3. The Core Idea: What Are Two Pointers?

The two-pointer technique uses two indices (left and right, or i and j) to traverse a sequence in a coordinated way.
The idea is to maintain a relationship between them (a window or pair) and move one or both intelligently based on conditions.

There are three main ways we can use this pattern:

Think of it as teaching your loops to communicate.
Instead of two independent loops, you now have two synchronized variables that work together to minimize redundant work.

4. Same Direction: The Sliding Window Pattern

Let’s revisit our substring example, but this time we’ll use a sliding window, one of the most versatile two-pointer strategies.

Problem
Find the length of the longest substring without repeating characters.

Idea

We’ll use two pointers left and right to represent the current window of unique characters.
We expand right to include new characters and shrink left whe never we find a duplicate.

Implementation

def lengthOfLongestSubstring(s):
    if not s:
        return 0

    last = {}          # char -> last index
    left = 0
    best = 0

    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        if right - left + 1 > best:
            best = right - left + 1

    return best

How It Works

right moves forward exploring new characters.
On a duplicate that lies inside the current window, jump left to last[ch] + 1 instead of sliding one by one.
Update last[ch] = right, then recompute the window width.
Each index is processed once and left only moves forward

Complexity
Time: O(N)
Space: O(min(N, charset size))

Key Insight
The sliding window turns what used to be two nested loops into a single, where each index is processed once, and left only moves forward in jumps.

5. Opposite Directions: The Converging Pointer Pattern

Sometimes, the input array is sorted or can be treated as ordered. In those cases, we can exploit symmetry by starting from both ends and moving inward.

Problem
Find the container that holds the most water between vertical lines.
Given an array height[i] representing vertical lines, the area between two lines i and j is min(height[i], height[j]) * (j - i).

Naive Approach
Check every pair (i, j), that’s O(N²) again.

Optimized Two-Pointer Approach

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0

    while left < right:
        area = (right - left) * min(height[left], height[right])
        best = max(best, area)

        # Move the smaller line inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

Why It Works

The area is limited by the shorter line.
Moving the taller one won’t help because the width shrinks but the limiting height stays the same.
By always moving the shorter pointer, we maximize the chance of finding a better area.

Complexity
Time: O(N)
Space: O(1)

6. Different Speeds: The Fast–Slow Pointer Pattern

Sometimes both pointers start at the same point but move at different speeds.
This approach is particularly powerful for linked list problems or anything involving cycles or midpoints.

Problem
Detect if a linked list contains a cycle.

Algorithm (Floyd’s Cycle Detection)

def hasCycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Intuition

The fast pointer moves two steps at a time, while slow moves one.
If there’s no cycle, fast will hit the end.
If there is a cycle, fast will eventually “lap” slow and they’ll meet.

Complexity
Time: O(N)
Space: O(1)

7. Quick Comprehension Check

Question:
You’re given a sorted array nums and a target t. How can you check if any two numbers sum up to t in O(N)? Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

Hint:
Start one pointer at the beginning and one at the end. Move inward based on whether the sum is too large or too small.

Answer:

def twoSumSorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1
    return False

8. Beyond the Basics: Variants and Edge Cases

Choosing the Right Strategy

When dealing with substrings or subarrays, use sliding windows.
When working with sorted data, use converging pointers.
When traversing linked lists or cycles, use fast–slow pointers.
When symmetry matters (like palindromes), use center expansion.

9. Final Review

The two-pointer technique is the Swiss Army knife of algorithmic problem-solving.
It simplifies a vast class of problems by controlling how two indices move through data.

In summary:

What makes this pattern elegant is that the logic stays simple, you move pointers intelligently based on the problem’s constraints, ensuring each element is visited only as often as necessary.

10. The Hook for Tomorrow

We’ve mastered how two pointers traverse data efficiently.
Next, we’ll explore how algorithms search — not by brute force, but by systematically narrowing the space of possibilities.

In the next chapter, we’ll begin a three-part deep dive into searching algorithms:

Searching in arrays and numbers: from binary search and search on answer patterns to bitonic arrays and other specialized strategies.
Searching in strings: exploring Z-algorithm, KMP, Rabin–Karp, and hybrid methods that combine pattern matching with binary search.
Searching in trees and graphs: covering BFS, DFS, and how these foundational traversals become the backbone of pathfinding and state-space exploration.

By the end of this trilogy, you’ll see how every kind of search (numeric, textual, or structural) is just a different way of asking the same question: where do I look next?

React Query, Part 1 — The Mental Model (with running JS examples)

Matteo — Mon, 20 Oct 2025 21:13:38 +0000

Series plan:

Fundamentals you'll actually use (this post)
Mutations, optimistic UIs & cache mastery
Architecture, error UX, testing & performance

React Query (TanStack Query) treats the server as the source of truth and gives you a cache with a clock. If you grok these five ideas…

query keys (what data is this?)
staleTime (how long before it's "old"?)
enabled (should we fetch now?)
keepPreviousData (don't flicker between pages)
select (reshape on read, not after)

…then the API becomes muscle memory.

What this guide assumes

100% JavaScript (no TypeScript)
One fetch wrapper that throws a typed HttpError
Cookies via credentials: 'include'
A dependent query chain: /me → /me/summary
A keyset-paginated feed that uses keepPreviousData
Notes on v5 changes (e.g., side effects belong in components—not onSuccess)

This post explains those ideas with realistic snippets modeled after Inkline (React + fetch wrapper, session-style auth).
There's a tiny mock API so everything runs without a backend. This demo comes with barebone CSS, feel free to tinker with it if you'd like a better-looking result!

Why React Query?

Most of what clutters our components isn't rendering, it's data orchestration:

Are we loading? Did this error? Should I refetch?
If I visit this route again, can I reuse the data?
If another tab already fetched the same thing, can we dedupe?
When I change a note, which lists should auto-update?
How long is this data fresh before I nag the server again?

React Query (TanStack Query) treats anything from your API as server state, not UI state, and gives that state a cache with a clock plus battle-tested behaviors (deduping, retries, background refetch, GC), so you can focus on rendering.

What "server state" means (and why it's tricky)

UI state (which modal is open, form inputs) lives in your app and changes synchronously.
Server state lives elsewhere, is shared across screens, can be stale, and changes outside your control. That's why rolling your own useEffect + fetch + useState often becomes a web of flags.

You get, for free:

Cache + staleness: staleTime, cacheTime (GC), background refetch
Deduping & cancellation: concurrent requests for the same key collapse into one
Retries with exponential backoff (configurable)
Dependent queries (enabled) and derived data (select)
Pagination without flicker (keepPreviousData) or full-blown infinite queries
DevTools to see cache, observers, states in real time
Transport-agnostic: fetch, Axios, GraphQL—doesn't care

When not to use it

Purely local UI state (toggled sections, uncontrolled inputs) → stick to React state or a tiny store.
Data that must be kept in sync across users in real time (WebSocket/AppSync/etc.): you can still use React Query for initial load + retries + caching, but push updates via your real-time channel.

The mental model we'll use in this series

Query keys are addresses in the cache (['feed', { before: 'cursor' }]).
Data has a clock: fresh → stale → garbage-collected.
Mutations change the server; you invalidate what became stale.
Side effects (toasts, navigation) belong in your component, not in onSuccess handlers (v5 best practice).

If you only internalize staleTime, query keys, enabled, keepPreviousData, and select, the rest of the API becomes muscle memory.

Project setup

Prereqs: Node 18+ (or 20+), npm or pnpm. The demo is 100% JS (no TS).

Expected directory layout

rq-inkline-examples-js-part-1/
├─ public/
│  └─ mockServiceWorker.js      # generated by `npx msw init public --save`
├─ src/
│  ├─ api/
│  │  ├─ client.js              # fetch wrapper (throws HttpError, credentials: 'include')
│  │  └─ keys.js                # central query keys (me, summary, feed, note…)
│  ├─ features/
│  │  ├─ feed/
│  │  │  └─ Feed.jsx            # keyset pagination example (useQuery + keepPreviousData, then useInfiniteQuery)
│  │  └─ me/
│  │     └─ Summary.jsx         # dependent query example (/me → /me/summary)
│  ├─ mocks/
│  │  ├─ browser.js             # MSW boot (worker.start)
│  │  └─ handlers.js            # mock handlers for /me, /me/summary, /feed/public
│  ├─ App.jsx                   # mounts <Summary/> and <Feed/>
│  ├─ index.css                 
│  └─ main.jsx                  # QueryClientProvider, Devtools, and MSW startup (dev only)
├─ index.html
├─ package.json
└─ vite.config.js

Why this shape?

src/api/ keeps network concerns in one place: a small client and stable query keys.
src/features/* mirrors “screens/feature areas,” so examples read like real code.
src/mocks/ isolates MSW boot + handlers; public/mockServiceWorker.js is auto-generated.
main.jsx is the only place that knows about QueryClient and starts MSW in dev.
App.jsx is intentionally tiny, just composes the two demos so the focus stays on React Query.

# 1) Create app
npm create vite@latest react-query-fundamentals -- --template react
cd react-query-fundamentals

# 2) Install runtime deps
npm i @tanstack/react-query @tanstack/react-query-devtools msw

# 3) Generate the service worker for MSW (mocks)
npx msw init public/ --save

We use MSW to mock endpoints (/me, /me/summary, /feed/public) so the demo is runnable without a server (check out /public/mockServiceWorker.js).

Our fetch wrapper (Inkline-style)

One place that sets headers, includes credentials, and throws errors.
Components handle { data, isLoading, error } — no res.ok branches.

// src/api/client.js
const API = import.meta.env.VITE_API_URL || '';

export class HttpError extends Error {
  constructor(message, status, details) {
    super(message);
    this.status = status;
    this.details = details;
  }
}

export async function request(path, opts = {}) {
  const res = await fetch((API + path), {
    credentials: 'include', // important for cookie sessions
    headers: { 'Content-Type': 'application/json', ...(opts.headers || {}) },
    ...opts,
  });

  if (!res.ok) {
    let payload = null;
    try { payload = await res.json(); } catch {}
    const msg = payload?.error || res.statusText || 'Request failed';
    throw new HttpError(msg, res.status, payload);
  }
  return res.status === 204 ? null : res.json();
}

Bootstrapping QueryClient

At the very top of the app we create a single QueryClient and pass it to QueryClientProvider. Think of QueryClient as React Query's brain: it holds the cache, timers, and global defaults. Putting the provider at the root lets every component use hooks like useQuery without extra wiring.

A quick tour of the important lines:

MSW setup (dev-only):
1. We start the mock service worker only in development. The BASE_URL trick ensures the service worker is registered under the right path even if your app is hosted at a sub-path.
2. serviceWorker: { url: swUrl.pathname } keeps the SW same-origin.
3. onUnhandledRequest: 'bypass' means if a request has no mock handler, MSW lets it go to the network (useful when you only mock some endpoints).
QueryClient defaults (the "house rules" for all queries): staleTime, gcTime, refetchOnWindowFocus, retry
Devtools: <ReactQueryDevtools /> is a huge time saver. You can see cache entries, status, and force-refetch. It only adds a tiny overlay in development.

// src/main.jsx
import React from 'react'
import ReactDOM from 'react-dom/client'
import App from './App.jsx'

import { QueryClient, QueryClientProvider } from '@tanstack/react-query'
import { ReactQueryDevtools } from '@tanstack/react-query-devtools'

// MSW mock API (so you can run without a backend)
if (import.meta.env.DEV) {
  // Construct the correct path whether base is "/" or "/subpath/"
  const swUrl = new URL(
    `${import.meta.env.BASE_URL}mockServiceWorker.js`,
    window.location.origin
  )

  const { worker } = await import('./mocks/browser')
  await worker.start({
    serviceWorker: { url: swUrl.pathname }, // pathname keeps it same-origin
    onUnhandledRequest: 'bypass',
  })
}

const queryClient = new QueryClient({
  defaultOptions: {
    queries: {
      staleTime: 30_000,     // fresh for 30s
      gcTime: 5 * 60_000,    // garbage collect after 5m of inactivity
      refetchOnWindowFocus: true,
      retry: (count, err) => {
        const status = err?.status ?? 0
        if (status === 401 || status === 403) return false // auth endpoints shouldn't retry
        return count < 2
      },
    },
  },
})

ReactDOM.createRoot(document.getElementById('root')).render(
  <React.StrictMode>
    <QueryClientProvider client={queryClient}>
      <App />
      <ReactQueryDevtools buttonPosition="bottom-right" />
    </QueryClientProvider>
  </React.StrictMode>,
)

Reading React Query Devtools like a pro

Add Devtools once at the root of your project like we did in the main.jsx. Then head to the browser, toggle the devtools, and open the panel (bottom-right button with Tanstack logo) and you’ll see something like this:

What you’re looking at:

Badges across the top – quick counters by state: Fresh, Fetching, Paused, Stale, Inactive.
Each row = one query – the left column shows the query key (e.g. ["me"], ["me","summary"], ["feed",{ "before": null }]).
Status dot – green (fresh), yellow (stale), purple (fetching), gray (inactive).
Actions on each row:
- Remove (clear from cache)
- Refetch (run the queryFn now)
- Focus (simulate window refocus to trigger refetch if refetchOnWindowFocus is enabled)
- Online/Offline (simulate network status)
- Details (inspect observers, last updated, data preview)

How to verify the concepts from this guide

1) staleTime is actually working

Click your ["me"] query; note “Last updated”.
Watch the top badges: it should live under Fresh until your staleTime elapses, then move to Stale.
Hit Focus (or switch tabs and come back). If refetchOnWindowFocus is true and the query is stale, you’ll see a refetch.

2) Dependent queries via enabled

When logged out (or your mock returns 401), you should not see ["me","summary"].
After ["me"] resolves to a user, ["me","summary"] appears and fetches once. No more 401 spam.

3) Pagination keys are distinct

Click “Load more” once in the feed.
You’ll see separate entries like ["feed",{"before":null}] and ["feed",{"before":""}].
With keepPreviousData: true, the first page stays fresh/visible while the second page fetches—no flicker.

4) Retry rules

If you simulate Offline, trigger a refetch.
Your retry function should back off and then stop; for 401/403 you’ll see no retries.

5) Data shape via select

Open ["me"] and ["me","summary"]; the Data panel shows already-selected shapes if you used select (e.g., attributes plucked out).
That’s why your components don’t do ?.data?.attributes on every render.

Handy moves in Devtools

Filter: search by key substring (e.g. type feed or summary).
Sort by status → Asc/Desc to bring fetching/stale items to the top.
Remove a query to force a “cold” fetch and watch how staleTime and retries behave.
Open details and expand Observers to see which components are subscribed.

Official docs: link

Tip: keep Devtools open while writing your rules. If something refetches more than you expect, the panel will tell you why (window focus, stale transition, new observer, manual refetch).

💡 Idea #1

staleTime (cache with a clock)

staleTime controls how long data is considered fresh.
Fresh → no refetch on mount/focus.
Stale → refetch on mount/focus.

Inkline defaults:
staleTime

    staleTime: 30_000

After a successful fetch, data is considered "fresh" for 30 seconds. During that window, React Query won't refetch on mount or when windows refocus. It reduces unnecessary network chatter. You can still manually refetch at any time.

gcTime

     gcTime: 5 * 60_000

Once no component is subscribing to a query, the cached data hangs around for 5 minutes before being garbage collected. This keeps "recently seen" data available if the user navigates back quickly.

Tip: Increase staleTime for data that doesn't change often (e.g., /me), and decrease for highly volatile data.

💡 Idea #2

Centralize and use stable array keys and include params.

// src/api/keys.js
export const keys = {
  me:      () => ['me'],
  summary: () => ['me','summary'],
  feed:    (p) => ['feed', p || {}],          // { before?: string }
  note:    (id) => ['note', String(id)],
  friends: (p) => ['friendships', p || {}],   // { status?: 'accepted' | ... }
}

Why arrays? They're safely serializable and parameterized, and React Query can partially match prefixes.

💡 Idea #3

enabled (don't fetch when you can't)

Dependent queries: don't fetch /me/summary until /me resolves.
This avoids 401 spam when the user is logged out.

// src/features/me/Summary.jsx
import { useQuery } from '@tanstack/react-query';
import { request } from '../../api/client';
import { keys } from '../../api/keys';

const useMe = () => useQuery({
  queryKey: keys.me(),
  queryFn: () => request('/me'),
  select: (json) => json?.data?.attributes || null,
  retry: 0, // auth shouldn't retry
});

const Summary = () => {
  const me = useMe();
  const enabled = Boolean(me.data);

  const summary = useQuery({
    queryKey: keys.summary(),
    queryFn: () => request('/me/summary'),
    enabled,   // ← gate the query
    retry: 0,
  });

  if (me.isLoading) return <p>Loading…</p>;
  if (!me.data)     return <p>Log in to see your summary.</p>;

  return (
    <div className="card">
      {summary.isLoading ? (
        <p>Loading summary…</p>
      ) : (
        <p>
          Notes: <strong>{summary.data?.notes_count ?? '—'}</strong> ·
          Friends: <strong>{summary.data?.friends_count ?? '—'}</strong>
        </p>
      )}
    </div>
  );
};

export default Summary;

💡 Idea #4

keepPreviousData(pagination that doesn't flash)

A cursor-based feed with useQuery and keepPreviousData: true (hybrid), then the native useInfiniteQuery

Why this is a "hybrid"

We keep a local list state and append each newly fetched page to it. That's the "component-managed" part.
We still use React Query to fetch/cache each page (keepPreviousData, staleTime, retries, etc.). That's the "RQ-managed" part.

This gives you full control over how items appear (replace vs append), but it means you must:

prevent duplicate pages on refetch,
decide when to reset the list,
juggle cursors manually.

React Query's native way to do this is useInfiniteQuery, which stores all pages for you. We'll show that right after.

The robust useQuery hybrid

Key ideas:

Replace when cursor === null (first page), append otherwise.
Guard duplicates with a ref that tracks which cursor you've already applied.
Use keepPreviousData: true so the list doesn't flicker during the next page fetch.

// src/features/feed/Feed.jsx
import { useEffect, useRef, useState } from 'react';
import { useQuery } from '@tanstack/react-query';
import { request } from '../../api/client';
import { keys } from '../../api/keys';

const Feed = () => {
    const [cursor, setCursor] = useState(null);
    const [list, setList] = useState([]);
    const lastAppliedCursorRef = useRef(null); // avoid dupes/races

    const { data, isSuccess, isLoading, isFetching } = useQuery({
        queryKey: keys.feed({ before: cursor }), // e.g. ['feed', { before: null|cursor }]
        queryFn: () =>
            request(`/feed/public${cursor ? `?before=${encodeURIComponent(cursor)}` : ''}`),
        keepPreviousData: true,
        staleTime: 10_000,
        refetchOnWindowFocus: false,
    });

    const pageItems = data?.data ?? [];
    const nextCursor = data?.meta?.next_cursor ?? null;

    useEffect(() => {
        if (!isSuccess) return;

        // Apply each cursor exactly once to avoid duplicates from refetch/retry.
        if (lastAppliedCursorRef.current === cursor && cursor !== null) return;
        lastAppliedCursorRef.current = cursor;

        setList(prev =>
            cursor === null ? pageItems : prev.concat(pageItems)
        );
    }, [isSuccess, cursor, pageItems]);

    if (isLoading && list.length === 0) {
        return <div className="card">Loading…</div>;
    }

    return (
        <section className="feed">
            <div className="feed-list">
                {list.map(n => (
                    <article key={n.id} className="note">
                        <h3>{n.attributes.title}</h3>
                        <p>{n.attributes.body.slice(0, 100)}…</p>
                    </article>
                ))}
            </div>

            <div className="row">
                <button
                    className="btn"
                    disabled={!nextCursor || isFetching}
                    onClick={() => setCursor(nextCursor)}
                >
                    {isFetching ? 'Loading…' : nextCursor ? 'Load more' : 'No more'}
                </button>
            </div>
        </section>
    );
};

export default Feed;

Tip: Why the guard matters? Because React Query can refetch the same page (focus, network retry, manual refetch). Without the lastAppliedCursorRef check, the effect would append those items again.

When to prefer `useInfiniteQuery` (native infinite)

useInfiniteQuery stores pages internally; you don't need a local list or a "last cursor" guard. You only tell it how to get the next cursor. For most infinite feeds, prefer useInfiniteQuery—it’s less code and harder to get wrong.

// src/routes/feed/Feed.jsx
import { useMemo } from 'react';
import { useInfiniteQuery } from '@tanstack/react-query';
import { request } from '../../api/client';

const Feed = () => {
  const q = useInfiniteQuery({
    queryKey: ['feed'],
    queryFn: ({ pageParam }) =>
      request(`/feed/public${pageParam ? `?before=${encodeURIComponent(pageParam)}` : ''}`),
    initialPageParam: null,
    getNextPageParam: (lastPage) => lastPage?.meta?.next_cursor ?? undefined,
    staleTime: 10_000,
    refetchOnWindowFocus: false,
  });

  // derive the full list; memoize to avoid re-flattening on every render
  const list = useMemo(
    () => (q.data?.pages ?? []).flatMap(p => p?.data ?? []),
    [q.data?.pages]
  );

  if (q.isLoading && list.length === 0) {
    return <div className="card">Loading…</div>;
  }

  return (
    <section className="feed">
      <div className="feed-list">
        {list.map(n => (
          <article key={n.id} className="note">
            <h3>{n.attributes.title}</h3>
            <p>{n.attributes.body.slice(0, 100)}…</p>
          </article>
        ))}
      </div>

      <div className="row">
        <button
          className="btn"
          disabled={!q.hasNextPage || q.isFetchingNextPage}
          onClick={() => q.fetchNextPage()}
        >
          {q.isFetchingNextPage ? 'Loading…' : q.hasNextPage ? 'Load more' : 'No more'}
        </button>
      </div>
    </section>
  );
};

export default Feed;

Tip: Why useMemo here? q.data.pages is a nested array of page payloads. Flattening it on every render can be wasteful. useMemo recomputes the flattened list only when pages changes—cheap, predictable renders.

Which one should you use?

TL;DR: The hybrid is great when you want fine-grained control or you're extending an existing useQuery flow. For most infinite feeds, prefer useInfiniteQuery—it's less code and harder to get wrong.

💡 Idea #5

select(shape data once, not per render)

Use select to transform server JSON into the shape your UI wants once per fetch.

// useMe above:
select: (json) => json?.data?.attributes || null

Cleaner components (no ?.data?.attributes all over).
Stable memoization: React Query caches the selected result too.

Common pitfalls & how we fixed them

401 storms when logged out Mounting
"private" widgets on public pages can fire many unauthorized requests.
Gate them with enabled: !!me.data or wrap the section in an auth guard.
Retrying auth endpoints
Default retry can make /me or /login feel broken.
retry: 0 for auth queries/mutations, or a function that disables for 401/403.
Missing params in keys
['feed'] won’t distinguish pages. Use ['feed', { before }].
Flashing on page change
keepPreviousData: true.
Transforming data inside JSX
Doing map/filter/get every render is noisy and costly. Use select to shape data once per fetch.

Cheatsheet (copy/paste)

// Query
useQuery({
  queryKey,                 // array, include params
  queryFn,                  // () => Promise
  enabled,                  // gate by preconditions
  select,                   // shape once per fetch
  staleTime, gcTime,
  keepPreviousData,
  refetchOnWindowFocus,
  retry: (count, err) => count < 2 && ![401,403].includes(err?.status),
})

// Mutation (Part 2)
useMutation({
  mutationFn,
  onMutate, onError, onSuccess, onSettled,
})

// Cache helpers
queryClient.invalidateQueries({ queryKey: keys.feed({}) })
queryClient.setQueryData(keys.me(), updaterFn)
queryClient.cancelQueries({ queryKey: keys.feed({ before }) })

What's next (Part 2)

We'll wire mutations the Inkline way:

create/update/delete with useMutation
optimistic updates + rollback on error
the right invalidation strategy per action
toasts + form errors (Formik) without tears

Appendix — Mock API (MSW), App.jsx

We use MSW so the demo runs anywhere:

// src/mocks/handlers.js (excerpt)
import { http, HttpResponse } from 'msw'

let isAuthed = true
let feed = Array.from({ length: 25 }).map((_, i) => ({
  id: String(1000 - i),
  attributes: { title: `Note #${1000 - i}`, body: `Demo body for note #${1000 - i}` }
}))

export const handlers = [
  http.get('/me', () =>
    isAuthed
      ? HttpResponse.json({ data: { type: 'users', id: '1', attributes: { email: 'demo@inkline.live' } }})
      : HttpResponse.json({ error: 'Unauthorized' }, { status: 401 })
  ),

  http.get('/me/summary', () =>
    isAuthed
      ? HttpResponse.json({ notes_count: feed.length, friends_count: 7 })
      : HttpResponse.json({ error: 'Unauthorized' }, { status: 401 })
  ),

  http.get('/feed/public', ({ request }) => {
    const url = new URL(request.url)
    const before = url.searchParams.get('before')
    const start = before ? feed.findIndex(n => n.id === before) : 0
    const items = feed.slice(Math.max(start, 0), Math.max(start, 0) + 10)
    const next = feed[Math.max(start, 0) + 10]?.id ?? null
    return HttpResponse.json({ data: items, meta: { next_cursor: next } })
  }),
]

This is the final App.jsx:

  import Summary from './features/me/Summary';
import Feed from './features/feed/Feed';

const App = () => (
  <main className="container">
    <h1>React Query - Inkline-style JS Examples</h1>

    <section className='summary'>
      <h2>Dependent query ( /me → /me/summary )</h2>
      <Summary />
    </section>

    <section className='feed'>
      <h2>Keyset pagination ( /feed/public )</h2>
      <Feed />
    </section>
  </main>
);

export default App;