Arrays, Strings, and Two Pointers¶

Roughly 40% of study problems live in this bucket. It’s also the friendliest bucket to solve in C — no custom containers required, just indices and pointer arithmetic. Master the four templates in this file and you’ve secured the largest slice of the problem space with the least infrastructure.

The Four Templates¶

Template 1: Two Pointers (Opposite Ends)¶

Works on sorted arrays or when the invariant lets you converge from both sides.

int left = 0, right = n - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return /* pair found */;
    else if (sum < target) left++;
    else right--;
}

Uses: Two Sum II (sorted), Container With Most Water, 3Sum (with sorting + outer loop), Valid Palindrome, Trapping Rain Water (two-pointer variant).

Template 2: Two Pointers (Same Direction / Fast-Slow)¶

Typically used for in-place mutation of an array.

int write = 0;
for (int read = 0; read < n; read++) {
    if (/* keep arr[read] */) {
        arr[write++] = arr[read];
    }
}
// new length is `write`

Uses: Remove Duplicates from Sorted Array, Move Zeroes, Remove Element. Also the pattern behind Floyd cycle detection on linked lists.

Template 3: Sliding Window (Variable Size)¶

The pattern behind roughly a third of “substring” and “subarray” problems.

int left = 0;
/* running state: counts, sum, etc. */
int best = 0;
for (int right = 0; right < n; right++) {
    /* add arr[right] to state */

    while (/* window violates constraint */) {
        /* remove arr[left] from state */
        left++;
    }

    /* window [left..right] is valid; update best */
    if (right - left + 1 > best) best = right - left + 1;
}
return best;

Uses: Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Repeating Character Replacement, Permutation in String, Sliding Window Maximum (variant with a deque).

The insight: the window slides monotonically. left only ever moves right; right only ever moves right. Total work is O(n), not O(n²), even though there are nested loops — the inner while amortizes.

Template 4: Prefix Sum¶

Turns “sum of any subarray” from O(n) per query to O(1) after O(n) preprocessing.

int prefix[n + 1];
prefix[0] = 0;
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
// sum of arr[l..r] inclusive = prefix[r+1] - prefix[l]

Combined with a hashmap {prefix_value -> earliest_index}, this pattern solves the “count subarrays whose sum equals K” family in O(n).

Uses: Subarray Sum Equals K, Range Sum Query - Immutable, Continuous Subarray Sum.

In-Place Reversal¶

Since you’re going to reverse arrays and substrings a lot, memorize the two-line template:

void reverse(int *arr, int i, int j) {
    while (i < j) {
        int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        i++; j--;
    }
}

The trick problems (Rotate Array, Reverse Words in String) reduce to “reverse three subranges.”

Strings: The C-Specific Landmines¶

Strings in C are char* to a null-terminated char[]. Everything you’d like to be automatic is manual.

`char[]` vs `char*` — The Modification Trap¶

char *s1 = "hello";       // s1 points to a string LITERAL in rodata; DO NOT modify
s1[0] = 'H';              // UNDEFINED BEHAVIOR (usually SIGSEGV)

char s2[] = "hello";      // s2 is an ARRAY on the stack, initialized by copy
s2[0] = 'H';              // fine, s2 is now "Hello"

This distinction bites people every week. LeetCode problem signatures usually give you char* that IS modifiable (they allocate it for you), but always check. Rule of thumb: if you got the pointer from a literal, don’t write through it; if you got it from malloc/calloc/an array declaration, do.

The `strncmp` / `strncpy` / `snprintf` Rule¶

Never use strcmp, strcpy, sprintf, or strcat in study code. They have no bounds checking. Use strncmp, strncpy, snprintf, strncat — the n versions — always. The overhead in code length is trivial; the safety gain is huge.

if (strncmp(a, b, 5) == 0) { /* first 5 chars match */ }
snprintf(buf, sizeof buf, "count=%d", n);   // always fits

One footgun: strncpy does not null-terminate if the source is longer than n. Always follow with buf[n-1] = '\0'; or use snprintf if you want a real string.

Char Frequency: The 26-Element Array¶

For problems on lowercase English letters, the hashmap is literally an int[26]:

int counts[26] = {0};
for (int i = 0; s[i]; i++) counts[s[i] - 'a']++;

O(1) space, faster than any hashmap, cache-friendly. Use this whenever the alphabet is bounded. For arbitrary bytes, use int[256]; for Unicode, break out uthash.

The Anagram Trick¶

Two strings are anagrams iff their sorted forms are equal, OR their character-count arrays are equal. The count-array version is O(n); sorting is O(n log n). In C, count arrays are one line each and memcmp compares them:

int ca[26] = {0}, cb[26] = {0};
for (int i = 0; a[i]; i++) ca[a[i]-'a']++;
for (int i = 0; b[i]; i++) cb[b[i]-'a']++;
return memcmp(ca, cb, sizeof ca) == 0;

One line, no allocations, cache-friendly. This is why C in the string-frequency subproblems is genuinely fun.

Integer Overflow Even Here¶

Even “just arrays and strings” problems can overflow int. The classic: “maximum subarray product” — the running product can exceed INT_MAX even when the answer fits. When in doubt, use long long. See 09_c_specific_pitfalls_in_interviews.md.

Signed vs Unsigned Index¶

Use int when the loop index might legitimately go negative (backwards iteration, two-pointer opposite-ends, binary search left = mid - 1 when mid == 0). Use size_t when it can’t. Never use size_t for a loop that decrements past zero:

for (size_t i = n - 1; i >= 0; i--)   // INFINITE LOOP: size_t wraps to SIZE_MAX

Fix with for (size_t i = n; i-- > 0; ) or just use int. In studies, prefer int unless you have a reason.

What Most People Get Wrong About This¶

They memorize sliding window as “a while inside a for” without internalizing that left only moves right. When they see a two-pointer problem where the right pointer might reset, they try to force sliding window and get O(n²). The pattern is not “nested loop”; it’s “monotonic pointers with amortized linear scan.” If your problem doesn’t have the monotonic property, sliding window is wrong — look elsewhere.

Return to README.md · Next: 03_linked_lists_from_scratch.md