Arrays & Strings II

Arrays and strings are the most-tested category in interviews, and this second pass is where the questions stop being warm-ups. The first array session was two pointers and sliding windows on easy mode; this one is the hard mode: three-pointer partitions that sort in one scan, in-place dedup that keeps exactly k copies, matrices you rotate without extra memory, comparators that build the largest possible number, the whole 2Sum → 3Sum → kSum ladder, merging k sorted streams, and finding the median of two sorted arrays in logarithmic time. Every problem below traces back to a small handful of ideas — two-pointer dialects, region invariants, binary reduction, and heaps — so the goal is not to memorize twenty solutions but to see the four or five patterns they are all wearing.

String Mechanics & the Two-Pointer Dialects

Before any problem, two pieces of Java fluency decide whether your code is fast or accidentally quadratic. First, strings are immutable. cur = cur + "1" does not append — it allocates a brand-new string and copies every existing character, which is O(n). Do that inside a loop and you have silently written an O(n²) algorithm. When you build a result character by character, use StringBuilder (append is amortized O(1)) or a preallocated char[]. Reach for charAt(i) to read a single character and toCharArray() to get a mutable buffer.

There is a systems echo here worth naming, because interviewers do: immutability is what makes strings safe to share the way stateless services are safe to scale — no caller can mutate them under you — whereas a mutable StringBuilder is stateful and must be owned by one writer. Same immutability tradeoff, one abstraction level up.

The workhorse of this whole session is the two-pointer technique, and it shows up in two distinct dialects that beginners blur together:

One more piece of vocabulary that pays off everywhere below: interval semantics. Whenever you track a region with pointers, decide up front whether each end is inclusive or exclusive — [), [], (], () — and write it as a comment. Half the off-by-one bugs in partition and sliding-window code are just a boundary you never pinned down. And for any sliding-window problem, answer three questions before writing code: where do the pointers start, where do they end, and where does the answer live (at the moment the window is valid, or after it closes).

In-Place Deduplication: One, K, or Zero Survivors

A family of four problems on a sorted (or "duplicates are adjacent") array, distinguished only by how many copies you keep. All are O(n) time, O(1) space.

Keep one copy (LC 26). The slow/fast pattern in its purest form: fast scans; whenever arr[fast] differs from the last kept element, write it at slow. A cute equivalent uses a StringBuilder as an implicit stack — append the incoming element only if it differs from the current last character: if (sb.length()==0 || i != sb.charAt(sb.length()-1)) sb.append(i);. The stack framing (compare against the top) generalizes to the unsorted variant below.

Keep k copies (LC 80, k = 2). The generalization is beautiful: start slow = k, and for each fast, keep the element only if it differs from the element k positions back in the already-written prefix. That single comparison guarantees no value appears more than k times.

public int dedup(int[] arr, int k) {
    if (arr == null || arr.length <= k) return arr == null ? 0 : arr.length;
    int slow = k;
    for (int fast = k; fast < arr.length; fast++) {
        if (arr[slow - k] != arr[fast]) {   // differs from element k slots back → safe to keep
            arr[slow++] = arr[fast];
        }
    }
    return slow;   // new logical length
}

Keep zero copies (remove every value that ever repeats). Two routes: build a frequency map / freq[] and emit only the singletons, or run a two-pointer scan carrying a "did this run repeat?" flag so you skip an entire duplicated run rather than a single element.

Unsorted, remove adjacent duplicates recursively (LC 1047 family). Given a b b b c c a d e e, collapsing adjacent equal runs once yields a a d, which itself has a new adjacent pair (a a) that must also collapse. The clean model is a stack (compare with the top and pop on a match), which resolves the cascading collapses in one pass — the recursion in the notes is that same stack, made implicit.

Partitioning: Move Zeroes & the Dutch National Flag

