Arrays, strings, and sequences.

Sequence problems become tractable when an index movement permanently rules out candidates or when a small piece of state summarizes the prefix already processed. The implementation should make that fact visible: every pointer move has a reason, and every map entry answers a specific query.

Two pointers

For a sorted pair sum, the endpoints describe the smallest and largest remaining values. If their sum is too small, no pair using the current left value can work: pairing it with anything left of right only makes the sum smaller. Incrementing left therefore discards an entire set of impossible pairs.

two_sum_sorted.cppstd::optional<std::pair<std::size_t, std::size_t>>
two_sum_sorted(std::span<const int> values, int target) {
    if (values.size() < 2) return std::nullopt;

    std::size_t left = 0;
    std::size_t right = values.size() - 1;
    while (left < right) {
        const auto sum =
            static_cast<std::int64_t>(values[left]) + values[right];
        if (sum == target) return std::pair{left, right};
        if (sum < target) ++left;
        else --right;
    }
    return std::nullopt;
}

3Sum sorts first, fixes one value, and runs this same search over the suffix. Duplicate skipping happens at all three positions. Container With Most Water also uses endpoints, but moves the shorter wall because moving the taller wall cannot improve the height bound. Valid Palindrome skips irrelevant characters at both ends. Sorted Squares writes the largest absolute value from either end into the output from right to left.

Sliding window

A variable window expands right once per iteration. When the window becomes invalid, a nested loop advances left until validity returns. Although the code contains two loops, each endpoint crosses the input once, so the total number of endpoint moves is linear.

Longest Substring Without Repeating Characters can store membership in a set and erase characters one by one. Storing the last index instead lets left jump directly past the duplicate. The table stores “one after the last position,” so its zero initialization also means “not seen.”

longest_unique.cppstd::size_t longest_unique(std::string_view text) {
    std::array<std::size_t, 256> next_allowed{};
    std::size_t left = 0;
    std::size_t best = 0;

    for (std::size_t right = 0; right < text.size(); ++right) {
        const auto byte = static_cast<unsigned char>(text[right]);
        left = std::max(left, next_allowed[byte]);
        best = std::max(best, right - left + 1);
        next_allowed[byte] = right + 1;
    }
    return best;
}

Not every contiguous problem permits a window. Negative values break the usual “sum too large, shrink left” monotonicity: removing a negative value increases the sum. Subarray Sum Equals K therefore uses prefix counts instead. Likewise, Minimum Window Substring needs frequency deficits, not only a set, because multiplicity matters.

Prefix sums and prefix counts

Let prefix[j] be the sum of the first j elements. The sum of [i, j) is prefix[j] - prefix[i]. For target k, each current prefix needs the number of earlier prefixes equal to prefix - k. A frequency map answers exactly that query.

subarray_sum_count.cppstd::int64_t subarray_sum_count(
    std::span<const int> values,
    std::int64_t target
) {
    std::unordered_map<std::int64_t, std::int64_t> frequency{{0, 1}};
    std::int64_t prefix = 0;
    std::int64_t answer = 0;

    for (const int value : values) {
        prefix += value;
        if (const auto it = frequency.find(prefix - target);
            it != frequency.end()) {
            answer += it->second;
        }
        ++frequency[prefix];
    }
    return answer;
}

Query before inserting the current prefix when the subarray must be nonempty. Use a 64-bit prefix even if each element is int. For Contiguous Array, convert zero to −1: equal prefix balances then enclose the same count of zeroes and ones. For Product Except Self, the prefix state is a running product written into the output, followed by a suffix product moving in the opposite direction.

Hashing and canonical keys

A hash set remembers membership. A hash map attaches a count, index, or object to the key. The essential design decision is the key. Group Anagrams can sort each word into a canonical representation, so all permutations of the same letters map to the same string.

group_anagrams.cppstd::vector<std::vector<std::string>>
group_anagrams(std::span<const std::string> words) {
    std::unordered_map<std::string, std::vector<std::string>> groups;
    for (const auto& word : words) {
        std::string key = word;
        std::sort(key.begin(), key.end());
        groups[key].push_back(word);
    }

    std::vector<std::vector<std::string>> answer;
    answer.reserve(groups.size());
    for (auto& [key, group] : groups) {
        answer.push_back(std::move(group));
    }
    return answer;
}

A 26-count array avoids sorting and makes the per-word work linear in word length, but it needs a custom hash or serialization. Longest Consecutive Sequence uses a set and begins a scan only at values whose predecessor is absent. That “start only at sequence heads” condition prevents repeated traversal and makes the total work expected linear.

