Arrays and Strings
On this page
Most interview problems hand you an array or a string, and most slow solutions come from treating them as if every operation were free. Inserting at the front of a list of a million items, or building a string one character at a time, can quietly turn an O(n) idea into O(n²). Knowing what arrays are fast and slow at is the first step to every pattern in this track.
How it works
One block of memory
![Because elements sit side by side, the address of any index is computed directly, so reading a[i] is O(1).](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-2dad054a.png)
An array stores its elements next to each other in one block of memory. If the block starts at address 1000 and each element takes 4 bytes, element i lives at 1000 + i × 4. The computer doesn't search for it; it computes the position. That's why reading or writing a[i] is O(1), and why scanning an array front to back is very fast in practice: the next element is already in the CPU cache.
Dynamic arrays grow by doubling
A Python list, Java ArrayList, C++ vector and Go slice all wrap a fixed block. When the block is full, they allocate a new one about twice as large and copy everything across. The copy is O(n), but it happens so rarely that appending stays O(1) amortized.
Inserting in the middle shifts the rest

There are no gaps in an array. To insert at index i, every element from i onward moves one slot right; deleting moves them left. Near the end that's cheap, at the front it costs O(n).
Strings are arrays of characters
A string is an array of characters, with one twist: in Python, Java, Go and JavaScript strings are immutable. Every "change" creates a new string and copies the characters. C++ std::string is mutable.

Operations and costs
| Operation | Cost | Note |
|---|---|---|
Read or write a[i] | O(1) | position is computed |
| Append at the end | O(1) amortized | occasional O(n) resize |
| Insert or delete at the end | O(1) | pop() |
| Insert or delete at index i | O(n − i) | shifts the rest |
| Search for a value (unsorted) | O(n) | scan |
| Search for a value (sorted) | O(log n) | binary search |
| Slice or copy k elements | O(k) | slices copy in Python and Java |
| Sort | O(n log n) |
When to reach for it
Arrays are the default container. Reach for something else only when an operation you need is slow on an array:
- Many lookups by value? Add a hash map or set next to the array.
- Many inserts or deletes at the front? Use a deque (double-ended queue).
- Repeatedly need the smallest or largest? Use a heap.
Some techniques work on arrays specifically because indexing is O(1):
- Two pointers from both ends, or a slow and a fast pointer (reverse, partition, remove duplicates in place).
- Sliding window over a contiguous range.
- Prefix sums: precompute running totals so any range sum is one subtraction.
- Binary search on sorted data.
- Counting arrays: when values are small (26 lowercase letters, digits), an array of counters beats a hash map.
Example
Reverse an array in place using two pointers that walk toward each other. This is the building block for reversing a string, checking a palindrome and rotating an array.
def reverse_in_place(a):
i, j = 0, len(a) - 1
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
return a
void reverseInPlace(int[] a) {
int i = 0, j = a.length - 1;
while (i < j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
void reverseInPlace(vector<int>& a) {
int i = 0, j = (int)a.size() - 1;
while (i < j) {
swap(a[i], a[j]);
i++;
j--;
}
}
func reverseInPlace(a []int) {
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
}
Time: O(n), each element is touched once. Space: O(1) extra.
A second example shows the string-building rule. Compress runs of the same character, so "aaabcc" becomes "a3b1c2":
def compress(s):
parts, i = [], 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
parts.append(s[i] + str(j - i))
i = j
return "".join(parts)
The inner loop looks like it makes this O(n²), but i jumps to j after each run, so every character is visited once: O(n) time. In Java use a StringBuilder, in Go a strings.Builder, in C++ append to a std::string (it is mutable).
Common mistakes
- Off-by-one at the ends. Decide whether your range is
[lo, hi]or[lo, hi)and keep it consistent. Most bugs in array code are here. - Modifying a list while looping over it. Removing items inside a
forloop skips elements. Loop over a copy, loop backwards, or build a new list. - Hidden O(n) calls.
list.insert(0, x),list.pop(0),x in listand slicing are all O(n) in Python. - String concatenation in a loop. Use a list and
join, or a builder. - Forgetting that strings are immutable. In Python and Java you can't assign
s[i] = 'x'; convert to a list or char array first. - Ignoring the empty input.
len(a) - 1is −1 for an empty array; make sure your loop conditions handle it.
Say this in the interview
- "Reading by index is O(1), but inserting at the front is O(n) because everything shifts, so I'll append and reverse at the end instead."
- "Strings are immutable here, so I'll collect the pieces in a list and join once, keeping it O(n)."
- "The values are lowercase letters, so I'll use an array of 26 counters instead of a hash map."
Used in
- Patterns: Two Pointers, Sliding Window, Hash Maps and Prefix Sums, Binary Search
- Problems: Move Zeroes, Valid Palindrome, Product of Array Except Self, Merge Intervals
- Data structures: Hash Maps, Linked Lists (the opposite trade-off)