Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 225 ยท Arrays and Lists

Array Operations

Master the core array operations in Python: traverse, search, reverse, rotate three ways, merge sorted arrays and remove duplicates in place, with traces and costs.

Nearly every array problem is built from a small set of basic moves: walk through the items, find one, change one, reverse a stretch, rotate, merge two arrays, clean out duplicates. If you can write these moves from memory, harder problems become a matter of combining them.

In this lesson you will write each operation from scratch, with the brute-force version first and then a better one where it exists. Every function is short on purpose, so you can trace it by hand. The costs build on Arrays and Python Lists: reading by index is O(1), shifting is O(n).

Traverse, search, update

Traversal visits every item once: O(n). Searching an unsorted array has no shortcut, so you check items one at a time (Linear Search goes deeper). Updating by index is O(1).

Python Traverse, search and update

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Returning -1 for "not found" is a convention borrowed from other languages. In Python you can also return None, but -1 mirrors the str.find method, and it is what interview problems usually expect.

Reverse

To reverse an array in place, swap the first and last items, then the second and second-last, and so on, until the two ends meet in the middle. It needs n // 2 swaps and O(1) extra space.

TEXT
 i                 j
[1, 2, 3, 4, 5]  swap -> [5, 2, 3, 4, 1]
    i         j
[5, 2, 3, 4, 1]  swap -> [5, 4, 3, 2, 1]
        i,j      stop: pointers met
Python Reverse in place with two indexes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop condition is i < j. With an odd length the two indexes meet on the middle item, which does not need to move. This "two ends moving inward" idea is the heart of Two Pointers.

Rotate

Rotating right by k moves the last k items to the front: [1,2,3,4,5,6,7] rotated right by 3 is [5,6,7,1,2,3,4]. First normalise k with k %= n, since rotating by n gives back the same array. There are three standard ways.

Way 1: a new array

Place item i at position (i + k) % n in a fresh list. Simple, O(n) time, O(n) extra space.

Way 2: rotate by one, k times (brute force)

Repeat "pop the last item, insert it at the front" k times. Each step shifts n items, so this is O(nยทk), which is O(nยฒ) in the worst case. It is easy to get right but slow.

Way 3: three reversals (in place, O(n))

Reverse the whole array, then reverse the first k items, then reverse the remaining n - k. Why does it work? Reversing the whole array puts the last k items in front but backwards; reversing each block fixes their order.

TEXT
a = [1, 2, 3, 4, 5, 6, 7], k = 3
reverse all        -> [7, 6, 5, 4, 3, 2, 1]
reverse first 3    -> [5, 6, 7, 4, 3, 2, 1]
reverse the rest   -> [5, 6, 7, 1, 2, 3, 4]
Python Three ways to rotate right

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python slicing gives a one-liner: a[-k:] + a[:-k] rotates right by k (for 0 < k < n). It builds new lists, so it is the O(n) extra-space version in disguise.

Maximum sum of rotation configurations

Given a, define the value of a rotation as sum(i * a[i]). Which rotation maximizes it? Computing each of the n rotations from scratch is O(n^2). Instead, derive each value from the previous one. Rotating right by one moves the last item to index 0 and shifts all others up by one, so

TEXT
next = current + total_sum - n * last_item

where last_item is the element that wraps around. That makes the whole scan O(n) time and O(1) space.

Python Best rotation value in O(n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merge two sorted arrays

Given two sorted arrays, produce one sorted array. The brute force is to concatenate and sort: O(n log n). The better way uses the fact that both inputs are already sorted: keep one pointer in each array, repeatedly take the smaller front item. That is O(n + m) time and O(n + m) space. This is also the merge step of Merge Sort.

TEXT
a = [1, 4, 9]     b = [2, 3, 10]
 i                 j
take 1 (1<2), take 2 (4>2), take 3 (4>3), take 4 (4<10), take 9 (9<10)
a is empty -> append the rest of b: 10
result = [1, 2, 3, 4, 9, 10]
Python Merge two sorted lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The comparison count is at most n + m - 1, so the cost really is linear. When one array is entirely smaller (the second case), only three comparisons are needed before the rest is copied.

Remove duplicates from a sorted array, in place

Classic problem: given a sorted array, keep one copy of each value and return the new length, using O(1) extra space. Because duplicates are neighbours, a write pointer works: write marks the end of the clean prefix, and a read pointer scans ahead. Whenever the read item differs from the last kept item, copy it to write.

TEXT
[1, 1, 2, 2, 2, 3]
 w  r
r=1: 1 == a[w]=1, skip
r=2: 2 != 1 -> w=1, a[1]=2     [1, 2, 2, 2, 2, 3]
r=3,4: equal to 2, skip
r=5: 3 != 2 -> w=2, a[2]=3     [1, 2, 3, 2, 2, 3]
length = w + 1 = 3

A brute-force alternative deletes each duplicate with del a[i], shifting every time: O(nยฒ). The two-pointer version is O(n).

Python Remove duplicates in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity summary

Operation Time Extra space
Traverse / count O(n) O(1)
Search (unsorted) O(n) O(1)
Reverse in place O(n) O(1)
Rotate: three reversals O(n) O(1)
Rotate: one by one O(nยทk) O(1)
Merge two sorted arrays O(n + m) O(n + m)
Remove duplicates (sorted, in place) O(n) O(1)

Common mistakes

  • Forgetting k %= n when rotating. Without it, k > n indexes go wrong.
  • Rotating an empty list. k % 0 raises ZeroDivisionError; check for an empty array first.
  • Deleting while iterating, which skips items. Use a write pointer or build a new list.
  • Assuming the input is sorted for the duplicate-removal trick. On unsorted data, equal values may not be neighbours.
  • Returning the array instead of the new length when a problem asks for the length: the tail beyond length is garbage.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many swaps does an in-place reversal of an array with 7 items perform?

    It performs n // 2 swaps. The middle item stays where it is, so 7 // 2 = 3.
  2. 2. Which rotation method uses O(1) extra space and O(n) time?

    Three reversals work in place, each item is touched a constant number of times. The new-list approach needs O(n) space and the one-by-one approach costs O(nยทk) time.
  3. 3. Merging sorted lists of sizes n and m with two pointers costs

    Each step places one item in the result and moves one pointer forward, so there are at most n + m steps.
  4. 4. Why does the in-place duplicate removal need a sorted array?

    The algorithm compares each item with the last kept one. In an unsorted array a duplicate can be far from its twin and would be missed.
  5. 5. What is rotating [1, 2, 3, 4] right by 6 equivalent to?

    6 % 4 = 2, so the result is [3, 4, 1, 2]. Rotating by the length returns the original array.

Summary

  • Traversal, search and counting are O(n); update by index is O(1).
  • Reverse in place with two indexes moving inward: n // 2 swaps, O(1) space.
  • Rotate with k %= n, then use three reversals for O(n) time and O(1) space; avoid the O(nยทk) one-by-one method.
  • Merge sorted arrays with one pointer each in O(n + m).
  • Remove duplicates from a sorted array with read and write pointers in O(n).

Next: Dynamic Arrays