I reversed the list, but the caller’s list didn’t change

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. A loop inside a loop is O(n²): twice the items, four times the work. Space is the same idea for the extra memory: a few numbers is O(1), a copy of the list is O(n). The full lesson: My code passed every test, then timed out on the big one.

Quick recapLists in two minutes· 2 min

A list keeps items in order, and you can change it. Each item has an index, counting from 0. append() adds at the end, pop() takes from the end, and insert(i, x) puts x at index i.

chars = ['c', 'a', 't']
chars[0]            # 'c'
chars.append('s')   # ['c', 'a', 't', 's']
chars.pop()         # 's', and chars is ['c', 'a', 't'] again
chars.insert(0, 'a')  # ['a', 'c', 'a', 't']
len(chars)          # 4

See the problem

The interview task: reverse a list of characters in place, with O(1) extra memory. You know [::-1] reverses, so you write:

def reverse_chars(chars):
    chars = chars[::-1]

You print chars inside the function, and it’s reversed. Then the test checks the caller’s list:

letters = ['h', 'e', 'l', 'l', 'o']
reverse_chars(letters)
print(letters)    # ['h', 'e', 'l', 'l', 'o']: not reversed

Nothing changed. chars[::-1] made a new list, and chars = ... only pointed the function’s own name at it. The caller’s list is still the old one. And the new list was a copy of every character: O(n) memory, when the task asked for O(1).

To change the caller’s list, you have to write into it. To do that with O(1) memory, you need to know how a list keeps its items.

Define the task

Write reverse_chars(chars).

• Input: chars, a list of one-character strings. Up to 400,000 of them.
• Output: nothing. Change chars itself, so the caller sees it reversed.
• The hard part: O(1) extra memory. No second list, and no reversed copy.

Example: after reverse_chars(letters) with letters = ['h', 'e', 'l', 'l', 'o'], letters is ['o', 'l', 'l', 'e', 'h'].

Pause and think

⏸ Pause and think

Before you write any code: which two characters must end up swapping places? And after them, which two?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

The first character must end up last, and the last first. So swap them.

Hint 2 of 3

Then the second and the second to last. Keep one index moving in from each end.

Hint 3 of 3

Stop when the two indices meet in the middle. Each swap puts two characters in place, so n characters take n // 2 swaps.

Understand the idea

A list is a row of boxes, numbered from 0. Python keeps a pointer to each item side by side, in one block of memory, so chars[3] jumps straight to box 3, whatever the length: O(1). chars[-1] is the last box, and chars[-2] the one before it.

The end is cheap. The front isn’t. append(x) puts x in the next free box at the end, and pop() takes the last one: O(1) on average. But insert(0, x) has to free box 0 first, so every item moves one box right. That’s O(n) for one insert. pop(0) moves every item one box left, which is also O(n). Python moves them with one fast copy in C, so you won’t notice on a small list. But n inserts at the front are still O(n²): 100,000 of them take about a second, and 200,000 about four.

Watch it on 5 characters. Each new character goes in at the front of out, and the panel counts the characters that moved to make room. Try your own word, 2 to 7 characters.

Put each character at the front

⤢ Full view

1. 0
2. 1
3. 2
4. 3
5. 4

Work so far

characters moved	0

Step 1 of 7. Start with an empty list, out. Each of the 5 characters goes in at its front. Question: With 5 characters, how many characters will the inserts move, in all?

What happens next? With 5 characters, how many characters will the inserts move, in all?

51025Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def reverse_chars(chars: list[str]) -> None:
2    out: list[str] = []
3    for c in chars:
4        out.insert(0, c)  # all of out moves one place right
5    chars[:] = out  # copy back into the caller's list

Try your own input

WordShow it

A slice is a copy. chars[2:5] makes a new list of 3 items, and chars[::-1] makes a new list of all n, backwards. Each costs O(k) time and O(k) memory, for k items. Slicing on the left of = is different: chars[:] = other writes into chars itself, so the caller sees the change.

Strings can’t be changed. s[0] = 'x' is an error. Every “change” to a string makes a new one: s.upper(), s.replace('a', 'b'), s + '!'. To change characters one at a time, turn the string into a list with list(s) and change the list. Then join it back into a string with ''.join(chars).