Move Zeroes (LC 283) keeps every non-zero in its original order and pushes all zeros to one side — a textbook stable slow/fast job. Let fast sprint; whenever it lands on a non-zero, write it to slow and advance both; then fill the tail with zeros. Because you only ever overwrite positions you have already read, order is preserved and it is a single O(n) pass.

Sort Colors / rainbow sort (LC 75) is the marquee problem: an array of only 0/1/2, sort it in one pass. You could counting-sort in O(n) with two passes when the value set is tiny and known — but the elegant answer is the Dutch National Flag three-way partition: three pointers i, j, k maintain four regions.

public void sortColors(int[] arr) {
    int i = 0, j = 0, k = arr.length - 1;
    // [0,i) = 0s   [i,j) = 1s   [j,k] = unseen   (k,end] = 2s
    while (j <= k) {
        if (arr[j] == 0) {
            swap(arr, i++, j++);   // grow the 0-region, 1-region shifts right
        } else if (arr[j] == 1) {
            j++;                    // already in place
        } else {
            swap(arr, j, k--);      // send 2 to the back; DON'T advance j — swapped-in value is unseen
        }
    }
}
private void swap(int[] a, int x, int y) { int t = a[x]; a[x] = a[y]; a[y] = t; }

The one line interviewers watch for: after swapping a 2 to the back you do not advance j, because the value you just pulled from position k is still unseen and must be classified next round. This is not a toy — it is exactly the 3-way partition that makes quicksort robust against duplicate keys (see Session 2 on sorting). And the generalization is neat: to sort three values you add a pointer; to sort them with only two-value logic, treat 1 and 2 as "not 0," partition once into (0 | 12), then partition the 12 tail again.

Binary Reduction: Winning on Fewest Comparisons

A cluster of problems that never ask for the answer — everyone can find it — but for the answer with the fewest comparisons. The unifying idea is a tournament tree: pit elements pairwise and reuse the results.

Max and min together. The naive "king of the hill" scan costs up to 2n comparisons. The trick: process elements in pairs — compare the pair first (1 comparison), then the larger against the running max and the smaller against the running min (2 more). That is 3 comparisons per 2 elements, so 3n/2 total. (A subtlety from the notes: when you update one extreme you often skip the other, so the truly naive version already beats 2n in practice — but pairing makes the 3n/2 bound guaranteed.)

Sum n numbers with the fewest + operations is the same shape and the answer is unavoidable: any strategy — sequential or pairwise tree — needs exactly n − 1 additions. It is a nice sanity check that binary reduction does not always help.

Largest and second-largest. Here reduction shines. Run a knockout tournament: the champion is the maximum, and the runner-up can only be someone who lost directly to the champion. Building the bracket costs n − 1 comparisons; the champion beat ⌈log n⌉ opponents along the way, so the second-largest is the max of those — another ⌈log n⌉ − 1 comparisons. Total n − 1 + ⌈log n⌉, far below the naive 2n.

The 25 horses puzzle is the same principle dressed as a brain-teaser: 25 horses, a track that races 5 at a time, no timer — find the top 3 in the fewest races. Race the 5 groups of 5 (5 races), then race the 5 group-winners (race 6) to get the overall champion and to rank the groups. Now prune ruthlessly: only horses that could still be 2nd or 3rd survive, which leaves a small triangle of candidates, and one final race (race 7) settles 2nd and 3rd. 7 races — the answer is a direct application of "top-m in each group are the only candidates for global top-m."

Matrix Traversal: Spiral Print & Rotate

Spiral order (LC 54) and Rotate Image (LC 48) are both exercises in index bookkeeping on shrinking squares. For spiral, define each ring by a top-left corner (offset) plus a size; walk the four edges, then recurse or loop inward with offset + 1 and size - 2 until the size drops below 1.

Rotate 90° clockwise in place has three well-known solutions, and the cleanest is transpose, then reflect:

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 1) transpose across the main diagonal
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    // 2) reflect each row horizontally → clockwise 90°
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = tmp;
        }
    }
}

