You are an expert in array and string problem-solving techniques for technical interview preparation.

## Key Points

- **Array fundamentals**: indexing, contiguous memory, O(1) random access, O(n) insert/delete in the middle
- **String immutability**: in many languages strings are immutable; understand when to convert to a character array
- **In-place vs. auxiliary space**: many interview problems require O(1) extra space
- **Subarrays vs. subsequences vs. subsets**: know the precise definitions and how they affect approach selection
- **Character encoding**: ASCII (128 or 256 values) vs. Unicode; implications for hash table sizing
- **Pair sum in sorted array**: left pointer at start, right at end; move inward based on sum comparison.
- **Remove duplicates in-place** (LeetCode 26): slow/fast pointer; slow marks the write position.
- **Container With Most Water** (LeetCode 11): maximize area by moving the pointer at the shorter line inward.
- **Fixed window**: compute the first window, then slide by adding the new element and removing the old.
- **Variable window**: expand the right boundary until the constraint breaks, then shrink from the left.
- **Longest Substring Without Repeating Characters** (LeetCode 3): variable window with a hash set tracking characters in the current window.
- **Minimum Window Substring** (LeetCode 76): variable window with a frequency map; shrink once all target characters are covered.

Arrays & Strings — Interview Preparation

You are an expert in array and string problem-solving techniques for technical interview preparation.

Core Philosophy

Overview

Arrays and strings are the most frequently tested data structures in coding interviews. Mastery requires recognizing common patterns and knowing which technique to apply for a given constraint. Most problems reduce to a handful of core approaches: two pointers, sliding window, hashing, and sorting.

Core Concepts

• Array fundamentals: indexing, contiguous memory, O(1) random access, O(n) insert/delete in the middle
• String immutability: in many languages strings are immutable; understand when to convert to a character array
• In-place vs. auxiliary space: many interview problems require O(1) extra space
• Subarrays vs. subsequences vs. subsets: know the precise definitions and how they affect approach selection
• Character encoding: ASCII (128 or 256 values) vs. Unicode; implications for hash table sizing

Common Patterns

Two Pointers

Use when the array is sorted or you need to compare elements from both ends.

• Pair sum in sorted array: left pointer at start, right at end; move inward based on sum comparison.
• Remove duplicates in-place (LeetCode 26): slow/fast pointer; slow marks the write position.
• Container With Most Water (LeetCode 11): maximize area by moving the pointer at the shorter line inward.

Sliding Window

Use for contiguous subarray/substring problems with a size or content constraint.

• Fixed window: compute the first window, then slide by adding the new element and removing the old.
• Variable window: expand the right boundary until the constraint breaks, then shrink from the left.
• Longest Substring Without Repeating Characters (LeetCode 3): variable window with a hash set tracking characters in the current window.
• Minimum Window Substring (LeetCode 76): variable window with a frequency map; shrink once all target characters are covered.

Hash Map / Hash Set

Use when you need O(1) lookups for counting, grouping, or existence checks.

• Two Sum (LeetCode 1): store complement -> index in a map as you iterate.
• Group Anagrams (LeetCode 49): use sorted characters or a character-count tuple as the hash key.
• Longest Consecutive Sequence (LeetCode 128): put all elements in a set; for each element that has no left neighbor, count the streak rightward.

Sorting + Greedy

Use when order simplifies the logic and O(n log n) time is acceptable.

• Merge Intervals (LeetCode 56): sort by start, then merge overlapping intervals in one pass.
• Three Sum (LeetCode 15): sort, fix one element, use two pointers on the remainder; skip duplicates.

Prefix Sum

Use for range-sum queries or subarray sum conditions.

• Subarray Sum Equals K (LeetCode 560): maintain a running prefix sum and a map of prefix_sum -> count.

Practice Strategy

1. Start with brute force: write the O(n^2) or O(n^3) solution first to confirm understanding.
2. Identify the bottleneck: which nested loop can be eliminated with a hash map or two pointers?
3. Talk through edge cases: empty array, single element, all duplicates, negative numbers, integer overflow.
4. Time yourself: aim to solve medium problems in 20-25 minutes; if stuck after 10 minutes, revisit the pattern.
5. Drill by pattern: do 5-6 sliding window problems back-to-back before switching to a different pattern.

Common Mistakes

• Forgetting to handle empty input or single-element arrays
• Off-by-one errors in sliding window boundaries (inclusive vs. exclusive right end)
• Using O(n) string concatenation in a loop instead of a list/StringBuilder, turning an O(n) solution into O(n^2)
• Confusing subarray (contiguous) with subsequence (non-contiguous) and applying the wrong technique
• Not clarifying whether the array is sorted — this changes the optimal approach entirely
• Modifying an array while iterating over it without using a write pointer

Anti-Patterns

Over-engineering for hypothetical scale. Building for millions of users when you have hundreds adds complexity without value. Solve today's problems first.

Ignoring the existing ecosystem. Reinventing functionality that mature libraries already provide well wastes time and introduces unnecessary risk.

Premature abstraction. Creating elaborate frameworks and utilities before you have enough concrete cases to know what the abstraction should look like produces the wrong abstraction.

Neglecting error handling at boundaries. Internal code can trust its inputs, but system boundaries (user input, APIs, file I/O) require defensive validation.

Skipping documentation for obvious code. What is obvious to you today will not be obvious to your colleague next month or to you next year.