Build a long string with join. ''.join(parts) adds up the lengths first, then makes one string: O(total length). Adding to a string with += in a loop may copy everything so far each time, which is O(n²). CPython can often skip that copy, but you can’t count on it.

Walk a list without copying it. for c in chars walks it forwards. for i, c in enumerate(chars) gives the index too. reversed(chars) walks backwards without making a copy, and range(len(chars) - 1, -1, -1) gives the indices backwards. And for two pointers, keep two indices, like left and right, and move them towards each other.

What each step costs, for a list or a string of n items:

Step	List	String
a[i], a[-1], len(a)	O(1)	O(1)
a.append(x), a.pop()	O(1) on average	can’t: strings don’t change
a.insert(0, x), a.pop(0)	O(n): everything moves	can’t
a[i] = x	O(1)	can’t
a[i:j], a[::-1]	O(j − i): a new list	O(j − i): a new string
x in a	O(n): one by one	O(n) for one character
a + b	O(len(a) + len(b)): a new list	O(len(a) + len(b)): a new string
''.join(parts)		O(total length)
reversed(a)	O(1) to start, O(n) to walk, no copy	the same

Sets and dicts, which find an item in about one step, are in My import got 100 times slower when the data grew 10 times.

Climb the ladder

All three leave ['o', 'l', 'l', 'e', 'h'] in the caller’s list. What changes is the time and the extra memory.

Okay

Put each character at the front

The idea: Build a new list, putting each character in at the front. Then copy it back into chars.

It works, and chars[:] = out writes into the caller’s list, so the caller sees it reversed.

def reverse_chars(chars: list[str]) -> None:
    out: list[str] = []
    for c in chars:
        out.insert(0, c)  # all of out moves one place right
    chars[:] = out  # copy back into the caller's list

Time

O(n²)

Space

O(n)

Why

The k-th insert moves the k − 1 characters already there: n(n − 1)/2 moves. out holds every character.

Where it breaks: speed. 400,000 characters make about 80 billion moves. The editor below stops it after 3 seconds. And out is a second list, so it’s O(n) memory too.

Better

Copy it reversed, then write it back

The idea: chars[::-1] makes a reversed copy. chars[:] = writes that copy into the caller’s list.

The waste in Okay: each insert at the front moves everything already there. The slice makes the whole reversed list in one pass.

This is the See the problem code with one change: chars[:] = writes into the list, where chars = only moved the name.

Highlighted lines are new in this rung.

def reverse_chars(chars: list[str]) -> None:
    # A reversed copy, then copied back into the caller's list.
    chars[:] = chars[::-1]

Time

O(n)was O(n²)

Space

O(n)

Why

One pass to make the copy, one to write it back. The copy holds all n characters.

What changed from the previous rung

def reverse_chars(chars: list[str]) -> None:
    out: list[str] = []
    for c in chars:
        out.insert(0, c)  # all of out moves one place right
    chars[:] = out  # copy back into the caller's list
    # A reversed copy, then copied back into the caller's list.
    chars[:] = chars[::-1]

Where it breaks: memory. The reversed copy is a second list of n characters: megabytes for 400,000, when the task allows O(1).

Best

Swap from both ends

The idea: Swap the first and last characters, then move both indices one place in. Stop when they meet.

The waste in Better: it copies every character, when each one only needs to trade places with its partner at the other end. Each swap puts two characters in place, in the list itself.

Watch the panel: 2 swaps for 5 characters, where Okay made 10 moves. The middle character never moves.

Swap from both ends

⤢ Full view

1. h0
2. e1
3. l2
4. l3
5. o4

▲ left▲ right

Work so far

swaps	0

Step 1 of 7. left starts at the first character, and right at the last. Question: With 5 characters, how many swaps will it make?

What happens next? With 5 characters, how many swaps will it make?

245Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def reverse_chars(chars: list[str]) -> None:
2    left, right = 0, len(chars) - 1
3    while left < right:
4        chars[left], chars[right] = chars[right], chars[left]
5        left += 1
6        right -= 1

Try your own input

WordShow it

Highlighted lines are new in this rung.

def reverse_chars(chars: list[str]) -> None:
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1

Time

O(n)

Space

O(1)was O(n)

Why

n // 2 swaps, each O(1). It keeps two numbers, left and right.