Two O(n²) passes, O(1) extra space, and almost impossible to get wrong. The alternatives are worth knowing out loud: a layer-by-layer 4-way corner swap that rotates each ring's four cells in one shot (derive it from the coordinate map [r,c] → [c, n-1-r]), and doing it purely by chasing those coordinate transforms. For the follow-ups: 180° is just a vertical flip followed by a horizontal flip (or transpose+reflect twice), and a non-square rectangle cannot rotate in place — the output has swapped dimensions, so you need a fresh matrix and track two sizes.

Custom Ordering: Comparators That Do the Work

Three problems where the entire difficulty is defining the right order, then letting Arrays.sort or a bucket do the rest.

Custom Sort String (LC 791) — sort characters of s by their priority in a pattern string, with everything not in the pattern going last (in normal order). A comparator handles three cases: both characters in the pattern (compare by pattern index), exactly one in the pattern (the pattern one ranks first), neither (natural order). But the O(n) answer skips comparison sorting entirely: bucket / counting sort — tally character frequencies, emit pattern characters in pattern order, then emit the rest.

Sort by first/last occurrence order — reorder 2 1 3 5 7 2 9 7 2 6 so equal values cluster in the order they first appear (2 2 2 1 3 5 7 7 9 6). Build a HashMap from value to its first-seen index (a one-to-one "pattern," same as the comparator trick above), or observe that "group equal things together while preserving order" is structurally the Move-Zeroes two-pointer pattern applied per value.

Largest Number (LC 179) — arrange non-negative integers so their concatenation is the largest possible number ([3,30,34,5,9] → 9534330). The insight is a pairwise comparator: for two numbers a and b, order them by comparing the strings a+b and b+a, not the numbers themselves — "9"+"34" beats "34"+"9".

public String largestNumber(int[] nums) {
    if (nums == null || nums.length == 0) return "";
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);

    // b+a before a+b ⇒ descending by concatenation
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

    if (strs[0].charAt(0) == '0') return "0";   // all zeros → "0", not "000"
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s);
    return sb.toString();
}

Don't miss the leading-zero edge case: if the largest arrangement starts with '0', every element was zero and the answer is "0", not a string of zeros.

Merge K Sorted Sequences & External Sort

Merge k sorted arrays is the classic, and its three solutions map cleanly to a complexity/space tradeoff. Always clarify first: sorted ascending? element type? duplicates? sizes? resources (is this really a big-data / parallel question)?

• Pairwise merge (merge-two, log k levels). Merge arrays two at a time up a binary tree. There are k−1 merges total, but the useful accounting is by level: each of the log k levels touches all kn elements, so O(kn·log k) time, O(kn) space.
• k pointers, naive. Keep a pointer per array and repeatedly take the smallest. Finding the min among k costs k, done kn times → O(k²n). The k-way min is the bottleneck.
• Min-heap of size k. Replace the linear min-scan with a heap: O(nk·log k) time, O(k) space. The catch every interviewer probes — when you pop the smallest, which array does it belong to? A bare HashMap<value, arrayIndex> fails on duplicate values, so wrap each entry in a small class carrying {value, arrayIndex, indexInArray} and order the heap by value.

Merge k sorted linked lists (LC 23) is the same heap idea with pointers doing the bookkeeping for free — a ListNode already knows its next, so no wrapper is needed. Seed the priority queue with every list head, then repeatedly poll the smallest node, append it, and push its successor. See Session 6 for the heap mechanics.

External sort (the "sort 100 GB with 1 GB RAM and two 120 GB disks" question) is merge-k applied to the physical world. A single core rules out parallelism, so: divide the 100 GB into ~1000 chunks of ~100 MB, sort each in memory, write them back as sorted runs, then do a k-way merge of the 1000 runs. Model it as k·n = 100 GB; memory usage is roughly max(k, n), minimized near √(100 GB). The dominant cost is k·n·(log n + log k) = 100 GB · log(100 GB) — the number of runs barely matters. Know the I/O hierarchy that makes this necessary (spinning disk ~50 MB/s, SSD ~500 MB/s, memory ~10 GB/s), and note that with multiple machines this becomes textbook map-reduce.

