Data Structures & Algorithms

This is one of the most common points of confusion when studying LIS. Let’s clear up the mystery of why the tails array works even though its contents look ‘wrong’.

1. What does the `tails` array actually represent?

In Patience Sorting (inspired by solitaire card games):

tails[k] stores the SMALLEST ending value of an increasing subsequence of length k + 1 found so far.

Why do we care about the smallest ending value? Because in an increasing subsequence, the smaller the number you end with, the easier it is for future numbers to be bigger than it! You want to keep your options as open as possible.

2. The Step-by-Step Card Dealing Analogy

Suppose our array is: [10, 9, 2, 5, 3, 7, 101, 18].

1. See 10: tails = [10] (Best subsequence of len 1 ends with 10).
2. See 9: 9 < 10. Replace 10 with 9: tails = [9] (Ending with 9 is strictly better than ending with 10).
3. See 2: 2 < 9. Replace 9 with 2: tails = [2].
4. See 5: 5 > 2! Extend! tails = [2, 5] (Best len 1 ends in 2, best len 2 ends in 5).
5. See 3: 3 < 5. Replace 5 with 3: tails = [2, 3] (Now best len 2 ends in 3!).
6. See 7: 7 > 3! Extend! tails = [2, 3, 7] (Len 3).
7. See 101: Extend! tails = [2, 3, 7, 101] (Len 4).
8. See 18: 18 < 101. Replace 101 with 18: tails = [2, 3, 7, 18].

Total length of tails is 4. The answer is 4!

3. Why the array contents might look scrambled, but length is ALWAYS correct

Imagine if after [2, 3, 7, 18] we saw 1. We would replace 2 with 1, resulting in tails = [1, 3, 7, 18].

Notice that [1, 3, 7, 18] might not be a valid subsequence from the original array. And that doesn’t matter!

Replacing 2 with 1 only prepares the board for a hypothetical future subsequence that starts with 1. It does not change the fact that a valid subsequence of length 4 ([2, 3, 7, 18]) was already locked in!

The length of tails only increases when a number is strictly greater than ALL existing tail values. Replacements never shrink the array length!

Clean Python 3.12 Implementation with bisect_left

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    """Calculates length of LIS in O(N log N) time and O(N) space."""
    tails = []

    for x in nums:
        # Binary search: find first element in tails >= x
        idx = bisect_left(tails, x)
        
        if idx == len(tails):
            # x is strictly greater than all existing tails -> extend length!
            tails.append(x)
        else:
            # Found smaller tail candidate -> update in-place
            tails[idx] = x

    return len(tails)

Complexity Breakdown

• Time Complexity: O(N log N). We iterate through N elements, and for each element we perform binary search over tails (at most length N). N * log(N). For 100,000 elements, this finishes in 0.02 seconds (compared to ~45 seconds for O(N^2)).
• Space Complexity: O(N) to hold the tails array.

Morris Traversal is one of the most brilliant algorithms in computer science. It solves the exact constraint you’re facing: how do you traverse a tree without spending any extra memory on a stack?

1. The Core Secret: Threaded Binary Trees

When you are at a node and go deep into its left subtree, how do you get back up to the node without a parent pointer or call stack? Normally, you need a stack to remember the return path.

J. H. Morris realized something clever: in every binary tree, about half of all pointers are NULL! Every leaf node has a null right child that is sitting there doing nothing.

Morris repurposes these unused null pointers as temporary bridge wires (called “threads”) back to the inorder successor:

1. Find the node’s inorder predecessor (the rightmost node in the left subtree).
2. If its right pointer is null, point it back to the current node: predecessor->right = current. Then move current = current->left.
3. If its right pointer is already pointing to current, that means you have already finished visiting the left subtree! You print/record current->val, restore the pointer to null (repairing the tree), and move current = current->right!

When the algorithm finishes, the tree is 100% restored to its original state. Zero memory allocated, zero permanent mutations!

Clean C++20 Morris Inorder Traversal