What changed from the previous rung

def reverse_chars(chars: list[str]) -> None:
    # A reversed copy, then copied back into the caller's list.
    chars[:] = chars[::-1]
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1

When Best isn’t best: in real code, use chars.reverse(). It makes the same swaps, in C, so it’s many times faster. Better is quicker than this loop too, since its copy runs in C: Best wins on memory, not speed. In an interview, ask first: they may want the loop. And for a string, which can’t change, s[::-1] is the answer: a new string is the only way.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Each test calls your function, then checks the list it was given. Try Okay from the ladder first: it runs out of time on the speed test. Better fails the 1 MB test.

Reverse a list in place

Ctrl + Enter runs

def reverse_chars(chars: list[str]) -> None: # Reverse chars itself, with O(1) extra memory. # Return nothing. pass

Run testsReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: chars after reverse_chars(['h', 'e', 'l', 'l', 'o']) → ['o', 'l', 'l', 'e', 'h']
2. ○Not run yet: chars after reverse_chars(['a', 'b', 'c', 'd']) → ['d', 'c', 'b', 'a']
3. ○Not run yet: chars after reverse_chars(['a']) → ['a']
4. ○Not run yet: Extra test
5. ○Not run yet: Speed test: 400,000 characters, then the first 3 and last 3 of chars → ['p', 'o', 'n', 'c', 'b', 'a']
6. ○Not run yet: 400,000 characters in 1 MB, then the first 3 and last 3 of chars → ['p', 'o', 'n', 'c', 'b', 'a']

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

reverse_chars()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: put each character at the front	O(n²)	O(n)	Uses only insert()	Too slow past about 100,000 characters	Never: it’s here to show what the front costs
Better: copy it reversed, then write it back	O(n)	O(n)	Short, and the quickest here in Python: the copy runs in C	A second list as long as the first	Memory isn’t tight, or you want a new list anyway
Best: swap from both ends	O(n)	O(1)	No copy	A Python loop, so slower than Better’s copy	The task says in place, or memory is tight

How much work is that? Each bar is one rung, with n characters. Pick a size, or run the race.

Reversing a list: steps with n characters

1. OkayPut each character at the front · O(n²)≈ 5,000,000,000 characters moved

2. BetterCopy it reversed, then write it back · O(n)≈ 200,000 characters copied

3. BestSwap from both ends · O(n)≈ 50,000 swaps

At n = 100,000, Okay does about 100,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

The race counts steps and gives each one the same time, but real steps differ. Better’s copy runs in C, so at 400,000 characters it takes about 4 ms, where Best’s Python loop takes about 12 ms. Best wins on memory, not speed.

Common mistakes and edge cases

!chars = … moves a name. chars[:] = … changes the list.

Inside a function, chars = chars[::-1] points the local name chars at a new list, and the caller’s list is left as it was. chars[:] = chars[::-1] and chars[i] = x write into the list itself, so the caller sees the change. I changed my copy, and the original changed too shows names and objects in pictures.

• Empty and one-item lists. With left, right = 0, len(chars) - 1, an empty list starts with right at −1, and a list of one starts with both at 0. left < right is False at once, so nothing happens, which is right.
• < or <=? With while left <= right, an odd list swaps its middle character with itself. That’s harmless, but it’s one wasted step. With <, the loop stops when the pointers meet or cross.
• Off by one at the end. The last index is len(chars) - 1, not len(chars). chars[len(chars)] is an IndexError.
• Strings can’t change. s[0] = 'x' raises TypeError. Use list(s), change the list, then ''.join(chars).
• A slice in a loop is a copy in a loop. word[:i] for every i copies 1 + 2 + … + n characters: O(n²) time.
• Removing while you loop. for x in nums: nums.remove(x) skips items, because each remove moves the later ones left under the loop. Build a new list, or walk with an index you control.
• Characters aren’t always letters. list('naïve') has 5 characters, and an emoji is one character in Python. But some emoji are several characters joined together, and reversing those splits them.

Say it in the interview

Questions to ask first

• In place, or may I return a new list?
• Is it a list or a string? A string can’t change, so “in place” isn’t possible.
• How big can it get, and is memory tight?
• May I use chars.reverse(), or do you want the loop?

A 60-second walkthrough

