Array indexing and shifting
An array stores values in numbered positions. An index lets the program go directly to one position, which is why reading or replacing array[i] takes constant time.
Operations that change the length of a dynamic array are different. Appending adds a new position after the existing values, so the indices of those existing values do not change. Inserting or deleting near the front changes the positions of later values, which may force many of them to shift.
How common array operations change positions
A fixed-size array cannot grow after it is created. A dynamic array preserves indexed access while adding append and automatic resizing.
| Array and dynamic-array operation | Time | Cost source |
|---|---|---|
| Read or replace by index | O(1) | The index identifies one cell directly. |
| Append to a dynamic array | amortized O(1) | Most appends use available capacity. An occasional resize copies the array. |
| Insert near the front or middle | O(n) | Later elements may all shift right. |
| Delete near the front or middle | O(n) | Later elements may all shift left. |
One resize may copy many values, but resizing does not happen on every append. Across a long sequence of appends, the total copying is spread over all operations, giving amortized O(1) time per append.
Repeatedly removing the first item can take O(n²) total time because each removal may shift the remaining elements. Moving an index forward reads the same items in O(n) total time without shifting.
These costs explain why two-pointer solutions usually read or overwrite by index, or append to a result, instead of repeatedly inserting or deleting near the front.
n times take O(n²) total time?Practice next: Find Maximum and Count Occurrences is a required 9-minute Easy problem and contributes to course progress.
String mutation and rebuilding
Suppose a program needs to change "code" into "cade". Changing one character looks like an indexed replacement, but an immutable string cannot be changed in place. The program must produce another string containing the unchanged characters together with the replacement.
Change one character without changing the original string
Python, Java, and JavaScript strings are immutable, so the original "code" remains unchanged and the operation produces a new string. C++ std::string is mutable, although insertions near the front or middle still move later characters.
Repeatedly extending an immutable string may copy the partial result each time. When the output grows with the input, use mutable storage and build the final string once.
Language-specific choices
| Language | Mutable indexed storage | String behavior | Build a string |
|---|---|---|---|
| Python | list | immutable | list plus ''.join(...) |
| Java | array or ArrayList | String is immutable | StringBuilder |
| C++ | vector | string is mutable | string with reserved capacity when useful |
| JavaScript | Array | immutable | array plus join('') |
Building a result of length n with mutable storage takes O(n) total time when each character is appended once using amortized constant-time append. Repeated concatenation of immutable strings can take O(n²) time when each concatenation copies the growing partial result. The mutable buffer uses O(n) space for the result being built. If an interviewer asks for auxiliary space, state separately whether that required output is being counted.
When an algorithm only needs to examine a sequence, move an index instead of repeatedly changing the sequence itself. When it must build a result, appending to mutable storage is usually cheaper than inserting near the front or repeatedly rebuilding an immutable string.