Arrays and Strings — Deep¶

Arrays and strings are 40% of coding-round problems. Not because they’re the hardest topics — because they show up in every screen, phone screen, and warmup. You want the four core patterns (two-pointer, sliding window, prefix sums, Kadane) so cached that identifying the pattern happens before you finish reading the problem.

Java has its own array/string idioms that matter for performance: String immutability, StringBuilder for concatenation loops, char[] for in-place manipulation, System.arraycopy for bulk moves. These are the differences between a solution that passes and one that TLEs.

1. Java-specific: `String` vs `StringBuilder` vs `char[]`¶

String is immutable. Every += creates a new object. In a loop, this is O(n²):

// O(n^2) — do not do this in a loop
String s = "";
for (int i = 0; i < n; i++) s += arr[i];

StringBuilder is a mutable backing char[] with amortized O(1) append. Use it for any string built in a loop.

StringBuilder sb = new StringBuilder(n);   // pre-size when you know n
for (int i = 0; i < n; i++) sb.append(arr[i]);
return sb.toString();

char[] is what you reach for when you need in-place character manipulation (reverse a string, swap chars, sort chars):

char[] a = s.toCharArray();
int i = 0, j = a.length - 1;
while (i < j) { char t = a[i]; a[i++] = a[j]; a[j--] = t; }
return new String(a);

⚠️ What most people get wrong¶

They use StringBuilder when the compiler was already going to. For flat concatenation ("a" + b + "c"), the compiler compiles to a single StringBuilder under the hood. Loops are the only place manual StringBuilder matters. Over-StringBuilder-ing hurts readability with zero perf gain.

Also: StringBuffer is StringBuilder’s synchronized older sibling. Never use StringBuffer unless multiple threads write to the same buffer, which is essentially never. Same-name-different-letter mistake shows up in old code.

`String` API you should know cold¶