“Slicing with [::-1] would be O(n) time, but it makes a full copy, so O(n) memory. And assigning it to the parameter wouldn’t change the caller’s list anyway. Instead I’ll use two pointers: left at 0 and right at the last index. While left is less than right, swap the two, then move left up and right down. Each swap puts two characters in place, so it’s n over 2 swaps: O(n) time and O(1) memory. Empty and one-character lists don’t enter the loop, which is right.”

Likely follow-ups

• Why not chars.reverse()? In real code, you would: it’s the same swaps, in C. The loop shows you know how it works.
• What if it’s a string? Strings can’t change, so return a new one: s[::-1], or ''.join(reversed(s)). That’s O(n) memory, and there’s no way round it.
• Reverse the order of the words in a sentence, in place? Reverse the whole list of characters, then reverse each word back. Each character moves twice: O(n) time, O(1) memory.
• What does “amortized” mean for append()? Now and then the list runs out of room and moves to a bigger block, which is O(n). It happens rarely enough that n appends take O(n) in all, so each one is O(1) amortized.

Practice

Three problems, from easy to medium. Each changes a list in place or walks a string. Each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. Move the zeros to the end (easy)

Write move_zeros(nums): move every 0 to the end of nums, in place, and keep the other numbers in their order. Return nothing.

Example: after move_zeros(nums) with nums = [0, 3, 0, 1, 2], nums is [3, 1, 2, 0, 0].

Hint 1 of 3

nums.remove(0) finds the first 0, then moves everything after it one place left. Once per 0, that’s O(n²).

Hint 2 of 3

A new list of the numbers that aren’t 0, then the zeros, is O(n) time. But it’s O(n) memory.

Hint 3 of 3

Keep an index, write, for where the next number that isn’t 0 goes. Copy each one there, then fill the rest with zeros.

Move the zeros to the end

Ctrl + Enter runs

def move_zeros(nums: list[int]) -> None: # Move every 0 to the end, in place, # keeping the other numbers in order. pass

Run testsReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: nums after move_zeros([0, 3, 0, 1, 2]) → [3, 1, 2, 0, 0]
2. ○Not run yet: nums after move_zeros([1, 2, 3]) → [1, 2, 3]
3. ○Not run yet: nums after move_zeros([0, 0]) → [0, 0]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 100,000 numbers, every other one 0, then the first 2 and last 2 of nums → [1, 1, 0, 0]
7. ○Not run yet: 400,000 numbers in 1 MB, then the first 2 and last 2 of nums → [1, 2, 0, 0]

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

move_zeros()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Take each 0 out, and add it at the end

The idea: For each 0, nums.remove(0), then nums.append(0).

Short, and it says what the problem says.

def move_zeros(nums: list[int]) -> None:
    """Move every 0 to the end, keeping the other numbers in order, in place."""
    for _ in range(nums.count(0)):
        nums.remove(0)  # finds the first 0, then moves everything after it left
        nums.append(0)

Time

O(n²)

Space

O(1)

Why

Each remove searches from the front, then moves the rest of the list left: O(n), once per 0.

Where it breaks: 100,000 numbers with 50,000 zeros is billions of steps: it runs out of time.

Better

Build the new order, then write it back

The idea: The numbers that aren’t 0, then as many zeros as there were, written into nums with nums[:] =.

The waste in Okay: every remove moves the whole rest of the list. Building the answer in one go moves each number once.

Highlighted lines are new in this rung.

def move_zeros(nums: list[int]) -> None:
    """Move every 0 to the end, keeping the other numbers in order, in place."""
    nums[:] = [x for x in nums if x != 0] + [0] * nums.count(0)

Time

O(n)

Space

O(n)was O(1)

Why

A pass to count the zeros, one to keep the rest, one to write back. The new list holds all n numbers.

What changed from the previous rung

def move_zeros(nums: list[int]) -> None:
    """Move every 0 to the end, keeping the other numbers in order, in place."""
    for _ in range(nums.count(0)):
        nums.remove(0)  # finds the first 0, then moves everything after it left
        nums.append(0)
    nums[:] = [x for x in nums if x != 0] + [0] * nums.count(0)

Where it breaks: memory. The new list is as long as nums: megabytes for 400,000 numbers.

Best

