MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 4 – Two pointers

In-place compaction with reader–writer pointers

Keep at most k copies of each value in a sorted array, in place and in one pass: the problem, three examples and why deleting copies costs n² moves.

  • Beginner
  • 20 minutes
  • Examples run with Python 3.14.8 and Pyodide 314.0.7
  • By MySmartCoPilot
Free: The problem: keep at most k readings per minute, in place · Deleting each extra copy makes the work quadratic. With a pass: the other 9 sections and 3 interview answers, about 16 minutes.

What you will learn

  • Remove duplicates from a sorted array in place, in one pass
  • Implement keep-at-most-k compaction with a reader and a writer pointer
  • Prove that the writer never overwrites an item the reader still needs
  • Explain why deleting inside the loop costs O(n²) moves
  • Maintain the original order of the kept items, and handle k = 0

Before you start

What you’ll learn · Before you start

What you will learn

  • Remove duplicates from a sorted array in place, in one pass
  • Implement keep-at-most-k compaction with a reader and a writer pointer
  • Prove that the writer never overwrites an item the reader still needs
  • Explain why deleting inside the loop costs O(n²) moves
  • Maintain the original order of the kept items, and handle k = 0

Before you start

On this page

Removing duplicates from a sorted array in place takes one pass with reader–writer pointers: Two indices that both move right through one list: read visits every item once, and write marks where the next kept item goes, so the kept items gather at the front in their order. More in “Two pointers: converging and reader–writer”, even on a log of 1,000,000 readings, where deleting each extra copy can shift about 5 × 10¹¹ items. A reader visits every item in turn, and a writer marks the end of the part you keep: an item that stays is copied to the writer’s position, and the writer moves on.

Nothing is deleted from the middle of the list: one pass, O(n) time, O(1) extra memory, and the kept items stay in their order. The problem below is the general in-place compaction: Rearranging an array so that the items to keep fill its first part, in their original order, and returning the length of that part. Whatever lies after it is left over and ignored.: at most k copies of each value, plain duplicate removal when k is 1.

The problem: keep at most k readings per minute, in place

The problem

A weather station logs a reading every few seconds, and stamps lists the minute of each reading, sorted from earliest to latest. To thin the log, keep at most k readings per minute, in place: rearrange stamps so that its first w positions hold the kept stamps in their original order, and return w. What is left after position w does not matter. Limits: 1 ≤ n ≤ 1,000,000 stamps, 0 ≤ k ≤ 1,000,000, and every stamp is between 0 and 10⁹.

  1. stamps = [3, 3, 3, 5, 8, 8, 8, 8, 9] with k = 2 gives 6, and the first six positions become 3, 3, 5, 8, 8, 9.
  2. stamps = [4, 4, 4, 7] with k = 1 gives 2, for 4 and 7: plain duplicate removal.
  3. stamps = [1, 2, 2] with k = 0 gives 0, because nothing may be kept.

The first example, before and after the call:

The log 3, 3, 3, 5, 8, 8, 8, 8, 9 before the call, and after it: the first six positions hold 3, 3, 5, 8, 8, 9.Before: stamps, k = 2After: the call returns 6333588889stamps[:6], keptignored335889???

What the call must leave in the log for the first example, with k = 2

Text description of the diagram

The diagram has two rows, one under the other.

  1. Before the call, with k = 2, the nine stamps are 3, 3, 3, 5, 8, 8, 8, 8 and 9.
  2. After the call, which returns w = 6, the first six positions, stamps[:6], hold 3, 3, 5, 8, 8 and 9: at most two readings of each minute, in their original order. The last three positions, stamps[6:], are marked with question marks, because the problem does not say what they hold and nothing compares them.

Checkpoint

Check: Keep at most k readings per minute, in place

  1. One question With k = 3, the sorted log [4, 4, 9, 9, 9, 9, 12] is thinned in place. What does the call return?

    Type a number.

    A hint

    Count the readings each minute keeps, at most 3 of each.

    Show the answer

    Answer: 6 readings

    Minute 4 keeps both of its readings, minute 9 three of its four and minute 12 its one: 2 + 3 + 1 = 6. The first six positions then hold 4, 4, 9, 9, 9, 12.

Deleting each extra copy makes the work quadratic

A natural first answer walks the list and counts the copies of the current minute. When a reading is one too many, it deletes it where it stands, with del stamps[i], and looks at position i again. It is short and plainly correct, but the deletion hides a cost: removing an item from a Python list shifts every item after it one place left, which is why the Python tutorial calls lists slow to pop from the front. Step through it on the first example:

