The trick n & (n - 1) is one of the most elegant one-liners in computer engineering. Let’s look at the exact bitwise mechanics so the mathematical proof becomes obvious.

1. What happens when you subtract 1 in binary?

Think about standard base-10 math: when you subtract 1 from 1000, what happens? The lowest non-zero digit (1) becomes 0, and all trailing zeroes become 9s: 0999.

Binary works exactly the same way, but with 0s and 1s:

Any positive binary integer can be written in this general form:

n = (arbitrary prefix) 1 0 0 0 ... 0

where the 1 shown is the lowest set bit (the rightmost 1), followed by zero or more 0s.

When you compute n - 1:

1. The arbitrary prefix before the lowest 1 remains completely untouched.
2. That lowest 1 turns into a 0 (borrowing from the subtraction).
3. All the trailing 0s flip into 1s!

    n     = (prefix) 1 0 0 0
  n - 1   = (prefix) 0 1 1 1

2. The Bitwise AND Operation: n & (n – 1)

Now perform a bitwise AND between n and n - 1:

    n     = (prefix) 1 0 0 0
& n - 1   = (prefix) 0 1 1 1
----------------------------
  result  = (prefix) 0 0 0 0

Look at what happened:

• The prefix matched identically → remains preserved.
• The rightmost 1 was paired with 0 → becomes 0!
• The trailing 0s were paired with 1s → remain 0!

Conclusion: The operation n & (n - 1) turns off the lowest set bit in n and leaves every other bit completely unchanged. Pure mathematical magic!

3. Real-World Applications

A. Counting Set Bits in O(k) time (where k is number of 1s)

Instead of looping 32 or 64 times, Brian Kernighan’s algorithm loops only as many times as there are 1-bits:

def count_set_bits(n: int) -> int:
    count = 0
    while n > 0:
        n &= (n - 1)  # Strips off one set bit per loop iteration
        count += 1
    return count

If a 64-bit integer has only two set bits, this loop executes exactly twice and terminates!

B. Instant Power of Two Check in O(1)

A power of two in binary has exactly one set bit (e.g. 8 = 1000_2, 16 = 10000_2). If you strip that single bit and the result is 0, it was a power of 2:

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

C. Hardware POPCNT Alternative

On modern x86_64 CPUs, you have the dedicated hardware assembly instruction POPCNT (or __builtin_popcount in GCC/Clang), which computes set bits in a single CPU cycle. But when writing portable code or kernel routines without AVX/SSE guarantees, Brian Kernighan’s algorithm remains the golden standard.

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.

The Largest Rectangle in Histogram is famous because it feels like magic until you see the visual geometry behind it. Let’s demystify it once and for all.

1. The Core Realization

For any bar at index k with height H = heights[k], what is the widest rectangle you can make using H as the height?

The rectangle can extend as far left as possible until it hits a bar shorter than H, and as far right as possible until it hits another bar shorter than H.

So the entire problem boils down to finding two things for every bar:

1. The First Shorter Bar on the Left (left boundary).
2. The First Shorter Bar on the Right (right boundary).

2. Why a Monotonic Increasing Stack?

A monotonic stack keeps indices of bars whose heights are strictly increasing: [2, 4, 6, 8].

As long as the next bar is taller or equal, the rectangle could potentially keep growing, so we just push its index onto the stack.

The Trigger: The moment you encounter a bar that is shorter than the top of the stack (say we see a bar of height 3 when the stack top is 8), you have found the Right Boundary for that 8! The bar of height 8 cannot extend any further to the right. Its journey is finished.

When you pop 8:

• The current index i is its first shorter bar on the right.
• The new top of the stack (the element directly below it) is its first shorter bar on the left!

Therefore, the width of the rectangle bounded by height H is simply: width = (i - stack[-1] - 1).

3. Clean Python 3.12 Implementation with Sentinel Trick

def largest_rectangle_area(heights: list[int]) -> int:
    """Calculates maximum rectangular area in histogram in O(N) time."""
    # Appending 0 at the end acts as a sentinel that forces
    # all remaining bars in the stack to be popped and calculated!
    extended_heights = heights + [0]
    stack: list[int] = []  # Stores indices
    max_area = 0

    for i, h in enumerate(extended_heights):
        # While the current bar is shorter than the bar at stack top
        while stack and extended_heights[stack[-1]] > h:
            height = extended_heights[stack.pop()]
            
            # If stack is empty, it means 'height' was shorter than everything to its left!
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
            
        stack.append(i)

    return max_area

4. Step-by-Step Trace with Numbers

Let’s trace heights = [2, 1, 5, 6, 2, 3] with sentinel [2, 1, 5, 6, 2, 3, 0]:

• i = 0 (h=2): Stack = [0]
• i = 1 (h=1): 1 < 2! Pop 0 (h=2). Stack empty → width = 1. Area = 2 * 1 = 2. Push 1. Stack = [1].
• i = 2 (h=5): 5 > 1. Push 2. Stack = [1, 2].
• i = 3 (h=6): 6 > 5. Push 3. Stack = [1, 2, 3].
• i = 4 (h=2): 2 < 6!
  • Pop 3 (h=6): right = 4, left = 2 → width = 4 - 2 - 1 = 1. Area = 6 * 1 = 6.
  • Pop 2 (h=5): right = 4, left = 1 → width = 4 - 1 - 1 = 2. Area = 5 * 2 = 10!

  Push 4. Stack = [1, 4].

• Finally, the trailing 0 sentinel cleanly flushes all remaining elements.

Max Area = 10 (from bars of height 5 and 6).

5. Why is this strictly O(N)?

Even though there is a while loop inside the for loop, every index is pushed onto the stack exactly once and popped from the stack at most once. Total operations across the entire array are at most 2N. That is a rock-solid, linear O(N) runtime with O(N) memory.

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.