Copy each number forward, then fill with zeros

The idea: write is where the next number that isn’t 0 goes. Copy each one there, then set everything from write on to 0.

The waste in Better: it builds a second list, when the numbers only ever move left. write never gets ahead of the loop, so copying into nums[write] never overwrites a number still to come.

For the example: 3, 1 and 2 are copied to indices 0, 1 and 2, then indices 3 and 4 are set to 0.

Highlighted lines are new in this rung.

def move_zeros(nums: list[int]) -> None:
    """Move every 0 to the end, keeping the other numbers in order, in place."""
    write = 0  # where the next number that isn't 0 goes
    for x in nums:
        if x != 0:
            nums[write] = x
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0

Time

O(n)

Space

O(1)was O(n)

Why

Two passes over nums, and one number kept.

What changed from the previous rung

def move_zeros(nums: list[int]) -> None:
    """Move every 0 to the end, keeping the other numbers in order, in place."""
    nums[:] = [x for x in nums if x != 0] + [0] * nums.count(0)
    write = 0  # where the next number that isn't 0 goes
    for x in nums:
        if x != 0:
            nums[write] = x
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0

When Best isn’t best: if the caller needs the old list too, change a copy, or build a new one: Better is clearer.

2. A palindrome, skipping spaces and case (easy)

Write is_palindrome(s): True if s reads the same forwards and backwards, counting only letters and digits, and not caring about upper or lower case. A big test has 600,000 characters, so watch the memory.

Example: is_palindrome('Never odd or even') gives True. is_palindrome('race a car') gives False.

Hint 1 of 3

s == s[::-1] compares every character, spaces and capitals too. “Never odd or even” backwards is “neve ro ddo reveN”.

Hint 2 of 3

Keep only the letters and digits, in lower case, then compare with the reverse. That works, but it builds new strings.

Hint 3 of 3

Two pointers from both ends: skip anything that isn’t a letter or digit, then compare the two in lower case.

A palindrome, skipping spaces and case

Ctrl + Enter runs

def is_palindrome(s: str) -> bool: # True if s reads the same both ways, counting # only letters and digits, in any case. return False

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: is_palindrome('Never odd or even') → True
2. ○Not run yet: is_palindrome('race a car') → False
3. ○Not run yet: is_palindrome('') → True
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: 600,000 characters, in 1 MB → True

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

is_palindrome()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Compare it with its reverse

The idea: s == s[::-1].

One line, and right for a plain word like “level”.

def is_palindrome(s: str) -> bool:
    """True if s reads the same both ways, counting only letters and digits, in any case."""
    return s == s[::-1]

Time

O(n)

Space

O(n)

Why

The reverse is a new string of n characters, and == compares them.

Where it breaks: it counts the spaces, the punctuation and the capitals. “Never odd or even” isn’t the same backwards, character for character, so it says False.

Better

Clean it up, then compare

The idea: Keep the letters and digits, in lower case, joined into t. Then t == t[::-1].

The waste in Okay: it’s not waste, it’s a bug: it compared characters the problem says to skip.

Highlighted lines are new in this rung.

def is_palindrome(s: str) -> bool:
    """True if s reads the same both ways, counting only letters and digits, in any case."""
    t = "".join(c.lower() for c in s if c.isalnum())
    return t == t[::-1]

Time

O(n)

Space

O(n)

Why

One pass to clean, one to reverse, one to compare. t and its reverse each hold up to n characters, and join first gathers them in a list.

What changed from the previous rung

def is_palindrome(s: str) -> bool:
    """True if s reads the same both ways, counting only letters and digits, in any case."""
    return s == s[::-1]
    t = "".join(c.lower() for c in s if c.isalnum())
    return t == t[::-1]

Where it breaks: memory. ''.join(...) gathers the 400,000 letters in a list first, then makes t, then t[::-1]: megabytes, for a yes or a no.

Best

Two pointers, skipping what doesn’t count

The idea: left from the start, right from the end. Skip anything that isn’t a letter or digit; compare the rest in lower case.

The waste in Better: it copies the string to clean it, when each check only needs two characters: one from each end. It also stops at the first pair that differs.

It’s the lesson’s swap loop, comparing instead of swapping.

Highlighted lines are new in this rung.

