Arrays and Strings

Memory basics

• An integer takes 4 bytes, a character 1 byte, and a byte is 8 bits.
• Arrays store values in contiguous memory locations, which is what makes index access $O(1)$.
• A one-dimensional array is accessed with a single index. A two-dimensional array is a table of $m$ rows and $n$ columns ($m\times n$).
• Indexing starts at 0.

Static arrays

• Fixed-size, contiguous block of memory. (Fixed size is not a concern in Python or JavaScript.)
• Values are “deleted” by overwriting them (for example with 0) and tracking a separate length.

Dynamic arrays

• Same complexities as static arrays; push / pop at the end is $O(1)$.
• When the array runs out of space, a larger block is allocated, elements are copied, and the old block is deallocated. This is rare, so pushing is $O(1)$ amortized.

Arrays vs linked lists

Prefix sum

Preprocess the array so that prefix[i] holds the sum of the elements before index i. Any subarray sum then becomes a subtraction.

• Use it for many sum queries on subarrays and for cumulative sums.
• Build: $O(n)$. Each query: $O(1)$.

prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
 
# sum of nums[l..r] inclusive
range_sum = prefix[r + 1] - prefix[l]

Two pointers

See Two Pointers.

Recognition signals

• Sorted (or sortable) array or string
• Finding pairs or triplets with a specific sum
• Partitioning elements (zeros vs non-zeros) or in-place modification
• Comparing from both ends; palindromes; subsequence checks

Main patterns

• Opposite direction (converging): start at both ends and move inward based on a comparison. Palindrome check, container problems, sorted pair sum.
• Same direction (slow-fast): the fast pointer finds elements, the slow pointer tracks where to place them. In-place removal of duplicates, subsequence matching.
• Fixed distance: keep a constant gap between pointers. Sliding window variants, k-distance problems.
• Anchor + runner: one pointer fixed, the other explores from it. 3Sum (fix one, two pointers on the rest), subarrays with constraints.

Checklist and gotchas

1. Sort first if needed; $O(n\log n)$ is often acceptable. If the input is already sorted, that is a hint for two pointers.
2. Define pointer positions and movement rules.
3. Choose while L < R vs L <= R carefully (is the equal case valid?).
4. Skip duplicates AFTER recording a valid result, otherwise valid answers can be skipped. Use a while loop to skip when unique results are required.
5. For triplets / k-sum, fix the outer pointer(s) and run two pointers on the remainder.
6. Check L+1 / R-1 exist before accessing them; break early when the first element is already greater than the target (sorted ascending).
7. Update the result before or after moving a pointer deliberately; order matters.
8. Check whether the answer needs 0-indexed or 1-indexed positions.
9. Two passes over the array is still $O(n)$ (written $O(2n)$).

Sliding window

Use for contiguous elements: subarray, substring, consecutive, “at most K”, anagram, permutation. See Fixed Size and Variable Size.

Main patterns

1. Fixed window (size k): build a window of k elements, then slide by adding one on the right and removing one on the left. Start processing when R >= k - 1.
2. Maximum length window: always expand right, shrink left only when invalid. Update after the window is valid: max_len = max(max_len, R - L + 1).
3. Minimum length window: expand right until valid. While valid, update min_len and then shrink left (update during shrinking).
4. Optimize a value (profit, swaps, sum): track the best value seen so far; greedily jump L to R when a better start is found, or reset when continuing hurts (negative sum).
5. Pattern matching (anagram / permutation): fixed window of pattern length; keep a match counter instead of comparing whole maps ($O(1)$ vs $O(26)$).

Tracking techniques

• Frequencies: hash map (delete the key when its count reaches 0).
• Pattern match: match counter for $O(1)$ comparison.
• Min / max in window: monotonic deque of indices.
• Valid replacements: window_length - max_freq <= k.
• Circular arrays: iterate $2N$ with modulo indexing.

Hash map operation order

• Adding to the window: increment the frequency, then check whether it equals the target.
• Removing from the window: check whether it equals the target, then decrement the frequency.
• The match counter is incremented after adding and decremented before removing.

Gotchas

• Window length is R - L + 1, not R - L.
• Fixed window starts at R >= k - 1, not R >= k.
• Max problems: update after the window is valid. Min problems: update while it is valid.

Kadane’s algorithm

See Kadane’s Algorithm. Finds the maximum subarray sum in $O(n)$; it is a greedy / sliding-window hybrid.

• Keep maxSum and curSum.
• For each element, decide whether it is better to start a new subarray with just this element (num) or extend the existing one (curSum + num): curSum = max(num, curSum + num).
• Equivalently, keep growing the window until its sum becomes negative, then reset curSum to 0. A negative prefix can only drag down whatever comes after it.
• After each step, maxSum = max(maxSum, curSum).

Intervals

Whether to sort by start or end time depends on the goal.

When merging, start with an empty result list and compare each interval with the last one appended.

Fast and slow pointers, in-place reversal

These are linked-list techniques (cycle detection, finding the middle, reversing a section) and are not covered by a template here. In an odd-length list the slow pointer ends on the exact middle; in an even-length list it ends on the first node of the second half.

Templates

• Static Arrays: fixed-capacity array with insert / remove at the end and in the middle.
• Dynamic Arrays: resizable array with amortized $O(1)$ push.
• Two Pointers: palindrome check and sorted two-sum with converging pointers.
• Sliding Window (Fixed Size): window of constant size k.
• Sliding Window (Variable Size): longest / shortest window satisfying a condition.
• Kadane’s Algorithm: maximum subarray sum, including the sliding-window variant that returns indices.

Problems