Array Traversal and Manipulation
An array (Python’s list) is a sequence of elements you can reach instantly by index. Traversal means visiting each element to read, transform, or aggregate it. Manipulation means changing the array’s contents — inserting, deleting, updating, or reordering elements, often without allocating a second array. These two skills underpin nearly every other array algorithm (searching, sorting, sliding window, two-pointer), and “modify the array in place” is one of the most common interview phrasings you’ll see.
Overview: How Traversal and Manipulation Work
Under the hood, a Python list is a dynamic array: a contiguous block of memory holding pointers to the actual objects. Because the block is contiguous and each pointer is the same fixed size, the interpreter computes the memory address of arr[i] directly from i — no searching required. That’s why indexing is O(1): it’s arithmetic, not a walk through the structure.
Traversal means visiting arr[0], arr[1], …, arr[n-1] in order, in reverse, or in some other pattern. In Python you rarely need raw index loops for simple traversal — for value in arr:, or for index, value in enumerate(arr): when you need the position too, is both faster to write and clearer than for i in range(len(arr)):.
Manipulation is where the dynamic-array structure matters more. Appending (arr.append(x)) is O(1) amortized because CPython over-allocates extra capacity when it grows the array, so most appends just write into already-reserved space; only occasionally does it need to allocate a bigger block and copy everything over. Inserting or deleting anywhere except the end (arr.insert(0, x), del arr[0], arr.pop(0)) is O(n), because every following element has to shift one slot to keep the array contiguous.
A large share of manipulation problems are solved with the two-pointer technique: keep two index variables that move through the array — from both ends inward, or one fast and one slow — so you can rearrange elements in place using O(1) extra space instead of building a second array. You’ll see this pattern in the examples below; it’s one of the most interview-relevant ideas in this course.
Slicing
Python’s slice syntax arr[start:stop] is convenient but it always creates a new list by copying the referenced elements — unlike some languages, it is not a view into the original. A slice of length k costs O(k) time and space. That’s fine occasionally, but doing it inside a loop can silently turn an O(n) algorithm into O(n²).
Time and Space Complexity
The table below summarizes the core operations. n is the number of elements in the array.
| Operation | Time | Space | Why |
|---|---|---|---|
Index access arr[i] |
O(1) | O(1) | Direct address calculation from a contiguous block |
| Traversal (visit every element) | O(n) | O(1) extra | Each element visited exactly once; no extra structure needed |
Search with in (unsorted) |
O(n) | O(1) | Must check elements one by one until a match or the end |
| Append at end | O(1) amortized | O(1) amortized | Over-allocated capacity absorbs most appends; occasional resize+copy is O(n) but rare |
| Insert/delete at front or middle | O(n) | O(1) | Every following element must shift one slot to stay contiguous |
| Pop from end | O(1) | O(1) | No shifting needed; capacity simply shrinks by one used slot |
Slice arr[a:b] |
O(k) | O(k) | Copies the k = b - a referenced elements into a new list |
| In-place reverse (two-pointer) | O(n) | O(1) | Each pair of elements is swapped once; no new array allocated |
The recurring theme: anything that touches every element at least once is O(n) — you can’t do better, since you must look at each element. The distinction that matters is space: an in-place two-pointer rewrite uses O(1) auxiliary space, while building a new list (via a comprehension or slicing) uses O(n). Both are valid; the choice depends on whether you can mutate the input and whether memory is a constraint.
Examples
Example 1: Index-aware traversal
This traverses an array while tracking both the index and a running total — the shape most traversal problems take once you need more than “look at every value.”
def traverse_and_sum(nums: list[int]) -> tuple[int, float]:
total = 0
for index, value in enumerate(nums):
total += value
print(f"index {index}: value {value}, running total {total}")
average = total / len(nums)
return total, average
numbers = [4, 8, 15, 16, 23, 42]
total, average = traverse_and_sum(numbers)
print(f"Total: {total}")
print(f"Average: {average:.2f}")
Output:
index 0: value 4, running total 4
index 1: value 8, running total 12
index 2: value 15, running total 27
index 3: value 16, running total 43
index 4: value 23, running total 66
index 5: value 42, running total 108
Total: 108
Average: 18.00
enumerate(nums) yields (index, value) pairs without a manual counter. The running total accumulates 4, 12, 27, 43, 66, 108 as each value is added, and the final average is 108 / 6 = 18.0, formatted to two decimals.
Example 2: In-place reversal with two pointers
Reversing an array without allocating a new one is the simplest demonstration of the two-pointer pattern.
def reverse_in_place(nums: list[int]) -> None:
left, right = 0, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
values = [10, 20, 30, 40, 50]
print(f"Before: {values}")
reverse_in_place(values)
print(f"After: {values}")
Output:
Before: [10, 20, 30, 40, 50]
After: [50, 40, 30, 20, 10]
left starts at index 0, right at index 4. Each iteration swaps nums[left] and nums[right], then moves both pointers inward, stopping once they meet or cross — for 5 elements that’s 2 swaps, not 5. No second list is created, which is why the function returns None.
Example 3: Removing duplicates from a sorted array in place
A classic interview problem: given a sorted array, remove duplicates in place and return the length of the deduplicated portion, using only O(1) extra space. It uses a read/write pointer pair instead of a left/right pair.
def remove_duplicates(nums: list[int]) -> int:
if not nums:
return 0
write_index = 1
for read_index in range(1, len(nums)):
if nums[read_index] != nums[write_index - 1]:
nums[write_index] = nums[read_index]
write_index += 1
return write_index
sorted_values = [1, 1, 2, 2, 2, 3, 4, 4, 5]
new_length = remove_duplicates(sorted_values)
print(f"New length: {new_length}")
print(f"Deduplicated portion: {sorted_values[:new_length]}")
Output:
New length: 5
Deduplicated portion: [1, 2, 3, 4, 5]
read_index scans forward while write_index only advances when it finds a value different from the last one kept. Because the input is sorted, duplicates of a value are always adjacent, so comparing against nums[write_index - 1] is enough to detect them. The full trace is below.
How It Works Step by Step
Tracing remove_duplicates on [1, 1, 2, 2, 2, 3, 4, 4, 5], starting with write_index = 1:
| read_index | nums[read_index] | nums[write_index – 1] | Action | write_index after |
|---|---|---|---|---|
| 1 | 1 | 1 | Equal, skip | 1 |
| 2 | 2 | 1 | Different, write to index 1 | 2 |
| 3 | 2 | 2 | Equal, skip | 2 |
| 4 | 2 | 2 | Equal, skip | 2 |
| 5 | 3 | 2 | Different, write to index 2 | 3 |
| 6 | 4 | 3 | Different, write to index 3 | 4 |
| 7 | 4 | 4 | Equal, skip | 4 |
| 8 | 5 | 4 | Different, write to index 4 | 5 |
By the time read_index reaches the end, write_index is 5, and the first 5 slots hold [1, 2, 3, 4, 5]. Everything from index 5 onward still holds leftover values from the original array, which is why the function returns write_index instead of relying on len(nums).
Common Mistakes
Mistake 1: Mutating a list while iterating over it
Removing elements from a list while looping over that same list is a common bug, because the loop’s internal position and the list’s contents fall out of sync.
numbers = [1, 2, 2, 3, 4]
for value in numbers:
if value % 2 == 0:
numbers.remove(value)
print(numbers)
Output:
[1, 2, 3]
The intent was to remove every even number, leaving [1, 3]. Instead one 2 survives. After the first 2 (index 1) is removed, everything shifts left — the second 2 moves from index 2 to index 1. But the loop’s cursor has already moved to index 2, so it never revisits index 1, and that 2 is skipped. Fix: never mutate a list you’re iterating over — iterate over a copy, or build a new list with a comprehension:
numbers = [1, 2, 2, 3, 4]
numbers = [value for value in numbers if value % 2 != 0]
print(numbers)
Output:
[1, 3]
Mistake 2: Off-by-one index bounds
Comparing each element to its neighbor is common, but looping over the full range of indices and reaching one past the end is an easy mistake:
def has_ascending_pair(arr: list[int]) -> bool:
for i in range(len(arr)):
if arr[i] < arr[i + 1]:
return True
return False
print(has_ascending_pair([5, 3, 1]))
Output:
IndexError: list index out of range
When i reaches len(arr) - 1, the code still tries to read arr[i + 1] — one past the end. Whenever a loop body looks at arr[i + 1] (or arr[i - 1]), the range needs to stop one earlier: range(len(arr) - 1), not range(len(arr)):
def has_ascending_pair(arr: list[int]) -> bool:
for i in range(len(arr) - 1):
if arr[i] < arr[i + 1]:
return True
return False
print(has_ascending_pair([5, 3, 1]))
print(has_ascending_pair([5, 3, 4]))
Output:
False
True
Best Practices
- Use
for value in arr:orfor index, value in enumerate(arr):instead offor i in range(len(arr)):when you don’t need manual index arithmetic. - Never remove from or insert into a list while iterating over it. Iterate over a copy (
arr[:]), or build a new list with a comprehension. - Reach for the two-pointer pattern whenever a problem calls for “in place” with
O(1)extra space — reversal, partitioning, deduplication, merging. - Remember slicing (
arr[a:b],arr[::-1]) always copies. Fine outside hot loops; avoid it inside anO(n)loop or it becomesO(n²). - For fast insertion/removal at both ends, use
collections.deque—list.insert(0, x)andlist.pop(0)areO(n), while thedequeequivalents areO(1). - Don’t build strings with
+=in a loop (O(n²)); collect pieces in a list and join once with"".join(pieces). - Prefer list comprehensions over manual append loops for simple
O(n)transformations.
Practice Exercises
- Write a function that rotates an array left by
kpositions in place, using onlyO(1)extra space. Hint: reversing the whole array, then reversing each of the two resulting pieces, produces a rotation. For[1, 2, 3, 4, 5]rotated left by 2, the expected result is[3, 4, 5, 1, 2]. - Write a function that moves all zeros in an array to the end while preserving the relative order of the non-zero elements, modifying the array in place. For input
[0, 1, 0, 3, 12], the expected result is[1, 3, 12, 0, 0]. - Given a sorted array and a target sum, use the two-pointer technique (one pointer at each end, moving inward) to find the indices of the two numbers that add up to the target, without using extra space for a hash map. For
[2, 7, 11, 15]with target9, the expected result is indices(0, 1).
Summary
- Traversal means visiting every element (
O(n)time,O(1)extra space); manipulation means changing the array’s contents in place or by building a new one. - Index access is
O(1)because a Python list is a contiguous block of pointers; the interpreter computes an address instead of searching. - Appending at the end is
O(1)amortized thanks to over-allocated capacity; inserting or deleting elsewhere isO(n)because elements must shift. - The two-pointer technique (left/right, or read/write) rearranges arrays in place using
O(1)extra space — the standard approach for reversal, deduplication, and partitioning. - Slicing always copies:
O(k)time and space for a slice of lengthk. Fine outside hot loops; costly inside one. - Never mutate a list while iterating over it — the loop’s cursor and the list’s contents fall out of sync, silently skipping elements.
- Always double-check loop bounds when a loop body looks one index ahead or behind (
arr[i + 1],arr[i - 1]) to avoid anIndexError.