def is_palindrome(s: str) -> bool:
    """True if s reads the same both ways, counting only letters and digits, in any case."""
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Time

O(n)

Space

O(1)was O(n)

Why

Each step moves left or right, or both, so at most n steps. Only two indices are kept.

What changed from the previous rung

def is_palindrome(s: str) -> bool:
    """True if s reads the same both ways, counting only letters and digits, in any case."""
    t = "".join(c.lower() for c in s if c.isalnum())
    return t == t[::-1]
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

When Best isn’t best: for short strings, Better is clearer and fast enough. And isalnum() counts letters in any language, like é or ü, which may or may not be what the task means.

3. Rotate a list (medium)

Write rotate(nums, k): move every number k places to the right, in place. Numbers that go past the end come round to the front. k can be bigger than the list. Return nothing.

Example: after rotate(nums, 2) with nums = [1, 2, 3, 4, 5], nums is [4, 5, 1, 2, 3].

Hint 1 of 3

Moving the last number to the front, k times, is k inserts at the front: O(n) each.

Hint 2 of 3

k % len(nums) is all that matters: a full turn puts every number back. Two slices, joined in the other order, make the answer in O(n), but they’re copies.

Hint 3 of 3

Reverse the whole list, and the last k numbers come first, but backwards. Then reverse the first k, and reverse the rest.

Rotate a list

Ctrl + Enter runs

def rotate(nums: list[int], k: int) -> None: # Move every number k places right, in place, # wrapping round to the front. pass

Run testsReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: nums after rotate([1, 2, 3, 4, 5], 2) → [4, 5, 1, 2, 3]
2. ○Not run yet: nums after rotate([1, 2, 3], 4) → [3, 1, 2]
3. ○Not run yet: nums after rotate([7], 5) → [7]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 400,000 numbers, k = 200,000, then the first 2 and last 2 of nums → [200000, 200001, 199998, 199999]
7. ○Not run yet: 400,000 numbers, k = 200,000, in 1 MB, then the first 2 and last 2 of nums → [200000, 200001, 199998, 199999]

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

rotate()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Move the last number to the front, k times

The idea: nums.insert(0, nums.pop()), k % len(nums) times.

It does just what the problem says, and the k % len(nums) skips the full turns.

def rotate(nums: list[int], k: int) -> None:
    """Move every number k places to the right, wrapping round to the front, in place."""
    if not nums:
        return
    for _ in range(k % len(nums)):
        nums.insert(0, nums.pop())  # the last number to the front: all the others move

Time

O(n · k)

Space

O(1)

Why

Each insert at the front moves all n numbers, and there are up to n − 1 of them.

Where it breaks: with 400,000 numbers and k = 200,000, it moves about 80 billion numbers: it runs out of time.

Better

Two slices, joined the other way round

The idea: The last k numbers, then the rest, written into nums with nums[:] =.

The waste in Okay: it moves every number k times, one place at a time. The slices put each number straight where it ends up.

Highlighted lines are new in this rung.

def rotate(nums: list[int], k: int) -> None:
    """Move every number k places to the right, wrapping round to the front, in place."""
    if not nums:
        return
    k %= len(nums)
    nums[:] = nums[len(nums) - k :] + nums[: len(nums) - k]

Time

O(n)was O(n · k)

Space

O(n)was O(1)

Why

The two slices and the list they make hold every number, about twice.

What changed from the previous rung

def rotate(nums: list[int], k: int) -> None:
    """Move every number k places to the right, wrapping round to the front, in place."""
    if not nums:
        return
    for _ in range(k % len(nums)):
        nums.insert(0, nums.pop())  # the last number to the front: all the others move
    k %= len(nums)
    nums[:] = nums[len(nums) - k :] + nums[: len(nums) - k]

Where it breaks: memory. Two slices and the list they make are megabytes for 400,000 numbers.

Best

Reverse three times

The idea: Reverse the whole list. Then reverse the first k, and reverse the rest.

The waste in Better: it copies the list to rearrange it. Reversing is a rearrangement you can do in place, with the swap loop from the lesson.

For the example, with k = 2: [1, 2, 3, 4, 5] reversed is [5, 4, 3, 2, 1]. The first 2 reversed give [4, 5, 3, 2, 1], and the other 3 reversed give [4, 5, 1, 2, 3].

