LC Patterns — Arrays & Strings

What it is: Add up the array once into a "running total" array, so any range sum [l,r] becomes one subtraction: pre[r+1] − pre[l]. The product version: "product of everything except me" = (product to my left) × (product to my right) — two passes, no division.

Intuition: A range sum is the difference of two running totals — everything up to r, minus everything before l. Works for any operation that can be "undone" (sum and XOR both can). When it can't be undone cleanly (products with a zero, or min/max), switch to the two-sided version: build a total from the left and one from the right, and combine.

vector<int> productExceptSelf(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, 1);
    for (int i = 1; i < n; ++i) res[i] = res[i-1] * a[i-1];   // res[i] = product of everything to the left
    long long suf = 1;
    for (int i = n - 1; i >= 0; --i) { res[i] *= suf; suf *= a[i]; }  // multiply in the right side
    return res;
}

What it is: Count (or find) subarrays whose sum is exactly k — even with negatives, where sliding windows fail. Walk once keeping a running sum. A subarray [j+1..i] sums to k exactly when pre[i] − pre[j] = k. So at each step ask the map: "have I seen an earlier running-sum equal to pre[i] − k?"

Intuition: This turns a "which two endpoints?" search into a "walk forward and remember what I've seen" scan. It's literally Two Sum, played on running sums. 525 turns each 0 into −1 so "equal 0s and 1s" becomes "sum = 0"; 974 stores the running sum mod k; "longest such subarray" versions store the first index a running-sum appeared at.

int subarraySum(vector<int>& a, int k) {
    unordered_map<long long, int> seen{{0, 1}};   // "empty prefix" seen once — lets subarrays starting at index 0 count
    long long pre = 0; int cnt = 0;
    for (int x : a) {
        pre += x;
        if (auto it = seen.find(pre - k); it != seen.end()) cnt += it->second;  // ask before recording
        ++seen[pre];
    }
    return cnt;
}

What it is: The mirror image of prefix sums. For many updates "add v to every element in [l,r]," don't touch every element — record the two edges: diff[l] += v and diff[r+1] -= v. One prefix-sum pass turns the edges back into final values. So m updates + one pass = O(n + m) instead of O(n·m).

Intuition: A range update changes nothing in the middle — only the two boundaries (where the added value switches on and off). Store where things change, and "add it all up" at the end. It's an event timeline: car-pooling is "+v get on at l, −v get off at r."

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<long long> diff(n + 1, 0);
    for (auto& b : bookings) { diff[b[0]-1] += b[2]; diff[b[1]] -= b[2]; }  // 1-indexed problem → shift to 0-indexed
    vector<int> res(n);
    long long run = 0;
    for (int i = 0; i < n; ++i) { run += diff[i]; res[i] = run; }   // add up the edges
    return res;
}

What it is: When values are bounded by the array's size (values in [1, n]), the array acts as its own lookup table. Mark "value v present" by changing position v−1 (e.g. flip its sign), or cyclic-sort each value to its home slot so a[i] == i+1. O(n) time, O(1) extra space — the follow-up that rules out "just use a hash set."

Intuition: A value→info map costs O(n) memory. But if values fit in [1,n], the array's own indices are that key space — the slot tells you the value, and the sign bit (or swap position) is free storage you already own. In First Missing Positive, once every value is home, the first slot not holding its expected value points straight at the answer.

int firstMissingPositive(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n; ++i)
        while (a[i] >= 1 && a[i] <= n && a[a[i]-1] != a[i])
            swap(a[i], a[a[i]-1]);            // send a[i] to its home slot
    for (int i = 0; i < n; ++i)
        if (a[i] != i + 1) return i + 1;      // first slot that isn't holding its own value
    return n + 1;
}

What it is: Rotating an array by k, rotating a matrix 90°, reversing words — all done in place by combining simple reversals. Rotate-by-k = reverse the whole thing, then reverse the first k, then the rest. Rotate a matrix = transpose, then reverse each row. Reverse words = reverse the whole string, then reverse each word back.

Intuition: Reversing undoes itself and needs no extra space, and rotations/word-swaps break down neatly into a few reversals. Don't trust the formula blindly — follow one element: track where a[0] ends up after each reversal; if it lands where it should, the whole thing is right.

void rotate(vector<int>& a, int k) {
    int n = a.size(); k %= n;
    reverse(a.begin(), a.end());
    reverse(a.begin(), a.begin() + k);
    reverse(a.begin() + k, a.end());
}
// Matrix 90° clockwise: transpose (swap a[i][j], a[j][i] for j > i), then reverse each row.

What it is: Two related skills. (a) Walking a matrix in an unusual order (spiral, diagonal) by tracking shrinking boundaries. (b) Updating a matrix in place when a new value depends on old neighbors — done by storing both old and new value in one cell (an extra bit or sentinel), decoding in a second pass.