#include <vector>
#include <cstdint>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> morrisInorderTraversal(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;

    while (curr != nullptr) {
        if (curr->left == nullptr) {
            // Case 1: No left child, visit this node and move right
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // Case 2: Find inorder predecessor (rightmost in left subtree)
            TreeNode* pred = curr->left;
            while (pred->right != nullptr && pred->right != curr) {
                pred = pred->right;
            }

            if (pred->right == nullptr) {
                // First time visiting: create temporary thread
                pred->right = curr;
                curr = curr->left;
            } else {
                // Second time visiting: restore tree and visit curr
                pred->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

Complexity & Trade-offs

• Time Complexity: O(N). Even though we search for predecessors, each edge in the tree is traversed at most 3 times (once to find predecessor, once to create thread, once to remove thread). 3 * (N - 1) = O(N).
• Space Complexity: O(1) auxiliary space. Just two pointers (curr and pred). No call stack, no heap allocations.
• Thread-Safety Warning: Because Morris Traversal temporarily mutates right pointers during execution, it is not safe for concurrent readers on the same tree instance. If multiple threads read the tree simultaneously, use standard recursive DFS with a large stack or an explicit thread-local queue.

Binary Search on Answer Space is one of the highest-leverage algorithmic patterns you can learn. Once you recognize it, dozens of seemingly hard problems (shipping packages, splitting arrays, cutting ribbons, allocating memory) all collapse into the exact same 15 lines of code.

1. When Can You Use This Pattern?

Ask yourself one simple question: Is the condition monotonic?

• If Koko eats at speed k = 100 bananas/hour and succeeds in finishing in under h hours, would eating at speed k = 101 also succeed? Yes, always.
• If eating at speed k = 5 is too slow and fails, would eating at speed k = 4 also fail? Yes, always.

Because the outcome transitions cleanly from False, False, ..., True, True, True, the answer space is monotonic. That means we don’t need to test every speed from 1 to 1 billion linearly—we can binary search it in O(log(MaxPile)) steps!

2. The Integer Ceiling Trick (Say Goodbye to Float Bugs)

If Koko has a pile of 7 bananas and eats at speed k = 3, she needs ceil(7 / 3) = 3 hours.

In Python or C++, doing math.ceil(pile / k) converts the numbers to IEEE-754 64-bit floats. On massive numbers (e.g. 10^14), floating-point precision degrades, causing silent off-by-one errors.

The standard integer arithmetic replacement for ceil(a / b) is:

hours = (pile + k - 1) // k

Let’s test it: (7 + 3 - 1) // 3 = 9 // 3 = 3. Exactly right, 100% integer math, zero float conversions!

3. Clean Python 3.12 Implementation

from typing import Sequence

def min_eating_speed(piles: Sequence[int], h: int) -> int:
    """Finds minimum integer eating speed k such that total hours <= h."""
    
    # Lower bound: Koko must eat at least 1 banana per hour
    # Upper bound: Eating faster than the largest pile doesn't save any more time
    low = 1
    high = max(piles)
    ans = high

    def can_finish(speed: int) -> bool:
        total_hours = 0
        for pile in piles:
            # Equivalent to ceil(pile / speed) without floats
            total_hours += (pile + speed - 1) // speed
            if total_hours > h:
                return False  # Early exit optimization
        return total_hours <= h

    while low <= high:
        mid = low + (high - low) // 2
        
        if can_finish(mid):
            ans = mid         # mid is valid, but can we go even slower?
            high = mid - 1    # try searching left
        else:
            low = mid + 1     # too slow, must eat faster

    return ans

4. Complexity & Production Benchmarks

• Time Complexity: O(N * log(M)) where N is the number of piles and M is max(piles). If M = 10^9, log2(10^9) ≈ 30. Even with 100,000 piles, the validation function runs at most 30 times. Total operations: ~3 million, executing in under 15 milliseconds.
• Space Complexity: O(1) auxiliary memory.
• Overflow Note for C++ / Java: In C++, total_hours can easily exceed 2^31 - 1 if speeds are small and piles are large. Always declare int64_t total_hours = 0; to prevent integer overflow.

This is a classic problem where the textbook solution and the production solution diverge. When you are moving 10 million integers in memory, allocating a temp slice or doing naive cyclic swaps will kill your performance due to cache misses.

The cleanest, most battle-tested way to do this in production is the 3-Reversal Trick (often called the Reversal Algorithm). It requires zero extra memory and traverses contiguous memory sequentially, which modern CPU prefetchers love.

1. The Intuition (Why 3 Reversals Work)

Suppose you have the array [1, 2, 3, 4, 5, 6, 7] and you want to rotate right by k = 3 (so [5, 6, 7, 1, 2, 3, 4]).

Notice the split: the last k elements need to move to the front, and the first n - k elements move to the back. If you reverse the whole thing first, everything is in the right neighborhood but backwards:

1. Reverse the entire array: [7, 6, 5, 4, 3, 2, 1]
2. Reverse the first k elements (0 to k-1): [5, 6, 7, 4, 3, 2, 1]
3. Reverse the remaining n-k elements (k to n-1): [5, 6, 7, 1, 2, 3, 4]

Done! Every element is now in its exact final position.

2. Production C++20 Implementation

#include <vector>
#include <algorithm>
#include <cstdint>

// In-place rotation using standard cache-friendly iterator reversal
void rotateArrayInPlace(std::vector<int32_t>& nums, size_t k) {
    const size_t n = nums.size();
    if (n <= 1) return;
    
    // Normalize k in case k > n
    k = k % n;
    if (k == 0) return;

    // Helper lambda for two-pointer swap
    auto reverseRange = [&nums](size_t start, size_t end) {
        while (start < end) {
            std::swap(nums[start], nums[end]);
            ++start;
            --end;
        }
    };

    // 1. Flip everything
    reverseRange(0, n - 1);
    // 2. Flip the first k
    reverseRange(0, k - 1);
    // 3. Flip the rest
    reverseRange(k, n - 1);
}

3. Python 3.12 Clean Version

def rotate_in_place(nums: list[int], k: int) -> None:
    """Rotates nums to the right by k steps in-place with O(1) extra space."""
    n = len(nums)
    if n <= 1:
        return
    k = k % n
    if k == 0:
        return

    def reverse(start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    # Step 1: reverse full list
    reverse(0, n - 1)
    # Step 2: reverse first k elements
    reverse(0, k - 1)
    # Step 3: reverse remaining elements
    reverse(k, n - 1)

4. Complexity Breakdown

• Time Complexity: O(N) total time. Step 1 does n/2 swaps, Step 2 does k/2 swaps, and Step 3 does (n-k)/2 swaps. Total swaps = exactly n swaps. You can't beat linear time because every element must change position.
• Space Complexity: O(1) auxiliary space. Just two index pointers living directly in CPU registers.
• Cache Friendliness: Because the pointers move inward in contiguous linear blocks, L1/L2 cache prefetching works at full hardware memory bandwidth.

5. Real-World Gotchas to Watch Out For

• When k > n: Always take k = k % n. Forgetting this causes out-of-bounds pointer crashes when k = 15 on an array of length 5.
• Negative k (Left Rotation): If your system asks for a left rotation by k, simply transform it: a left rotation by k is equivalent to a right rotation by (n - (k % n)) % n.
• Empty or Single Element Arrays: Check n <= 1 upfront to prevent unsigned integer underflow on n - 1.