Arrays: traversal and in-place updates

What an array really is

An array is a row of equal-sized boxes placed next to each other in memory. Each box has a number, its index, starting at 0. Because the boxes are side by side and the same size, the computer finds box i with one calculation: start address + i × box size. That is why reading or writing nums[i] is O(1), whether the array has 10 items or 10 million.

A Python list is a dynamic array. Its boxes hold references (pointers) to the actual objects, so items of different types can share one list, but the costs are the same as a plain array: O(1) to index, O(1) amortised to append at the end.

Insert and delete in the middle cost O(n)

Inserting at index i means moving every item after i one place right to make room; deleting means moving them one place left to close the gap. In the worst case (index 0) that is all n items, so insert and delete in the middle are O(n). At the end there is nothing to move, so append and pop() are cheap.

Traversal patterns

• Forward: for i in range(len(nums)), or for x in nums when you do not need the index.
• Backward: for i in range(len(nums) - 1, -1, -1).
• With index and value: for i, x in enumerate(nums).
• Neighbours: for i in range(1, len(nums)) and compare nums[i - 1] with nums[i].
• Two ends towards the middle: left = 0, right = len(nums) - 1, move them inwards (used for reversing; more in Module 3).
• A read pointer and a write pointer: read every item, but write only the ones you keep (used for moving zeros).

Rotating by k

Rotating right by k moves every item k places to the right, and items that fall off the end come back at the front. [1, 2, 3, 4, 5, 6, 7] rotated right by 3 is [5, 6, 7, 1, 2, 3, 4]. Rotating by n (the length) gives the same list back, so always reduce k first with k % n. Do this only when n > 0, because % 0 raises ZeroDivisionError.

The easy way builds a new list with slices: nums[-k:] + nums[:-k], O(n) time and O(n) extra space. Careful: when k is 0, nums[-0:] is the whole list, so check k == 0 separately or use nums[n - k:] + nums[:n - k].

The in-place trick uses three reversals and O(1) extra space: reverse the whole list, then reverse the first k items, then reverse the rest.

def reverse(nums, left, right):
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

def rotate_in_place(nums, k):
    n = len(nums)
    if n == 0:
        return
    k %= n
    reverse(nums, 0, n - 1)      # [7, 6, 5, 4, 3, 2, 1]
    reverse(nums, 0, k - 1)      # [5, 6, 7, 4, 3, 2, 1]
    reverse(nums, k, n - 1)      # [5, 6, 7, 1, 2, 3, 4]

a = [1, 2, 3, 4, 5, 6, 7]
rotate_in_place(a, 3)
print(a)   # Output: [5, 6, 7, 1, 2, 3, 4]

Moving zeros to the end, keeping order

To move all zeros to the end while keeping the other items in their original order, use a write index. Walk through the list; each time you see a non-zero, copy it to position write and move write forward. When the walk ends, fill the rest of the list with zeros. That is O(n) time and O(1) extra space.

def move_zeros(nums):
    write = 0
    for x in nums:
        if x != 0:
            nums[write] = x
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0

a = [0, 1, 0, 3, 12]
move_zeros(a)
print(a)   # Output: [1, 3, 12, 0, 0]

Common mistakes

• Removing items from a list while looping over it with for x in nums: the loop skips the item after each removal. Fix: build a new list, or use the write-pointer pattern.
• Forgetting k % n, or computing it when the list is empty. Fix: if not nums: return first, then k %= len(nums).
• Rebinding instead of changing in place: nums = nums[-k:] + nums[:-k] inside a function does not change the caller's list. Fix: assign nums[:] = … or swap items by index.
• Off-by-one errors with range(). Fix: range(a, b) stops BEFORE b; test with a one-item list.
• Not saying whether you return a new list or change the input. Fix: state it before coding; interviewers care.