Intuition: (a) A spiral is four edge-walks — top → right → bottom → left — the boundary shrinking after each side. The loop structure is the answer; simulate it. (b) Game of Life has a chicken-and-egg problem: read old values while writing new. It goes away if one cell holds both — store old + 2·new (bit 0 = old, bit 1 = new), then a final >> 1 pass reveals the new grid. Same idea as 73's trick: use the first row/column as scratch space.

int top = 0, bot = m - 1, lef = 0, rig = n - 1;
while (top <= bot && lef <= rig) {
    for (int j = lef; j <= rig; ++j) out.push_back(a[top][j]);   ++top;   // top row, →
    for (int i = top; i <= bot; ++i) out.push_back(a[i][rig]);   --rig;   // right col, ↓
    if (top <= bot) for (int j = rig; j >= lef; --j) out.push_back(a[bot][j]); --bot;  // bottom row, ←
    if (lef <= rig) for (int i = bot; i >= top; --i) out.push_back(a[i][lef]); ++lef;  // left col, ↑
}

What it is: Problems about ranges [start, end] — merge overlapping ones, insert a new one, or count how many to delete so none overlap. Almost all yield to: sort by start (or by end for greedy-deletion), then one linear pass carrying the "current" interval, deciding at each step: overlap, or start a new group?

Intuition: Once sorted by start, an interval can only overlap the one right before it — so cur.end ≥ next.start is the complete overlap test, and merging is cur.end = max(cur.end, next.end). The greedy cousin (435): to keep the most non-overlapping intervals, sort by end and always keep the earliest finisher — it leaves the most room. Overlap test to memorize: two intervals overlap when max(s1,s2) ≤ min(e1,e2).

vector<vector<int>> merge(vector<vector<int>>& iv) {
    sort(iv.begin(), iv.end());                       // by start (then end)
    vector<vector<int>> out;
    for (auto& in : iv) {
        if (!out.empty() && out.back()[1] >= in[0]) out.back()[1] = max(out.back()[1], in[1]);  // overlap → extend
        else out.push_back(in);                                                                  // gap → new group
    }
    return out;
}

What it is: Group or compare things that are "the same after some transformation" — anagrams, isomorphic strings, mirrored patterns — by turning each item into a single canonical key (sorted letters, a letter-count signature, a first-occurrence encoding) and hashing on that key. Equivalent items produce the same key, so they land in the same bucket automatically.

Intuition: Pairwise "same-except-for-rearrangement" is slow (O(n²)). But normalize each item to one standard form and equal items collide for free. Isomorphic strings / word patterns → encode each char by the index where it first appeared ("egg" → 0,1,1; "add" → 0,1,1 → match ⇒ isomorphic). First-occurrence encoding automatically enforces the two-way matching an isomorphism needs.

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> g;
    for (auto& s : strs) {
        string key(26, 0);
        for (char c : s) ++key[c - 'a'];      // the letter-count signature is the canonical key
        g[key].push_back(s);
    }
    vector<vector<string>> out;
    for (auto& [k, v] : g) out.push_back(move(v));
    return out;
}

What it is: No clever algorithm — just a spec you implement exactly: atoi (skip whitespace, read a sign, read digits, clamp on overflow), comparing version numbers (split, compare number by number, missing parts count as 0), multiplying big numbers digit by digit. Graded on careful edge-case handling and clean state, not cleverness.

Intuition: These test whether you can turn an English spec into ordered steps without dropping a case. Method: (1) restate the spec as a numbered list of phases; (2) list edge inputs straight from the spec ("", " ", "+-2", "words 42", overflow "2147483648"); (3) code one phase at a time. Overflow idiom: check res > (INT_MAX − digit) / 10 before multiplying. Multiply-strings: digits at i and j land in result position i + j + 1 (carry into i + j).

int res = 0;
while (i < n && isdigit(s[i])) {
    int d = s[i] - '0';
    if (res > (INT_MAX - d) / 10)             // would overflow on the next step → clamp per spec
        return sign == 1 ? INT_MAX : INT_MIN;
    res = res * 10 + d;  ++i;
}

What it is: One pass with an unordered_set/unordered_map replacing a nested loop. Two Sum asks the map "have I seen target − x?" Longest Consecutive Sequence (128) gets O(n) on unsorted data by only starting to count a run at its head — a number x where x−1 is not in the set.

Intuition: A hash lookup is basically a free inner loop. The deeper trick in 128 is accounting for the work: walking x, x+1, x+2, … looks quadratic, but only sequence heads start a walk, and every element is walked once across the whole run → amortized O(n). "Only start at heads" is a general de-dup idea: make each piece of work belong to exactly one owner. (Two Sum here vs Two Sum II: unsorted + need indices → hash map; already sorted → two pointers.)

int longestConsecutive(vector<int>& a) {
    unordered_set<int> s(a.begin(), a.end());
    int best = 0;
    for (int x : s) {
        if (s.count(x - 1)) continue;          // not a head — someone else's run counts this one
        int y = x;
        while (s.count(y + 1)) ++y;            // walk the run forward
        best = max(best, y - x + 1);
    }
    return best;
}