Measured pair scan versus hash map

Two correct unsorted Two Sum implementations expose the tradeoff. The baseline checks pairs in index order and allocates nothing. The optimized version stores earlier values in unordered_map, paying for allocation, hashing, bucket lookup, and weaker locality to remove the nested scan.

two_sum_scan_and_hash.hppResult two_sum_scan(std::span<const int> values, int target) {
    for (std::size_t left = 0; left < values.size(); ++left)
        for (std::size_t right = left + 1; right < values.size(); ++right)
            if (static_cast<std::int64_t>(values[left]) + values[right] ==
                target)
                return IndexPair{left, right};
    return std::nullopt;
}

Result two_sum_hash(std::span<const int> values, int target) {
    std::unordered_map<int, std::size_t> first_index;
    first_index.reserve(values.size());
    first_index.max_load_factor(0.75F);

    for (std::size_t index = 0; index < values.size(); ++index) {
        const std::int64_t complement =
            static_cast<std::int64_t>(target) - values[index];
        if (complement >= std::numeric_limits<int>::min() &&
            complement <= std::numeric_limits<int>::max()) {
            const auto found = first_index.find(static_cast<int>(complement));
            if (found != first_index.end())
                return IndexPair{found->second, index};
        }
        first_index.try_emplace(values[index], index);
    }
    return std::nullopt;
}

The measured input is [0, n) with target 2n - 3, so only the final pair solves it and both functions process the full input. Google Benchmark 1.9.5 ran nine randomly interleaved repetitions after warm-up with GCC 11.4 Release code. These are median CPU times from that host, not portable crossover constants.

The scan wins at 16 and 64 elements because its tight contiguous loop has little setup. The hash table crosses over between 64 and 256 for this compiler, library, machine, and input. The measurement package includes 5,006 differential cases, raw JSON/CSV, the benchmark source, and a Linux perf stat script for cycles, instructions, branches, and cache events.

Cyclic placement

Use the input array as a placement table. A value x belongs at index x - 1. Keep swapping the current value toward its destination until the position is correct, contains a duplicate, or holds an out-of-range value. Each successful swap fixes at least one destination, so there are at most n successful swaps.

first_missing_positive.cppint first_missing_positive(std::vector<int> values) {
    const std::size_t size = values.size();
    std::size_t index = 0;

    while (index < size) {
        const int value = values[index];
        const bool in_range =
            value > 0 && static_cast<std::size_t>(value) <= size;
        if (!in_range) {
            ++index;
            continue;
        }
        const std::size_t destination = static_cast<std::size_t>(value - 1);
        if (values[destination] == value) ++index;
        else std::swap(values[index], values[destination]);
    }

    for (std::size_t i = 0; i < size; ++i) {
        if (values[i] != static_cast<int>(i + 1))
            return static_cast<int>(i + 1);
    }
    return static_cast<int>(size + 1);
}

Intervals: sort, merge, and sweep

Sorting by start makes every future interval begin no earlier than the current one. The merged output therefore needs only its last interval. If the next start is inside it, extend the end. Otherwise begin a new component.

merge_intervals.cppusing Interval = std::array<int, 2>;

std::vector<Interval> merge_intervals(std::vector<Interval> intervals) {
    std::sort(intervals.begin(), intervals.end());
    std::vector<Interval> merged;

    for (const auto interval : intervals) {
        if (merged.empty() || interval[0] > merged.back()[1]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = std::max(merged.back()[1], interval[1]);
        }
    }
    return merged;
}

Meeting Rooms II changes the state: sort starts, then retain active end times in a min-heap, or sort separate start and end arrays and sweep them. Maximum non-overlapping selection sorts by end rather than start. That ordering supports an exchange argument: replacing a selected interval with one that ends earlier cannot reduce the remaining space.

Fast and slow pointers

If a cycle exists, a pointer moving two edges per iteration eventually laps a pointer moving one. To locate the entry, reset one pointer to the start after the meeting and advance both by one. The distance from the start to the entry equals the remaining distance around the cycle from the meeting point.

cycle_start.cppListNode* cycle_start(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    do {
        if (fast == nullptr || fast->next == nullptr) return nullptr;
        slow = slow->next;
        fast = fast->next->next;
    } while (slow != fast);

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

Find the Duplicate Number treats each array value as the next index, producing a functional graph without modifying the input. Happy Number applies the digit-square transform as its next function. For a list midpoint, start both pointers at the head and return slow when fast reaches the end. Decide explicitly whether an even-length list should return the first or second middle.

Decision table