Highlighted lines are new in this rung.

def reverse(nums: list[int], left: int, right: int) -> None:
    """Reverse nums[left..right] in place, swapping from both ends."""
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1


def rotate(nums: list[int], k: int) -> None:
    """Move every number k places to the right, wrapping round to the front, in place."""
    if not nums:
        return
    k %= len(nums)
    reverse(nums, 0, len(nums) - 1)  # the whole list: the last k come first, backwards
    reverse(nums, 0, k - 1)  # put those k back in order
    reverse(nums, k, len(nums) - 1)  # and the rest

Time

O(n)

Space

O(1)was O(n)

Why

The three reversals swap about n numbers in all, each in place.

What changed from the previous rung

def reverse(nums: list[int], left: int, right: int) -> None:
    """Reverse nums[left..right] in place, swapping from both ends."""
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1


def rotate(nums: list[int], k: int) -> None:
    """Move every number k places to the right, wrapping round to the front, in place."""
    if not nums:
        return
    k %= len(nums)
    nums[:] = nums[len(nums) - k :] + nums[: len(nums) - k]
    reverse(nums, 0, len(nums) - 1)  # the whole list: the last k come first, backwards
    reverse(nums, 0, k - 1)  # put those k back in order
    reverse(nums, k, len(nums) - 1)  # and the rest

When Best isn’t best: if a new list is fine, Better is clearer. And Python’s collections.deque has rotate(k) built in, for a queue that rotates often.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Predict the outputWhat does this print?

   def shout(words):
       words = [w.upper() for w in words]
   
   names = ['ann', 'bo']
   shout(names)
   print(names)

   ['ANN', 'BO']['ann', 'bo']NoneAn error

   Check answer
2. Multiple choicenums is a list of n numbers. Which of these is O(1)?

   nums.insert(0, x)nums.pop()nums.pop(0)x in nums

   Check answer
3. Predict the outputWhat happens?

   s = 'cat'
   s[0] = 'b'
   print(s)

   It prints 'bat'It prints 'cat'TypeErrorIt prints 'b'

   Check answer
4. Multiple choiceWhich loop walks chars backwards without making a copy of it?

   for c in chars[::-1]:for c in reversed(chars):for c in sorted(chars, reverse=True):for c in list(chars)[::-1]:

   Check answer
5. Spot the bugThis looks like one loop. What does it cost for a word of n characters?

   def prefixes(word):
       return [word[:i] for i in range(1, len(word) + 1)]

   O(n)O(n log n)O(n²)O(1)

   Check answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1Why is nums[i] O(1)?Show answer
• Card 2What do insert(0, x) and pop(0) cost, and why?Show answer
• Card 3What does a slice like nums[a:b] cost?Show answer
• Card 4chars = chars[::-1] or chars[:] = chars[::-1]?Show answer
• Card 5How do you build a long string quickly?Show answer
• Card 6How do you reverse a list in place with O(1) memory?Show answer

Add 6 cards to my review deck

Cheat sheet

• A list is a row of boxes from index 0: a[i], a[-1] and len(a) are O(1).
• The end is cheap: append() and pop() are O(1) on average. The front isn’t: insert(0, x) and pop(0) are O(n).
• A slice is a new list or string: O(k) time and memory for k items.
• name = new_list moves a name. name[:] = new_list and name[i] = x change the list itself.
• Strings can’t change. Use list(s), change it, then ''.join(chars).
• Build long strings with ''.join(parts), not += in a loop.
• reversed(a) walks backwards without a copy.
• Two pointers from both ends: left, right = 0, len(a) - 1, then while left < right. O(n) time, O(1) memory.

Go deeper

• In the Python docs: what lists and strings can do, and the string methods.
• From the Python wiki: the time each list operation takes.
• Draw your own: the Reversing a list pictures on the DSA visualizer.
• Next on the DSA roadmap: hashing. Two Sum teaches it, and it uses two pointers too.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Say what indexing, appending, inserting at the front, slicing and joining cost, for lists and for strings
• Change the caller’s list in place, and tell that apart from pointing a name at a new list
• Walk a list from both ends with two pointers, using O(1) extra memory
• Build a long string with join, and say why strings can’t be changed in place

✓Mark as completeI already know this

Status: Not started