Method	Returns	Notes
`s.length()`	`int`	Yes, method, not field
`s.charAt(i)`	`char`	Bounds-checked
`s.substring(i)` / `s.substring(i,j)`	`String`	`j` exclusive; Java 7+ actually copies (no shared backing array)
`s.indexOf(c)`, `s.lastIndexOf(c)`	`int`	-1 if not found
`s.contains(cs)`	`boolean`
`s.startsWith`, `s.endsWith`	`boolean`
`s.split(regex)`	`String[]`	Regex, not literal; escape `.` `
`s.replace(target, replacement)`	`String`	Literal replace
`s.replaceAll(regex, repl)`	`String`	Regex-based
`s.strip()` / `s.trim()`	`String`	`strip` is Unicode-aware (Java 11+); prefer it
`s.chars()`	`IntStream`	Stream of UTF-16 code units as int
`s.codePoints()`	`IntStream`	Actual Unicode code points (handles surrogate pairs)

2. Array utilities you should not re-implement¶

Arrays.sort(arr);                             // dual-pivot quicksort for primitives
Arrays.sort(objArr);                          // TimSort for objects
Arrays.sort(objArr, comparator);              // TimSort with custom order
Arrays.sort(arr, from, to);                   // sort a range

Arrays.fill(arr, 0);
Arrays.fill(arr, from, to, 0);

int[] copy   = Arrays.copyOf(arr, newLen);           // pad with 0 if newLen > arr.length
int[] slice  = Arrays.copyOfRange(arr, from, to);    // [from, to)

System.arraycopy(src, srcPos, dst, dstPos, length);  // fastest bulk copy

int idx = Arrays.binarySearch(sortedArr, target);    // < 0 if absent; -(insertion+1)

String repr = Arrays.toString(arr);           // 1D
String rep2 = Arrays.deepToString(matrix);    // nested

System.arraycopy is a native intrinsic. Faster than any hand loop for bulk moves. Reach for it when shifting slices around (e.g. implementing ArrayList.remove).

Arrays.binarySearch return value is subtle. Positive index if found; -(insertion_point) - 1 if not. So to convert to insertion point on a miss:

int i = Arrays.binarySearch(arr, x);
if (i < 0) i = -(i + 1);   // now i is where x would go

3. Two-pointer pattern¶

Signature: sorted array / linked list / string, or a problem where you can independently move two indices.

Template — opposite ends (pair sum in sorted array):

int l = 0, r = arr.length - 1;
while (l < r) {
    int sum = arr[l] + arr[r];
    if (sum == target) return new int[]{l, r};
    if (sum < target) l++;
    else r--;
}
return new int[]{-1, -1};

Template — same direction (remove duplicates from sorted array):

int w = 0;   // write index
for (int r = 0; r < arr.length; r++) {
    if (r == 0 || arr[r] != arr[r-1]) arr[w++] = arr[r];
}
return w;   // new length

Canonical problems: Two Sum II (sorted), Container with Most Water, 3Sum, Trapping Rain Water, Remove Duplicates from Sorted Array, Sort Colors (Dutch flag).

4. Sliding window¶

Signature: contiguous subarray / substring with some constraint (“longest”, “shortest”, “count of”), variable-size window that grows and shrinks based on a condition.

Template — variable window (longest substring without repeating chars):

int[] last = new int[128];
Arrays.fill(last, -1);
int l = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
    char c = s.charAt(r);
    if (last[c] >= l) l = last[c] + 1;   // shrink from the left
    last[c] = r;
    best = Math.max(best, r - l + 1);
}
return best;

Template — fixed window (max sum of subarray of size k):

int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int best = sum;
for (int i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    best = Math.max(best, sum);
}
return best;

Canonical problems: Longest Substring Without Repeating Chars, Minimum Window Substring, Longest Repeating Character Replacement, Maximum Sum Subarray of Size K, Permutation in String, Sliding Window Maximum (uses Deque).

5. Prefix sums¶

Signature: range-sum queries, subarray-sum-equals-K, any “between i and j inclusive” question over a fixed array.

// Build once, query in O(1)
int[] p = new int[n + 1];       // p[0] = 0; p[i+1] = p[i] + arr[i]
for (int i = 0; i < n; i++) p[i+1] = p[i] + arr[i];
// range sum arr[l..r] inclusive:
int rangeSum = p[r+1] - p[l];

Subarray sum equals K (the pattern that unlocks a dozen mediums):

Map<Integer, Integer> countByPrefix = new HashMap<>();
countByPrefix.put(0, 1);        // empty prefix
int sum = 0, ans = 0;
for (int x : arr) {
    sum += x;
    ans += countByPrefix.getOrDefault(sum - k, 0);
    countByPrefix.merge(sum, 1, Integer::sum);
}
return ans;

Canonical problems: Range Sum Query - Immutable, Subarray Sum Equals K, Contiguous Array, Product of Array Except Self, Continuous Subarray Sum (mod k).

6. Kadane’s algorithm (maximum subarray)¶

Signature: “maximum sum contiguous subarray” and its cousins (max product, circular max, etc.).

int best = arr[0], cur = arr[0];
for (int i = 1; i < arr.length; i++) {
    cur = Math.max(arr[i], cur + arr[i]);   // extend or restart
    best = Math.max(best, cur);
}
return best;

That is the entire algorithm. Two lines of state, one loop, O(n) time, O(1) space. It is DP in disguise, which is why it appears in the DP file too.

Canonical problems: Maximum Subarray, Maximum Product Subarray (careful — track min and max), Best Time to Buy and Sell Stock (basically Kadane on differences), Maximum Circular Subarray Sum.

7. Sort as a preprocessing step¶

If a problem allows sorting (order not required in the answer, or you can restore it via indices), sorting first is often the shortest path.

“Any two elements summing to K” → sort + two-pointer, O(n log n).
“Group anagrams” → sort each string, use as key, O(n · k log k).
“Minimum meeting rooms” → sort by start, sweep. O(n log n).
“Merge intervals” → sort by start, walk. O(n log n).

When you need the original indices, sort a wrapper array of (value, originalIndex):

Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(idx, Comparator.comparingInt(i -> arr[i]));
// now idx[k] is the original index of the k-th smallest value

8. In-place O(1)-space tricks¶

Reverse a subarray in place: two-pointer swap. Building block for rotate-array, next-permutation, etc.
Rotate array by k (cyclic-reversal trick): reverse whole, reverse first k, reverse last n-k. O(n) time, O(1) space.
Encoding state in the sign of arr[i]: for problems on arrays of 1..n, flipping arr[abs(v) - 1] negative marks “seen”. Restore with Math.abs. (Find All Duplicates in an Array, First Missing Positive.)
Cyclic sort: for arrays containing 0..n or 1..n, swap arr[i] to its correct index in one pass. O(n), finds missings and duplicates.

9. Complexity table for the patterns above¶

Pattern	Time	Space
Two-pointer opposite ends	O(n)	O(1)
Two-pointer same direction	O(n)	O(1)
Fixed sliding window	O(n)	O(1)
Variable sliding window	O(n)	O(k) for the char table
Prefix sum build	O(n) build, O(1) query	O(n)
Prefix sum + hashmap	O(n)	O(n)
Kadane	O(n)	O(1)
Sort-then-sweep	O(n log n)	O(1) with in-place sort, else O(n)

Memorize this table. When you’re 10 minutes into a problem and unsure, look at your target complexity — it often narrows the pattern.

study-time heuristics¶

See “sorted” in the problem? Think two-pointer or binary search first.
See “contiguous subarray” or “substring”? Think sliding window or prefix sum.
See “pair” / “triple” summing to X? Think sort + two-pointer for pair; sort + fix one + two-pointer for triple.
See “maximum / minimum contiguous …”? Kadane variant.
See “in-place, O(1) space”? Think sign-flip, cyclic sort, or reverse trick.

Practice slate (from NeetCode 150)¶

Two-pointer: Valid Palindrome, Two Sum II, 3Sum, Container With Most Water, Trapping Rain Water. Sliding window: Best Time to Buy and Sell Stock, Longest Substring Without Repeating, Longest Repeating Character Replacement, Permutation in String, Minimum Window Substring, Sliding Window Maximum. Prefix sum: Subarray Sum Equals K, Contiguous Array, Product of Array Except Self. Kadane: Maximum Subarray, Maximum Product Subarray.

Do those 15 before moving to the next file. Complexity comment at top of every solution.

Return to README.md · Next: 02_linked_lists_stacks_queues.md