Arrays & Strings

Arrays and strings are among the most fundamental data structures in computer science, and manipulating them efficiently is a common focus of technical interviews.

Arrays. An array is a collection of elements stored in contiguous memory, accessed by index. This contiguous storage gives arrays fast, constant-time access to any element by its position, but inserting or removing elements (other than at the end) generally requires shifting other elements, making those operations slower.

Strings. A string is, at its core, a sequence of characters, and many string problems are really array problems in disguise, since strings are commonly implemented as arrays of characters internally.

Common array/string techniques. A few recurring patterns show up repeatedly in array and string problems: the two-pointer technique (using two indices that move through the array, often from opposite ends or at different speeds), the sliding window technique (maintaining a subrange of the array that expands or contracts based on a condition), and prefix sums (precomputing cumulative sums to answer range-sum queries efficiently).

Time and space complexity. Understanding the time complexity of common operations — accessing an element (fast), searching for a value (generally requires scanning, unless the array is sorted and binary search applies), inserting or deleting (potentially slow, depending on position) — is essential for reasoning about whether a given approach to an array or string problem will be efficient enough for the input sizes involved.

Fixed-size arrays and dynamic arrays. Many languages expose a growable list type — a dynamic array — built on top of a fixed-size array underneath. When it runs out of capacity it allocates a larger block and copies the existing elements across. Any individual append can therefore be expensive, but because capacity typically doubles, the copying cost spread across many appends works out to constant time per operation on average. This is what "amortized O(1) append" means, and it explains why appending in a loop is fine while inserting at the front repeatedly is not.

Hash maps as the companion structure. A large share of array problems that look like they need nested loops become linear once a hash map is introduced, because a map turns "have I seen this value, and where?" from an O(n) scan into an O(1) lookup. The classic example is finding two elements that sum to a target: the brute-force approach checks every pair in O(n²), while a single pass that records each value seen so far solves it in O(n). Recognizing when a repeated lookup is the bottleneck is one of the most transferable skills in this area.

In-place work versus extra space. Problems frequently specify that a transformation be done in place, meaning with only a constant amount of additional memory rather than by building a new array. In-place solutions typically rely on swapping elements or on a write pointer that trails a read pointer, overwriting the array as it is consumed. The trade-off is real: in-place work saves memory but destroys the original input and is usually harder to reason about, so it is worth asking whether the constraint is actually required before paying for it.

String immutability and the cost of building. In many languages strings are immutable, so every concatenation creates a new string and copies the existing characters. Building a long string by repeated concatenation inside a loop is therefore quadratic in the length of the result — a common and easily missed performance bug. The standard remedy is to accumulate the pieces in a list and join them once at the end, or to use the language's dedicated builder type. Knowing whether your language's strings are mutable is the prerequisite for reasoning about any string-heavy loop.

Sorting as a preprocessing step. Sorting costs O(n log n), which is often worth paying because it makes the rest of the problem much easier: duplicates become adjacent, binary search becomes available, and the two-pointer technique from opposite ends becomes valid. If a problem's brute-force solution is O(n²) and the underlying difficulty is comparing every element to every other, sorting first is one of the first alternatives to consider. The cost is that sorting destroys the original ordering, which matters when the answer must be expressed in terms of original indices.

Edge cases that decide correctness. Array and string problems fail on their boundaries far more often than on their main logic. The recurring cases are the empty input, a single element, all elements identical, already-sorted and reverse-sorted input, and values at the extremes of the allowed range. Off-by-one errors in loop bounds and window boundaries are the single most common defect in this area, which is why walking through a small concrete example by hand — rather than reasoning about the code abstractly — is the fastest way to catch them.

How to approach these problems. A reliable sequence is: restate the problem and confirm the constraints, describe the brute-force solution and state its complexity, identify what makes it wasteful, and then reach for the technique that eliminates that specific waste — a hash map for repeated lookups, two pointers or a sliding window for repeated scanning of overlapping ranges, prefix sums for repeated range queries. Stating the target complexity before writing code keeps the search for a solution directed rather than exploratory.

Mastering these fundamentals — how arrays and strings are stored, their performance characteristics, and the common techniques used to manipulate them efficiently — is foundational preparation for a large fraction of common coding interview questions.