These are the notes for Python Coding Questions, episode 8, the fourth round of list questions. Three questions: two-sum (probably the most asked coding question in the world), moving zeros to the end while keeping the order, and a trap that catches even experienced developers: changing a list while you loop over it. Along the way you'll see how a dictionary turns O(n²) into O(n), how two pointers keep the order in O(1) space, and why removing items inside a for loop silently skips some of them.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine, so compare them, don't copy them.
Q1: Two-sum
Real-life example: you have a 500-rupee gift voucher, and the shop says: buy exactly two items, worth exactly 500. The prices are 120, 250, 380 and 130. 120 + 380 = 500, so the answer is their positions, 0 and 2. A smart shopper, looking at 380, asks one question: have I already seen something for 120?
| Input (prices, target) | Output |
|---|---|
[120, 250, 380, 130], 500 |
(0, 2) |
[250, 90, 410], 500 |
(1, 2) (90 + 410), not (0, 0) |
[250, 300], 500 |
None (no pair) |
[250, 250], 500 |
(0, 1) (two different items, same price) |
Ask the interviewer: do they want positions or values? Can the same item be used twice? (Usually no.) What if there is no pair? What if there are several? (Usually any one pair.)
Attempt 1: two loops over every i and j
def two_sum(prices, target):
for i in range(len(prices)):
for j in range(len(prices)):
if prices[i] + prices[j] == target:
return i, j
print(two_sum([120, 250, 380, 130], 500)) # a 500-rupee voucher
print(two_sum([250, 90, 410], 500))
Output:
(0, 2)
(0, 0)
Why it's wrong: j also starts at 0, so it can land on the same position as i. At i = 0, j = 0 the check is 250 + 250 = 500, and the function returns (0, 0): the same 250-rupee item bought twice. The real answer, 90 + 410, is never reached. Also, if no pair works the function falls off the end and returns None by accident, not on purpose.
Attempt 2: start j at i + 1
import time
def two_sum(prices, target):
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
if prices[i] + prices[j] == target:
return i, j
return None
print(two_sum([120, 250, 380, 130], 500), two_sum([250, 90, 410], 500))
print(two_sum([250, 300], 500))
prices = list(range(1, 8_001))
start = time.perf_counter()
print(two_sum(prices, 15_999), f"{time.perf_counter() - start:.3f} s")
Output (one run):
(0, 2) (1, 2)
None
(7998, 7999) 1.579 s
Why it works: range(i + 1, len(prices)) checks every pair once, and never an item with itself. return None says clearly "no pair".
Why it's slow: for each price, the inner loop tries every later one. That's about n²/2 pairs: for 8,000 prices, about 32 million additions and comparisons. The test puts the answer at the very end (7,999 + 8,000 = 15,999), which is the worst case. The video saw about a second; your machine will differ.
- Time O(n²), space O(1). This is the brute force: try every possibility.
The fix: one pass with a dictionary
For each price p, work out what you need: target - p. Look it up in a dictionary of prices you've already seen. If it's there, you're done. If not, store this price with its position, and move on.
import time
def two_sum(prices, target):
seen = {} # price -> index
for j, p in enumerate(prices):
need = target - p
if need in seen: # check first...
return seen[need], j
seen[p] = j # ...then store
return None
print(two_sum([120, 250, 380, 130], 500), two_sum([250, 90, 410], 500))
print(two_sum([250, 300], 500), two_sum([250, 250], 500))
prices = list(range(1, 8_001))
start = time.perf_counter()
print(two_sum(prices, 15_999), f"{time.perf_counter() - start:.4f} s")
Output (one run):
(0, 2) (1, 2)
None (0, 1)
(7998, 7999) 0.0008 s
Same answers, None for no pair, (0, 1) for the two 250-rupee items, and 8,000 prices in under a millisecond: thousands of times faster than the brute force.
Why it works: need in seen is a hash lookup: the dictionary jumps straight to where the key would be, instead of scanning. That's O(1) on average, so the whole loop is O(n) time. The dictionary can hold up to n prices: O(n) extra space. We trade memory for speed (a space-time trade-off).
enumerate(prices) gives (index, value) pairs, so j, p is the position and the price together.
Walking through the dictionary
[120, 250, 380, 130], target 500. Adding a print inside the loop:
def two_sum(prices, target):
seen = {}
for j, p in enumerate(prices):
need = target - p
print(f"j={j} p={p} need={need} seen={seen}", "-> found" if need in seen else "")
if need in seen:
return seen[need], j
seen[p] = j
return None
print(two_sum([120, 250, 380, 130], 500))
Output:
j=0 p=120 need=380 seen={}
j=1 p=250 need=250 seen={120: 0}
j=2 p=380 need=120 seen={120: 0, 250: 1} -> found
(0, 2)
| j | p | need = 500 − p | seen before the check |
need in seen? | Action |
|---|---|---|---|---|---|
| 0 | 120 | 380 | {} |
no | store 120: 0 |
| 1 | 250 | 250 | {120: 0} |
no | store 250: 1 |
| 2 | 380 | 120 | {120: 0, 250: 1} |
yes, at 0 | return (0, 2) |
130 is never looked at: the loop stops as soon as a pair is found.
Why "check first, then store"
If we store the price before checking, a single 250 finds itself:
def two_sum_store_first(prices, target):
seen = {}
for j, p in enumerate(prices):
seen[p] = j # store first (wrong)
need = target - p
if need in seen:
return seen[need], j
return None
print(two_sum_store_first([250], 500))
print(two_sum_store_first([250, 90, 410], 500))
Output:
(0, 0)
(0, 0)
The same bug as attempt 1. Checking first means seen only holds earlier positions, so the pair is always two different items. It also handles duplicates: for [250, 250], the first 250 is stored, the second finds it, and the answer is (0, 1).
Follow-up: if the prices were sorted, there's a third answer with two pointers and O(1) space (see practice question 3 below; the full episode on it is episode 26).
Q2: Move zeros to the end, keeping the order
Real-life example: a library shelf with gaps between the books. You push the books to the left without changing their order, and the gaps end up on the right. A librarian does it with two hands: one hand reads each slot, the other places each book in the next free spot on the left.
| Input | Output (same list, changed in place) |
|---|---|
[0, 1, 0, 3, 12] |
[1, 3, 12, 0, 0] |
[0, 0, 1] |
[1, 0, 0] |
[4, 2] (no zeros) |
[4, 2] |
[0, 0] (all zeros) |
[0, 0] |
[] |
[] |
"In place" means change the given list itself, without building a second list.
Attempt 1: swap each zero with the last item
Borrowing two pointers from reversing: i from the front, j from the back.
def move_zeros(nums):
i, j = 0, len(nums) - 1
while i < j:
if nums[i] == 0:
nums[i], nums[j] = nums[j], nums[i] # zero to the back
j -= 1
else:
i += 1
shelf = [0, 1, 0, 3, 12]
move_zeros(shelf)
print(shelf)
Output:
[12, 1, 3, 0, 0]
Why it's wrong: the zeros are at the end, but 12 jumped to the front. Swapping with the far end moves a book from the back to the front. The question said keep the order. Read the question twice.
Attempt 2: remove a zero and append one
import time, random
def move_zeros_remove(nums):
for x in nums:
if x == 0:
nums.remove(x) # finds and deletes the first 0
nums.append(0)
shelf = [0, 1, 0, 3, 12]
move_zeros_remove(shelf)
print(shelf)
random.seed(5)
data = [random.choice([0, 0, 1, 2, 3]) for _ in range(30_000)]
nums = data[:]
start = time.perf_counter()
move_zeros_remove(nums)
print("remove:", nums[:5], f"{time.perf_counter() - start:.3f} s")
Output (one run):
[1, 3, 12, 0, 0]
remove: [3, 1, 1, 3, 2] 1.362 s
Why it's correct but slow: nums.remove(0) searches for the first 0 and then shifts every item after it one slot left. That's O(n), and it happens for every zero (about 2 in 5 of the 30,000 items here), so the whole thing is O(n²). The video saw about a second; yours will differ.
It also changes the list while looping over it. Here it happens to give the right answer (every removal is matched by an append, so the length never changes), but that is luck, not design. Q3 shows when it doesn't work.
random.seed(5) makes the "random" list the same on every run, and data[:] is a copy, so both timings use identical input.
The fix: read and write pointers
import time, random
def move_zeros(nums):
write = 0 # next place for a non-zero
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
for shelf in [[0, 1, 0, 3, 12], [0, 0, 1], [4, 2], [0, 0], []]:
move_zeros(shelf)
print(shelf)
random.seed(5)
data = [random.choice([0, 0, 1, 2, 3]) for _ in range(30_000)]
nums = data[:]
start = time.perf_counter()
move_zeros(nums)
print("pointers:", nums[:5], f"{time.perf_counter() - start:.4f} s")
Output (one run):
[1, 3, 12, 0, 0]
[1, 0, 0]
[4, 2]
[0, 0]
[]
pointers: [3, 1, 1, 3, 2] 0.0014 s
Every shelf is right: order kept, all zeros, no zeros, and empty. And 30,000 items in about a millisecond, with the same first five values as attempt 2: roughly a thousand times faster.
Why it works: write is the next free spot on the left; read walks over every slot. When read finds a book, it is swapped into the write spot and write moves forward. write never passes read, and books are placed in the order read meets them, so the order stays. The swap (instead of a plain copy) leaves the zeros behind at the end.
- Time O(n) (one pass), space O(1) (two variables). Interviewers call this the fast and slow pointer pattern: both pointers move in the same direction, one faster.
The pointer step by step
[0, 1, 0, 3, 12], printing after each step:
def move_zeros(nums):
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
print(f"read={read} write={write} {nums}")
move_zeros([0, 1, 0, 3, 12])
Output:
read=0 write=0 [0, 1, 0, 3, 12]
read=1 write=1 [1, 0, 0, 3, 12]
read=2 write=1 [1, 0, 0, 3, 12]
read=3 write=2 [1, 3, 0, 0, 12]
read=4 write=3 [1, 3, 12, 0, 0]
| read | nums[read] | write before | Action | List after | write after |
|---|---|---|---|---|---|
| 0 | 0 | 0 | gap: skip | [0, 1, 0, 3, 12] |
0 |
| 1 | 1 | 0 | swap slots 0 and 1 | [1, 0, 0, 3, 12] |
1 |
| 2 | 0 | 1 | gap: skip | [1, 0, 0, 3, 12] |
1 |
| 3 | 3 | 1 | swap slots 1 and 3 | [1, 3, 0, 0, 12] |
2 |
| 4 | 12 | 2 | swap slots 2 and 4 | [1, 3, 12, 0, 0] |
3 |
At the end, write = 3 = the number of non-zero books.
Q3: The list-modified-while-looping trap
Real-life example: a teacher walks along a row of students with roll numbers 2, 4, 6, 7 and 8, and sends every even number out. Roll number 2 leaves; everyone slides one seat left to close the gap, so 4 is now in seat 0. But the teacher steps forward to seat 1, as planned. She never looks at 4.
| Input | Expected (remove evens) |
|---|---|
[2, 4, 6, 7, 8] |
[7] |
The obvious attempt: remove inside the loop
nums = [2, 4, 6, 7, 8]
for x in nums:
if x % 2 == 0:
nums.remove(x)
print(nums)
Output:
[4, 7]
Why it's wrong: 4 is even and it's still there. No error, just a wrong answer, which is the worst kind of bug.
Watching the loop
Print the index, the item and the list at every step:
nums = [2, 4, 6, 7, 8]
for i, x in enumerate(nums):
print(f"i={i} x={x} list={nums}")
if x % 2 == 0:
nums.remove(x)
print(nums)
Output:
i=0 x=2 list=[2, 4, 6, 7, 8]
i=1 x=6 list=[4, 6, 7, 8]
i=2 x=8 list=[4, 7, 8]
[4, 7]
| Step (hidden index) | List at that moment | Item seen | Action | List after |
|---|---|---|---|---|
| 0 | [2, 4, 6, 7, 8] |
2 | even: remove | [4, 6, 7, 8] (4 slid to index 0) |
| 1 | [4, 6, 7, 8] |
6 (4 skipped) | even: remove | [4, 7, 8] (7 slid to index 1) |
| 2 | [4, 7, 8] |
8 (7 skipped) | even: remove | [4, 7] |
| 3 | [4, 7] |
(length is 2) | loop ends | [4, 7] |
Why: a for loop over a list keeps a hidden position counter and moves it forward by one every step. Removing an item shifts everything after it back by one. So the item right after every removal is skipped. 7 was skipped too, but it is odd, so the bug only shows on 4.
Dictionaries are stricter: RuntimeError
A shop's stock: delete every item with zero in stock, while looping.
stock = {"pen": 0, "book": 5, "bag": 0}
for item in stock:
if stock[item] == 0:
del stock[item]
print(stock)
Output:
Traceback (most recent call last):
File "main.py", line 2, in <module>
for item in stock:
^^^^^
RuntimeError: dictionary changed size during iteration
Python refuses outright. Here a crash is kinder than a silent wrong answer. Sets do the same (RuntimeError: Set changed size during iteration). Lists don't check, which is why the list version just gives a wrong answer.
The rule for both: never change the size of a collection while looping over it.
Four safe fixes (and one for the dictionary)
nums = [2, 4, 6, 7, 8]
print([x for x in nums if x % 2 != 0]) # 1. a new list
same = nums
nums[:] = [x for x in nums if x % 2 != 0] # 2. same list, new contents
print(same)
nums = [2, 4, 6, 7, 8]
for x in nums[:]: # 3. loop over a copy
if x % 2 == 0:
nums.remove(x)
print(nums)
nums = [2, 4, 6, 7, 8]
for i in range(len(nums) - 1, -1, -1): # 4. walk backwards
if nums[i] % 2 == 0:
del nums[i]
print(nums)
stock = {"pen": 0, "book": 5, "bag": 0}
for item in list(stock): # a copy of the keys
if stock[item] == 0:
del stock[item]
print(stock)
Output:
[7]
[7]
[7]
[7]
{'book': 5}
- A comprehension builds a new list of the items to keep. The clearest, O(n).
- Slice assignment
nums[:] = ...puts the new contents into the same list object, so other names for it (same) see the change. O(n). - Loop over a copy:
nums[:]is a copy, so the loop's list never changes;removechanges only the original. Correct, butremoveis O(n) each time: O(n²), like Q2. - Walk backwards: deleting at
ishifts only the items afteri, which you've already seen. O(n²) in the worst case too (eachdelshifts the tail). - For a dict,
list(stock)makes a list of the keys first; you loop over that list and delete from the dict freely.
Use the comprehension; use slice assignment when other code holds the same list. Here's why that difference matters:
nums = [2, 4, 6, 7, 8]
same = nums
nums = [x for x in nums if x % 2 != 0] # a NEW list, only nums points to it
print(nums, same)
nums = [2, 4, 6, 7, 8]
same = nums
nums[:] = [x for x in nums if x % 2 != 0] # the SAME list gets new contents
print(nums, same, nums is same)
Output:
[7] [2, 4, 6, 7, 8]
[7] [7] True
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
for j in range(len(prices)) |
(0, 0) for [250, 90, 410] |
j can equal i: one item twice |
range(i + 1, len(prices)) |
| two loops over every pair | ~1-2 s for 8,000 prices (varies) | O(n²) | a dict of seen prices, O(n) |
| store, then check | [250], 500 → (0, 0) |
the price finds itself | check need first, then store |
| swap a zero with the end | [12, 1, 3, 0, 0] |
order broken | read/write pointers |
remove(0) + append(0) in a loop |
correct, but ~1 s on 30,000 items (varies) | remove is O(n): O(n²) total |
read/write pointers, O(n) |
nums.remove(x) in for x in nums |
[4, 7]: 4 skipped, no error |
items slide under the hidden index | a comprehension, or loop over nums[:] |
del d[k] while looping d |
RuntimeError: dictionary changed size during iteration |
the dict's size changed | for k in list(d): |
s.remove(x) while looping a set |
RuntimeError: Set changed size during iteration |
the set's size changed | for x in list(s): or a set comprehension |
nums = [...] when others share the list |
the other name still has the old list | a new object, not a change | nums[:] = [...] |
Your turn: count all pairs with a target sum (solution)
Not just one pair: count all pairs i < j with nums[i] + nums[j] == target. For [1, 5, 7, -1, 5] and target 6 there are 3: 1 + 5, 1 + the other 5, and 7 + (−1).
Solution
Brute force: every pair once, j from i + 1, count instead of return. O(n²) time, O(1) space.
One pass: keep a Counter of the values seen so far. At each x, every earlier value equal to target - x makes one pair, so add seen[target - x]. Then count x itself. Check first, then store, exactly like two-sum, so an item never pairs with itself. O(n) time, O(n) space.
from collections import Counter
def count_pairs_brute(nums, target):
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
count += 1
return count
def count_pairs(nums, target):
seen = Counter() # value -> how many times seen so far
count = 0
for x in nums:
count += seen[target - x] # pairs with every earlier partner
seen[x] += 1 # check first, then store
return count
for nums, target in [([1, 5, 7, -1, 5], 6), ([3, 3, 3], 6), ([1, 2], 10), ([], 6)]:
print(nums, target, "->", count_pairs_brute(nums, target), count_pairs(nums, target))
Output:
[1, 5, 7, -1, 5] 6 -> 3 3
[3, 3, 3] 6 -> 3 3
[1, 2] 10 -> 0 0
[] 6 -> 0 0
Walking [1, 5, 7, -1, 5]: at 1 nothing (need 5, seen 0 times); at 5, need 1, seen once → 1; at 7 nothing; at −1, need 7, seen once → 2; at the last 5, need 1, seen once → 3. [3, 3, 3] gives 3 pairs: (0, 1), (0, 2), (1, 2). A Counter returns 0 for a missing key instead of raising KeyError, which keeps the code short.
Practice questions (with solutions)
1. Move zeros to the front, keeping the order of the rest. [0, 1, 0, 3, 12] → [0, 0, 1, 3, 12].
Solution
The same read/write pointers, walking from the right: write is the next free spot on the right.
def move_zeros_front(nums):
write = len(nums) - 1 # next free spot on the right
for read in range(len(nums) - 1, -1, -1):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write -= 1
for shelf in [[0, 1, 0, 3, 12], [1, 2, 0], [0, 0], []]:
move_zeros_front(shelf)
print(shelf)
Output:
[0, 0, 1, 3, 12]
[0, 1, 2]
[0, 0]
[]
O(n) time, O(1) space. The non-zeros are placed right-to-left in the order the reader meets them from the right, so their order is kept.
2. Remove every copy of a value in place and return the new length. [3, 2, 2, 3, 4], value 3 → 3 (the first 3 slots are [2, 2, 4]).
Solution
Read/write pointers again: copy every item that is not the value into the write spot. What's after the new length doesn't matter.
def remove_value(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # the new length
nums = [3, 2, 2, 3, 4]
k = remove_value(nums, 3)
print(k, nums[:k], nums)
nums = [5, 5]
k = remove_value(nums, 5)
print(k, nums[:k])
Output:
3 [2, 2, 4] [2, 2, 4, 3, 4]
0 []
O(n) time, O(1) space. Compare: while val in nums: nums.remove(val) is O(n²). If you really need the list shortened, add del nums[k:] at the end.
3. Two-sum on a sorted list, in O(1) space. [120, 130, 250, 380], 500 → (0, 3).
Solution
Two pointers from both ends. If the sum is too small, the only way to grow it is to move lo right; if too big, move hi left. Every step rules out one item for good.
def two_sum_sorted(prices, target):
lo, hi = 0, len(prices) - 1
while lo < hi:
total = prices[lo] + prices[hi]
if total == target:
return lo, hi
if total < target:
lo += 1 # need a bigger sum
else:
hi -= 1 # need a smaller sum
return None
print(two_sum_sorted([120, 130, 250, 380], 500))
print(two_sum_sorted([90, 250, 410], 500))
print(two_sum_sorted([250, 300], 500), two_sum_sorted([250, 250], 500))
Output:
(0, 3)
(0, 2)
None (0, 1)
O(n) time, O(1) space (no dictionary). lo < hi means an item is never paired with itself. It only works because the list is sorted; sorting an unsorted list first costs O(n log n) and loses the original positions.
Quick quiz
What does this print?
nums = [1, 1, 2, 3]
for x in nums:
if x == 1:
nums.remove(x)
print(nums)
(A) [1, 2, 3] (B) [2, 3] (C) [3] (D) RuntimeError
Answer
(A). Step 0 sees the first 1 and removes it; the list becomes [1, 2, 3]. Step 1 looks at index 1, which is now 2, so the second 1 (now at index 0) is skipped. Lists don't raise an error for this; only dicts and sets do.
[1, 2, 3]
Interview questions
- What's the brute force for two-sum, and its complexity? Two loops,
jfromi + 1: O(n²) time, O(1) space. - How do you solve two-sum in O(n)? One pass with a dict
value -> index: for eachp, check whethertarget - pis in the dict, then storep. O(n) time on average, O(n) space. - Why check before storing? So an item can't pair with itself (
[250], 500 would give(0, 0)), and so duplicates like[250, 250]give(0, 1). - Move zeros to the end, keeping the order, in place? Read/write pointers: swap each non-zero into the
writespot and advancewrite. O(n) time, O(1) space. - Why is calling
remove()in a loop slow?removesearches and then shifts every later item: O(n) each, O(n²) total. - What happens if you remove items from a list, or a dict, while looping over it? A list gives no error, but the item after each removal is skipped, because the loop's hidden index moves forward while the items slide back. A dict raises
RuntimeError: dictionary changed size during iteration; loop overlist(d)instead, or build a new dict with a comprehension. nums = [...]vsnums[:] = [...]? The first makesnumspoint to a new list; the second changes the existing list, so every other reference sees it.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Two-sum | Find two positions whose values add up to a target | [120, 250, 380], 500 → (0, 2) |
| Target | The sum we're looking for | 500 (the voucher) |
| Brute force | Try every possibility, no cleverness | every pair i, j |
| Nested loop | A loop inside another loop | for i ...: for j ...: |
| Pair (i < j) | Two different positions, each pair counted once | range(i + 1, n) |
enumerate |
Gives (index, value) pairs while looping |
for j, p in enumerate(prices) |
| Dictionary (dict) | Key → value store with fast lookup | seen = {120: 0} |
| Hash lookup | Jumping straight to a key's slot via its hash, no scanning | need in seen |
| O(1) average | Constant time in the usual case, regardless of size | dict lookup |
| O(n), O(n²) | Time grows like n, or like n × n | one pass; every pair |
| Space-time trade-off | Use more memory to save time | the seen dict |
Counter |
A dict that counts things; missing keys give 0 | Counter()[5] → 0 |
| In place | Change the given list itself, no second list | move_zeros(shelf) |
| Read/write pointers | One index reads every slot, another marks where the next kept item goes | read, write |
| Fast and slow pointers | Two indexes moving the same way at different speeds | read fast, write slow |
| Two pointers from both ends | One index from the front, one from the back | sorted two-sum |
| Swap | Exchange two values in one line | a, b = b, a |
list.remove(x) |
Deletes the first x, shifting later items left: O(n) |
nums.remove(0) |
list.append(x) |
Adds x at the end: O(1) |
nums.append(0) |
del nums[i] |
Deletes the item at index i |
walking backwards |
del d[k] |
Deletes key k from a dict |
del stock["pen"] |
| Iteration | Going through a collection's items one by one | for x in nums |
| Hidden index | The position counter a for loop keeps over a list |
why 4 was skipped |
| Comprehension | Build a new list from a loop in one expression | [x for x in nums if x % 2] |
| Slice assignment | Replace a list's contents in place | nums[:] = [...] |
Copy nums[:] |
A new list with the same items | for x in nums[:] |
list(d) |
A list of a dict's keys (a snapshot) | for item in list(stock) |
| Reference / alias | Two names for the same object | same = nums |
RuntimeError |
Raised when something goes wrong while running, here a resized dict or set | dictionary changed size during iteration |
random.seed() |
Makes random numbers repeatable | random.seed(5) |
time.perf_counter() |
High-resolution stopwatch | timing the brute force |
Summary
- Two-sum: brute force needs
jfromi + 1(else the same item is used twice) and is O(n²). One pass with a dictprice -> indexis O(n): computeneed = target - p, check first, then store. The dict trades O(n) space for time. - Move zeros, keeping the order: swapping with the end breaks the order;
remove+appendis O(n²). Read/write pointers do it in one pass, O(n) time and O(1) space, and keep the order becausewritenever passesread. - The loop trap: removing from a list while looping skips the item after each removal, silently. Dicts and sets raise
RuntimeError. Never resize what you loop over: build a new list with a comprehension (ornums[:] = ...), loop over a copy, walk backwards, or loop overlist(d).
Next episode: List questions V: merge two sorted lists, intersection and union with and without duplicates, and the maximum subarray sum with Kadane's algorithm.