An array stores elements in contiguous memory, so any element is reachable in one step by its index. That makes access O(1), but inserting or deleting in the middle is O(n) because the rest must shift.
The two-pointer pattern
Instead of a nested loop, keep two indices and move them intelligently — from the two ends towards the middle, or one chasing the other. On a sorted array this answers 'find a pair' questions in a single O(n) pass.
Pair with a given sum (sorted array)
left = 0; right = n - 1
while left < right:
s = A[left] + A[right]
if s == target: return (left, right)
if s < target: left = left + 1 // need bigger
else: right = right - 1 // need smallerO(n)→O(1)
Two pointers replace a nested loop; no extra memory.
⚡ The edge
- When a problem gives a sorted array and asks for a pair, a triple, or a partition, reach for two pointers — it collapses an O(n²) scan into O(n).
- If the array is unsorted but you only need a pair sum, a hash map is the faster tool (see the Hashing chapter).
Worked example
Reverse an array in place. What is the result for [1,2,3,4,5]?
left = 0; right = n - 1
while left < right:
swap(A[left], A[right])
left++; right--- Swap the outermost pair, then move both pointers inward and repeat.
- [1,2,3,4,5] -> swap 1 and 5 -> [5,2,3,4,1] -> swap 2 and 4 -> [5,4,3,2,1].
- The pointers meet at the middle (3), which stays in place.
Answer: [5, 4, 3, 2, 1] in O(n) time, O(1) space
⚠ Watch out
- Arrays are 0-indexed: valid indices are 0 to n−1; A[n] is out of bounds.
- Two pointers from both ends only work when the array is sorted (for sum/search problems).
- Avoid inserting or deleting inside an array in a loop — each shift is O(n).