In-place Changes and Swaps

22 min · Intermediate

Many problems say 'do it in place', meaning use no second list. Python makes this pleasant: one line swaps two items, and a second index lets you tidy a list in one pass.

What in place means

In-place change means updating the items of the existing list instead of building a new one. It needs O(1) extra space: a few variables, however long the list is.

A stock tool must raise every price by 10 percent without building a second list. Changing items where they sit is called working in place. It needs no extra list that grows with the input.

Python

prices = [100, 250, 80]for i in range(len(prices)):    prices[i] = prices[i] * 11 // 10print(prices)

The same list object is updated. A comprehension would build a new list instead.

Swap with tuple assignment

Swap means exchanging the values at two positions. In Python, a[i], a[j] = a[j], a[i] does it in one safe step.

Two seats in a booking list must trade places. Many languages need a temporary variable. Python builds the right-hand pair first and then assigns it, so one line is enough.

Python

seats = ["A1", "A2", "A3", "A4"]seats[0], seats[3] = seats[3], seats[0]print(seats)

Example 1 · One pass of neighbour swaps

Python

marks = [40, 90, 15, 70]for i in range(len(marks) - 1):    if marks[i] > marks[i + 1]:        marks[i], marks[i + 1] = marks[i + 1], marks[i]print(marks)

Output

[40, 15, 70, 90]

What this code does

Each neighbouring pair is compared and swapped if it is out of order.
After one pass the largest mark, 90, has moved to the end.
This is the first pass of bubble sort. It uses O(1) extra space.

No temporary variable is needed. Both values are read before either place is changed.

The write pointer: keep what you want

Write pointer is an index that marks where the next kept item goes while a loop reads ahead. It filters a list in place in one pass with O(1) extra space.

A job log holds zeros for failed jobs. Keep the real values at the front, in order. One loop reads every item, and a second index, write, marks where the next kept item goes.

Python

1jobs = [0, 4, 0, 7, 9, 0]2write = 03for value in jobs:4    if value != 0:5        jobs[write] = value6        write += 17print(jobs[:write])

Example 2 · Move zeros: brute force with a new list

Python

jobs = [0, 4, 0, 7, 9, 0]result = [x for x in jobs if x != 0] + [0] * jobs.count(0)print(result)

Output

[4, 7, 9, 0, 0, 0]

What this code does

The comprehension keeps the non-zero values and the count rebuilds the zeros.
It is short and correct, but it builds a second list: O(n) extra space.
Interviews usually ask for the in-place version next.

Example 3 · Move zeros in place

Python

1def move_zeros(items):2    write = 03    for read in range(len(items)):4        if items[read] != 0:5            items[write], items[read] = items[read], items[write]6            write += 17
8
9jobs = [0, 4, 0, 7, 9, 0]10move_zeros(jobs)11print(jobs)

Output

[4, 7, 9, 0, 0, 0]

What this code does

read scans every position and write marks the next slot for a non-zero value.
Swapping, not copying, pushes the zeros towards the end.
One pass: O(n) time and O(1) extra space.

Example 4 · Remove duplicates from a sorted list

Python

1def dedupe(items):2    if not items:3        return 04    write = 15    for read in range(1, len(items)):6        if items[read] != items[write - 1]:7            items[write] = items[read]8            write += 19    return write10
11
12ids = [1, 1, 2, 2, 2, 3, 5, 5]13kept = dedupe(ids)14print(kept, ids[:kept])

Output

4 [1, 2, 3, 5]

What this code does

In a sorted list, equal values sit side by side, so one comparison with the last kept item is enough.
The function returns how many items are valid; the slots after that are ignored.
O(n) time, O(1) extra space.

write is never ahead of the item being read, so no unread item is overwritten. The slots after write still hold old values.

Copy or alias

Writing backup = prices does not copy the list. Both names point at one list, so an in-place change shows through both. A slice makes a real copy when you need the old values too.

Python

1prices = [100, 250, 80]2alias = prices3copy = prices[:]4prices[0] = 9995print(alias)6print(copy)

Example 5 · Protect the caller's list

Python

1def add_tax(prices):2    for i in range(len(prices)):3        prices[i] += prices[i] // 104    return prices5
6
7original = [100, 200]8taxed = add_tax(original[:])9print(original, taxed)

Output

[100, 200] [110, 220]

What this code does

The function changes the list it receives in place.
Passing original[:] hands it a copy, so the caller's list stays unchanged.
Decide who owns the list, and say so in the function name or a comment.

alias sees the change because it is the same list. copy keeps the old values.

Next step

Check your understanding

11 quick questions

What in place means

In-place change means updating the items of the existing list instead of building a new one. It needs O(1) extra space: a few variables, however long the list is.

A stock tool must raise every price by 10 percent without building a second list. Changing items where they sit is called working in place. It needs no extra list that grows with the input.

The write pointer: keep what you want

Write pointer is an index that marks where the next kept item goes while a loop reads ahead. It filters a list in place in one pass with O(1) extra space.

A job log holds zeros for failed jobs. Keep the real values at the front, in order. One loop reads every item, and a second index, write, marks where the next kept item goes.

1def move_zeros(items):2 write = 03 for read in range(len(items)):4 if items[read] != 0:5 items[write], items[read] = items[read], items[write]6 write += 17 8 9jobs = [0, 4, 0, 7, 9, 0]10move_zeros(jobs)11print(jobs)

1def dedupe(items):2 if not items:3 return 04 write = 15 for read in range(1, len(items)):6 if items[read] != items[write - 1]:7 items[write] = items[read]8 write += 19 return write10 11 12ids = [1, 1, 2, 2, 2, 3, 5, 5]13kept = dedupe(ids)14print(kept, ids[:kept])