The k-Sum Ladder: 2Sum → 3Sum → kSum

2Sum (LC 1) starts with a clarifying question that changes the whole solution: return indices, values, or just a boolean? And is the array sorted?

• Sorted → two pointers from both ends, moving in based on the sum vs target: O(n) time, O(1) space.
• Sorted → binary search the complement of each element: O(n·log n).
• Unsorted → brute force O(n²) (which generalizes to DFS/combination-sum when any count of numbers is allowed), sort then two-pointer, or the one-pass HashMap of seen values → O(n).

When duplicates are allowed, ask the interviewer what "an answer" means before coding — it silently changes the dedup logic.

3Sum (LC 15) is the template for the whole ladder: fix the first element, then run 2Sum on the rest. Sort first, so the inner two-pointer is O(n) and duplicate triplets are easy to skip.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // skip duplicate anchors
        int lo = i + 1, hi = nums.length - 1, need = -nums[i];
        while (lo < hi) {
            if (nums[lo] + nums[hi] == need) {
                ans.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++;   // skip dup lows
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;   // skip dup highs
                lo++; hi--;
            } else if (nums[lo] + nums[hi] < need) {
                lo++;
            } else {
                hi--;
            }
        }
    }
    return ans;
}

4Sum (LC 18) follows by induction: fix two elements with a double loop, then 2Sum the remainder → O(n³), down from the naive O(n⁴). There is a tempting "compute all pair-sums, sort, then 2Sum on the pair-sums" idea, but it is not recommended — sorting the n² pair-sums costs O(n²·log(n²)) and, worse, you must dedup elements reused across a pair (does 3+5 reuse the same index twice?). kSum generalizes the recursion: peel off one fixed element per level down to a base-case 2Sum, turning O(nᵏ) into O(n^(k−1)).

Intersection of Sorted Arrays

Common elements in two arrays (LC 349 / 350). Clarify the usual five (sorted? order? duplicates? sizes? resource limits?) then choose:

• Both sorted → two pointers, advancing whichever is smaller, stopping when either runs out: O(m + n).
• One much smaller → binary search each of the m elements in the larger array: O(m·log n). Since m + n = m(1 + n/m), this wins over two-pointer exactly when 1 + n/m < log n, i.e. when one array dwarfs the other.
• Unsorted → sort the shorter one ((m+n)·log m beats (m+n)·log n when m < n) or drop the shorter into a HashSet and stream the other → O(m + n), with the smaller array chosen to minimize space.

Three sorted arrays extends to three pointers, advancing the smallest, O(m + n + p) — strictly better than running two-common twice. K sorted arrays is where it gets interesting: k pointers, "advance the smallest," but now finding the smallest among k grows costly, so use a min-heap (O(log k) per step) — again with a wrapper so you know which array each value came from. An element is in the intersection when all k pointers agree; since a heap only exposes the minimum, keep a running global max (which only ever increases) and declare a hit when min == max. Alternatively, pairwise "two-common" k−1 times, sorting arrays by length so an emptied intersection lets you stop early — worst case O(2kn). When sizes are wildly unequal, binary-search the small array's elements in the big ones. For duplicates in any of these, either while-loop past equal runs or dump results into a set.

Order Statistics on Two Sorted Arrays & Streams

k-th smallest of two sorted arrays. You can merge until you have counted k elements (O(k)), but you don't need to physically merge — since each merge step just advances the smaller pointer, k advances suffice.

Median of two sorted arrays (LC 4) pushes this to O(log(min(m, n))) by binary reduction. Reframe median as "find the k-th smallest," then at each step compare the k/2-th candidate of each array: the array with the smaller k/2-th element cannot contain the k-th overall in its first k/2 slots, so discard them and halve k.

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    int left = (total + 1) / 2, right = (total + 2) / 2;   // +1/+2 handles odd/even (kth, not index)
    return (getKth(nums1, 0, nums2, 0, left)
          + getKth(nums1, 0, nums2, 0, right)) / 2.0;
}

