Arrays & two pointers
Why indexing is O(1), why inserting in the middle isn't, and the two-pointer pattern. · 7 min read
An array stores its elements in one contiguous block of memory. Because every slot is the same size, the address of a[i] is just start + i × size — a single calculation. That's why random access is `O(1)`: reaching a[1000] costs exactly the same as a[0].
Why indexing is constant
address(a[i]) = start + i × item_size— The machine computes the address directly.one multiplication + one addition— The number of arithmetic steps does not grow with n.no elements before i are inspected— Indexing jumps straight to the slot.
Result: O(1) access
Many array problems have an elegant O(n) solution using two pointers that move toward each other. Here we reverse an array in place — no extra memory, one pass:
Run the two-pointer reverse:
def reverse_in_place(a):
a = a[:]
left, right = 0, len(a) - 1
while left < right:
a[left], a[right] = a[right], a[left]
left += 1
right -= 1
return a
data = [2, 4, 6, 8, 10]
print("input: ", data)
print("reversed:", reverse_in_place(data))
Interactive visualization: Reverse in place with two pointers — step through it frame by frame on this page.
The same pattern powers palindrome checks, pair-sum on a sorted array, and merging — any time you can make progress from both ends at once.
Practice: Running Sum (Easy) — Build the array of prefix sums.
Practice: Move Zeroes (Easy) — Push all zeroes to the end, keeping the order of the rest.
Practice: Valid Palindrome (Easy) — Ignore case and non-alphanumerics — is it a palindrome?