Interactive · line by line Deleting each extra copy from the first example Step through the brute force with k = 2. The lit line has just run; watch what each del does to the readings after the one it deletes.

Program · trace/delete_steps.py

stamps = [3, 3, 3, 5, 8, 8, 8, 8, 9]
k = 2
i = 0
copies = 0
moves = 0
while i < len(stamps):
    if i == 0 or stamps[i] != stamps[i - 1]:
        copies = 0
    if copies < k:
        copies += 1
        i += 1
    else:
        moves += len(stamps) - i - 1
        del stamps[i]
print(stamps, moves, "moves")

Variables

After line 15: stamps is [3, 3, 5, 8, 8, 9]; k is 2; i is 6; copies is 1; moves is 9.stamps303152838495k2i6copies1moves9
  • changed in this step

Printed so far

[3, 3, 5, 8, 8, 9] 9 moves

Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.

The drawing shows the variables when the program ends, and the program's 57 steps are listed below.

Line run 15
Next line end
Loop pass –
Every step as text
  1. Start. No line has run yet, so there are no variables. Python starts with line 1.
  2. Line 1. stamps = [3, 3, 3, 5, 8, 8, 8, 8, 9] makes stamps a list of 9 items.
  3. Line 2. k = 2 sets k to 2.
  4. Line 3. i = 0 sets i to 0.
  5. Line 4. copies = 0 sets copies to 0.
  6. Line 5. moves = 0 sets moves to 0.
  7. Line 6. while i < len(stamps): tests its condition: it is true (i is 0 and stamps is [3, 3, 3, 5, 8, 8, 8, 8, …]), so the body runs.
  8. Line 7. i == 0 or stamps[i] != stamps[i - 1] is true (i is 0 and stamps is [3, 3, 3, 5, 8, 8, 8, 8, …]), so the block under if i == 0 or stamps[i] != stamps[i - 1]: runs.
  9. Line 8. copies = 0 copies keeps its value, 0.
  10. Line 9. copies < k is true (copies is 0 and k is 2), so the block under if copies < k: runs.
  11. Line 10. copies += 1 changes copies from 0 to 1.
  12. Line 11. i += 1 changes i from 0 to 1.
  13. Line 6. while i < len(stamps): tests its condition: it is true (i is 1 and stamps is [3, 3, 3, 5, 8, 8, 8, 8, …]), so the body runs again (pass 2).
  14. Line 7. i == 0 or stamps[i] != stamps[i - 1] is false (i is 1 and stamps is [3, 3, 3, 5, 8, 8, 8, 8, …]), so Python skips the block under if i == 0 or stamps[i] != stamps[i - 1]:.
  15. Line 9. copies < k is true (copies is 1 and k is 2), so the block under if copies < k: runs.
  16. Line 10. copies += 1 changes copies from 1 to 2.
  17. Line 11. i += 1 changes i from 1 to 2.
  18. Line 6. while i < len(stamps): tests its condition: it is true (i is 2 and stamps is [3, 3, 3, 5, 8, 8, 8, 8, …]), so the body runs again (pass 3).
  19. Line 7. i == 0 or stamps[i] != stamps[i - 1] is false (i is 2 and stamps is [3, 3, 3, 5, 8, 8, 8, 8, …]), so Python skips the block under if i == 0 or stamps[i] != stamps[i - 1]:.
  20. Line 9. copies < k is false (copies is 2 and k is 2), so the else block runs.
  21. Line 13. moves += len(stamps) - i - 1 changes moves from 0 to 6.
  22. Line 14. del stamps[i] takes 3 out of stamps, from position 2: the 6 items after it move up one place. Key point The third 3 is one too many, so it is deleted where it stands. The six readings after it each move up one place, and i stays at 2 to read the 5 that moved into its slot.
  23. Line 6. while i < len(stamps): tests its condition: it is true (i is 2 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so the body runs again (pass 4).
  24. Line 7. i == 0 or stamps[i] != stamps[i - 1] is true (i is 2 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so the block under if i == 0 or stamps[i] != stamps[i - 1]: runs.
  25. Line 8. copies = 0 sets copies to 0 (it was 2).
  26. Line 9. copies < k is true (copies is 0 and k is 2), so the block under if copies < k: runs.
  27. Line 10. copies += 1 changes copies from 0 to 1.
  28. Line 11. i += 1 changes i from 2 to 3.
  29. Line 6. while i < len(stamps): tests its condition: it is true (i is 3 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so the body runs again (pass 5).
  30. Line 7. i == 0 or stamps[i] != stamps[i - 1] is true (i is 3 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so the block under if i == 0 or stamps[i] != stamps[i - 1]: runs.
  31. Line 8. copies = 0 sets copies to 0 (it was 1).
  32. Line 9. copies < k is true (copies is 0 and k is 2), so the block under if copies < k: runs.
  33. Line 10. copies += 1 changes copies from 0 to 1.
  34. Line 11. i += 1 changes i from 3 to 4.
  35. Line 6. while i < len(stamps): tests its condition: it is true (i is 4 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so the body runs again (pass 6).
  36. Line 7. i == 0 or stamps[i] != stamps[i - 1] is false (i is 4 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so Python skips the block under if i == 0 or stamps[i] != stamps[i - 1]:.
  37. Line 9. copies < k is true (copies is 1 and k is 2), so the block under if copies < k: runs.
  38. Line 10. copies += 1 changes copies from 1 to 2.
  39. Line 11. i += 1 changes i from 4 to 5.
  40. Line 6. while i < len(stamps): tests its condition: it is true (i is 5 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so the body runs again (pass 7).
  41. Line 7. i == 0 or stamps[i] != stamps[i - 1] is false (i is 5 and stamps is [3, 3, 5, 8, 8, 8, 8, 9]), so Python skips the block under if i == 0 or stamps[i] != stamps[i - 1]:.
  42. Line 9. copies < k is false (copies is 2 and k is 2), so the else block runs.
  43. Line 13. moves += len(stamps) - i - 1 changes moves from 6 to 8.
  44. Line 14. del stamps[i] takes 8 out of stamps, from position 6: the item after it moves up one place. The third 8 goes the same way, and the two readings after it move up one place.
  45. Line 6. while i < len(stamps): tests its condition: it is true (i is 5 and stamps is [3, 3, 5, 8, 8, 8, 9]), so the body runs again (pass 8).
  46. Line 7. i == 0 or stamps[i] != stamps[i - 1] is false (i is 5 and stamps is [3, 3, 5, 8, 8, 8, 9]), so Python skips the block under if i == 0 or stamps[i] != stamps[i - 1]:.
  47. Line 9. copies < k is false (copies is 2 and k is 2), so the else block runs.
  48. Line 13. moves += len(stamps) - i - 1 changes moves from 8 to 9.
  49. Line 14. del stamps[i] takes 8 out of stamps, from position 5: the item after it moves up one place.
  50. Line 6. while i < len(stamps): tests its condition: it is true (i is 5 and stamps is [3, 3, 5, 8, 8, 9]), so the body runs again (pass 9).
  51. Line 7. i == 0 or stamps[i] != stamps[i - 1] is true (i is 5 and stamps is [3, 3, 5, 8, 8, 9]), so the block under if i == 0 or stamps[i] != stamps[i - 1]: runs.
  52. Line 8. copies = 0 sets copies to 0 (it was 2).
  53. Line 9. copies < k is true (copies is 0 and k is 2), so the block under if copies < k: runs.
  54. Line 10. copies += 1 changes copies from 0 to 1.
  55. Line 11. i += 1 changes i from 5 to 6.
  56. Line 6. while i < len(stamps): tests its condition: it is false (i is 6 and stamps is [3, 3, 5, 8, 8, 9]), so the loop ends.
  57. Line 15. print(stamps, moves, "moves") prints [3, 3, 5, 8, 8, 9] 9 moves. That was the last line, so the program ends. Three deletions moved 6 + 2 + 1 = 9 readings. When every reading shares one minute, each deletion moves almost the whole list, about n²/2 moves in all.

Deleting each extra copy, with the moves counted Python · brute/delete_each.py 
"""The first answer most people write: delete each reading that is one too many, where it stands.

Deleting from a Python list moves every later item one place left, so the function also counts those moves.
"""


def keep_at_most_slow(stamps, k):
    """Keeps at most k readings per minute; returns the new length and the number of items moved."""
    moves = 0
    i = 0
    copies = 0  # copies kept so far of the minute stamps[i - 1]
    while i < len(stamps):
        if i == 0 or stamps[i] != stamps[i - 1]:
            copies = 0
        if copies < k:
            copies += 1
            i += 1
        else:
            moves += len(stamps) - i - 1  # del shifts every item after position i
            del stamps[i]
    return len(stamps), moves


for stamps, k in [([3, 3, 3, 5, 8, 8, 8, 8, 9], 2), ([4, 4, 4, 7], 1), ([1, 2, 2], 0)]:
    log = list(stamps)
    w, moves = keep_at_most_slow(log, k)
    print(f"k = {k}: {stamps} -> {w}, kept {log}, {moves} moves")

print()
print("The worst case: every reading in the same minute, k = 1")
for n in [1_000, 2_000, 4_000, 8_000]:
    w, moves = keep_at_most_slow([7] * n, 1)
    print(f"n = {n:>5,}: {moves:>12,} moves")
n = 1_000_000
print(f"n = {n:,} would need {(n - 2) * (n - 1) // 2:,} moves")

Output

k = 2: [3, 3, 3, 5, 8, 8, 8, 8, 9] -> 6, kept [3, 3, 5, 8, 8, 9], 9 moves
k = 1: [4, 4, 4, 7] -> 2, kept [4, 7], 3 moves
k = 0: [1, 2, 2] -> 0, kept [], 3 moves

The worst case: every reading in the same minute, k = 1
n = 1,000:      498,501 moves
n = 2,000:    1,997,001 moves
n = 4,000:    7,994,001 moves
n = 8,000:   31,988,001 moves
n = 1,000,000 would need 499,998,500,001 moves

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 delete_each.py

Python Online Compiler Run the deleting version on a log of your own and watch the count of moves grow.

In the worst case every reading shares one minute: each deletion of this brute force: The simplest method that is plainly correct, usually trying every possibility. Said first in a round, it confirms what the problem asks, and later it checks a faster version's answers. More in “A six-step method for any coding problem” shifts almost the whole list, so the moves add up to about n²/2 and quadruple when n doubles, as the counts show. A million stamps need about 5 × 10¹¹ moves, against a million reads for one pass.

Checkpoint

Check: Deleting each extra copy, and what it costs

  1. One question The delete-each brute force runs on 2,000 readings that all share one minute, with k = 1. How many items does it move, by the recorded count?

    Type a number.

    A hint

    Each deletion happens at position 1 and moves every reading after it.

    Show the answer

    Answer: 1997001 moves

    The first reading stays and each later one is deleted at position 1, moving everything after it: 1,998 items, then 1,997, down to 0. Their sum is 1,998 × 1,999 ÷ 2 = 1,997,001, as the recorded output shows, four times the count for 1,000 readings.

What to notice: kept readings only move towards the front

Two facts point to a faster method. A kept reading only ever moves towards the front, and a dropped one is never needed again, so you can copy each kept reading forward instead of deleting the others. And because the log is sorted, the copies of one minute sit next to each other, so whether a reading is one too many can be decided by looking a fixed distance back into the part already kept. Together they let every item be touched once, as the figure shows:

The log 3, 3, 3, 5, 8, 8, 8, 8, 9 above the kept 3, 3, 5, 8, 8, 9, with an arrow from each kept reading to its new slot, never to the right.The first example, k = 2minute 3minute 8012345678333588889335889???012345678Arrows: kept readings move forwardDashed: an extra copy or a leftover slot

In the first example, every kept reading moves towards the front or stays

Text description of the diagram

The diagram has two rows of nine slots, numbered 0 to 8, for the first example with k = 2.

  1. The upper row is the log before the call: 3, 3, 3, 5, 8, 8, 8, 8 and 9. Brackets above it mark the copies of minute 3 in slots 0 to 2 and of minute 8 in slots 4 to 7: because the log is sorted, the copies of one minute sit side by side. The third 3 and the third and fourth 8 are dashed: they are copies too many.
  2. The lower row is the log after the call: 3, 3, 5, 8, 8 and 9 in slots 0 to 5, and three dashed slots, 6 to 8, whose values no longer matter.
  3. An arrow runs from each kept reading to its slot in the lower row: slot 0 to 0, 1 to 1, 3 to 2, 4 to 3, 5 to 4 and 8 to 5. Every arrow points straight down or to the left, so a kept reading only ever moves towards the front. The dashed readings have no arrow: once dropped, they are never needed again.

Checkpoint

Check: Kept readings move forward, copies sit together

  1. One question Why can a faster method copy the kept readings forward instead of deleting the others?

    Choose one answer.

    Show the answer

    Answer: A kept reading only ever moves towards the front, and a dropped one is never needed again

    In the figure every arrow points down or to the left: each kept reading moves towards the front or stays, and the dashed copies are never read again. That is why copying forward can replace deleting.

These questions start with the idea your answers show is weakest.

Practice that adapts to you

Practise this lesson

9 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 9 After the call returns w, what must the first w positions of stamps hold?

    Choose one answer.

    Show the answer

    Answer: The kept readings, at most k per minute, in their original order

    The problem asks for the kept stamps in their original order in the first w positions, and for w as the return value. What lies after position w does not matter.

  2. Question 2 of 9 With k = 1, what does the call return for [5, 5, 6, 6, 6, 9]?

    Type a number.

    A hint

    With k = 1 each minute keeps one reading.

    Show the answer

    Answer: 3 readings

    Each of the minutes 5, 6 and 9 keeps one reading, so the first three positions become 5, 6, 9 and the call returns 3.

  3. Question 3 of 9 A caller prints the whole list after the call and sees old readings after the kept ones. Is the function wrong?

    Choose one answer.

    Show the answer

    Answer: No: what lies after position w does not matter, so the caller should use only the first w positions

    The contract is the first w positions and the return value. A caller that wants a shorter list cuts it after the call.

  4. Question 4 of 9 What does del stamps[i] do to the readings after position i?

    Choose one answer.

    Show the answer

    Answer: Each one moves one place towards the front

    Deleting from a Python list closes the gap by moving every later item one place left, which is why the Python tutorial calls lists slow to pop from the front.

  5. Question 5 of 9 How many readings does the brute force move on the first example, [3, 3, 3, 5, 8, 8, 8, 8, 9] with k = 2?

    Type a number.

    A hint

    Count the readings after each of the three deletions.

    Show the answer

    Answer: 9 moves

    Deleting the third 3 moves the six readings after it, the third 8 moves two and the fourth 8 one: 6 + 2 + 1 = 9, as the recorded run prints.

  6. Question 6 of 9 Why does the brute force fail at the limit of 10⁶ readings, when its code is short and correct?

    Choose one answer.

    Show the answer

    Answer: On a log of one minute it makes about 5 × 10¹¹ moves, far beyond a time limit

    When every reading shares one minute, each deletion moves almost the whole list, about n²/2 moves in all: 5 × 10¹¹ for a million readings, against a million reads for one pass.

  7. Question 7 of 9 Why do the copies of one minute sit next to each other in the log?

    Choose one answer.

    Show the answer

    Answer: Because the log is sorted from earliest to latest

    In a sorted log every reading between two copies of a minute has that same minute, so the copies form one run.

  8. Question 8 of 9 Thinning the first example with k = 2, the part kept so far is [3, 3, 5, 8, 8] and the next reading is an 8. What happens to it, and what decides?

    Choose one answer.

    Show the answer

    Answer: It is dropped: the kept part already ends with two 8s, the most minute 8 may keep

    Because the log is sorted, the 8s kept so far sit at the end of the kept part. Two are there already, so a third would break the limit of k = 2: the end of the kept part decides, without counting.

  9. Question 9 of 9 Suppose the log were not sorted. Which fact behind the faster method would no longer hold?

    Choose one answer.

    Show the answer

    Answer: The copies of a minute sitting next to each other, so a look a fixed distance back could no longer decide

    Moving forward does not depend on sorting, but finding the copies of a minute at the end of the kept part does. Unsorted, the faster method needs another way to count copies.

Reader and writer in one pass, step by step Pro

In this part:

  • A dry run on the first example, one row per reading
  • The invariant, and a proof that the kept part is always right
  • The code in 14 languages
  • Two bugs that look right, reproduced
  • Deleting against copying, measured
  • Variants: filters, zeros moved to the end, and minutes seen once
  • Practise: keep at most k copies
    • Keep at most k copies of each value, in place
    • A practice set with sample answers
  • Interview questions
    • To keep at most k copies of each value of a sorted array in place, a candidate's loop keeps a[r] when r < k or a[r] != a[r − k], and writes kept values forward. Is that right? Find an input that decides it, and explain what the test really checks.
    • A Python solution removes duplicates from a sorted list by calling del a[i] whenever a[i] equals a[i − 1]. It passes the sample tests and times out on a hidden test with a million items. Explain the cost, estimate the time, and fix it.
    • The same task on unsorted data: keep at most k copies of each value of an array of a million integers, in place, keeping the original order of the kept items. What changes, what does it cost in time and memory, and what can you offer if extra memory must be O(1)?
  • Key takeaways

3 diagrams · 7 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 47 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

in-place compaction
Rearranging an array so that the items to keep fill its first part, in their original order, and returning the length of that part. Whatever lies after it is left over and ignored.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. JavaScript & TypeScript Online Compiler Write, run and debug JS or TS snippets — safely sandboxed, nothing to install.

Report a problem with this lesson