private double getKth(int[] a, int i, int[] b, int j, int k) {
    if (i >= a.length) return b[j + k - 1];   // a exhausted
    if (j >= b.length) return a[i + k - 1];   // b exhausted
    if (k == 1) return Math.min(a[i], b[j]);

    int aMid = i + k / 2 - 1 < a.length ? a[i + k / 2 - 1] : Integer.MAX_VALUE;
    int bMid = j + k / 2 - 1 < b.length ? b[j + k / 2 - 1] : Integer.MAX_VALUE;

    return aMid < bMid
        ? getKth(a, i + k / 2, b, j, k - k / 2)   // drop a's first k/2
        : getKth(a, i, b, j + k / 2, k - k / 2);
}

The corner cases are the whole problem: an array shorter than k/2 (guard with Integer.MAX_VALUE so that array is never the one discarded), an exhausted array, and the parity handled by taking both the left-th and right-th and averaging (with k − k/2 so odd totals stay correct). If either array has just one element, a plain binary search for its insertion point is simpler than the general recursion.

Median from a data stream (LC 295) flips the setup: numbers arrive one at a time and you must report the median in O(1) at any moment. Keep two heaps splitting the data in half — a max-heap lo for the smaller half, a min-heap hi for the larger. To use one PriorityQueue type for both, store negated values in lo. Rebalance so sizes differ by at most one; the median is the top of the larger heap, or the average of both tops. Its honest limitation, from the notes: if the stream is so long the heaps won't fit in memory, this breaks — but if the value domain is bounded (say 0–9), fall back to counting sort with a running total, or store cumulative counts so you can binary-search the median position.

Max product of three (LC 628) is a bite-sized order-statistics puzzle: with negatives in play, the answer is either the three largest, or the two smallest (most negative) times the single largest. Sort, or track those five extremes with a pair of heaps / a TreeSet — a min-heap holding the large values and a max-heap holding the small ones.

Sliding Window Maximum: The O(n) That Looks Like O(nk)

LC 239 — a window of size k slides across the array; report the maximum in each of the n − k + 1 positions. The naive answer rescans each window for its max: O((n − k + 1)·k). Swapping the scan for a max-heap gets you O((n − k + 1)·log k) but hits a wall — you can't cheaply remove the element that just fell out of the window unless it happens to be on top.

The right structure is a monotonic deque of indices, kept decreasing by value, so its front is always the current window's max. Two invariants maintain it: evict indices that have slid out of the window from the front, and — the key move — before pushing a new index, pop every index from the back whose value is smaller, because a smaller-and-older element can never again be the max while the newcomer is around.

public int[] maxSlidingWindow(int[] a, int k) {
    if (a == null || k <= 0) return new int[0];
    int n = a.length, ri = 0;
    int[] res = new int[n - k + 1];
    Deque<Integer> q = new ArrayDeque<>();   // stores indices, values decreasing front→back
    for (int i = 0; i < n; i++) {
        while (!q.isEmpty() && q.peek() < i - k + 1) q.poll();        // drop out-of-window
        while (!q.isEmpty() && a[q.peekLast()] < a[i]) q.pollLast();   // drop useless smaller
        q.offer(i);
        if (i >= k - 1) res[ri++] = a[q.peek()];   // front is the window max
    }
    return res;
}

Why is this O(n) and not O(nk)? Each index is pushed once and popped at most once, so across the whole run the total work is 2n — amortized O(n). The moment that "one big value clears the deque" looks expensive is exactly the moment that buys many cheap steps afterward; that is the essence of amortized analysis. (Store indices, not values, so equal elements and window boundaries stay unambiguous.)

Problem Checklist