Skip to content

Volume ITechnology

4.0.18 — Remove Duplicates and Move Zeros: the Write Pointer ​

Classic · Easy · LeetCode 26 (Remove Duplicates from Sorted Array), LeetCode 27 (Remove Element), LeetCode 283 (Move Zeroes)

The problem ​

  1. A sorted array has repeats. Remove them in place, so each value appears once. Return the new length. [1, 1, 2, 3, 3] becomes [1, 2, 3, ...] with length 3.
  2. Remove every copy of a given value in place.
  3. Move every 0 to the end, keeping the other numbers in their original order. [0, 1, 0, 3, 12] becomes [1, 3, 12, 0, 0].

"In place" means you may not build a second list. You must use O(1) extra memory.

Why the obvious answer is slow ​

The obvious way to remove an element is del nums[i] or nums.pop(i). But a Python list stores its elements side by side in memory. Deleting from the middle leaves a gap, and every element after it must shift one place left to close it. That costs O(n) per deletion. Deleting up to n elements this way is O(n^2).

The write pointer ​

Use two indexes that both move left to right.

  • read visits every element, one by one.
  • write marks where the next element we want to keep should go.

When read finds an element worth keeping, copy it to write and move write forward. When it finds one to throw away, do nothing. write stays put, and the next kept element will overwrite the unwanted one.

So the front of the list, up to write, always holds exactly the kept elements, in their original order. Each element is looked at once. No shifting happens. That is O(n) time and O(1) memory.

1. Remove duplicates from a sorted array ​

Because the array is sorted, equal values sit next to each other. So an element is a new value exactly when it differs from the last value we kept.

python
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    write = 1                              # (1)
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:  # (2)
            nums[write] = nums[read]       # (3)
            write += 1
    return write                           # (4)

a = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(a)
print(k, a[:k])   # → 5 [0, 1, 2, 3, 4]

(1) The first element is always kept, so writing starts at position 1.

(2) Compare with the last value we kept, nums[write - 1]. Not with nums[read - 1]. In this problem both work, because the array is sorted. Comparing with the last kept value is the habit that also works for the variations below.

(3) A new value. Copy it into the next free slot.

(4) write is now the count of kept elements. What sits after position write does not matter. LeetCode only checks the first k positions.

Trace on [1, 1, 2, 3, 3]:

readnums[read]last keptkeep?list afterwrite
111no1 1 2 3 31
221yes1 2 2 3 32
332yes1 2 3 3 33
433no1 2 3 3 33

The first 3 positions hold 1 2 3.

A variation: keep at most two of each (LeetCode 80). Compare with the value two places back from write. If the new value equals nums[write - 2], two copies are already kept, so skip it.

python
def keep_at_most_two(nums: list[int]) -> int:
    write = 0
    for x in nums:
        if write < 2 or x != nums[write - 2]:
            nums[write] = x
            write += 1
    return write

a = [1, 1, 1, 2, 2, 3]
k = keep_at_most_two(a)
print(k, a[:k])   # → 5 [1, 1, 2, 2, 3]

2. Remove every copy of a value ​

The same pattern with a simpler test: keep anything that is not the value.

python
def remove_element(nums: list[int], val: int) -> int:
    write = 0
    for x in nums:
        if x != val:
            nums[write] = x
            write += 1
    return write

a = [3, 2, 2, 3, 4]
k = remove_element(a, 3)
print(k, a[:k])   # → 3 [2, 2, 4]

3. Move zeros to the end ​

Copy forward, then fill with zeros ​

Use the write pointer to pack every non-zero to the front, in order. Then fill the rest with zeros.

python
def move_zeros(nums: list[int]) -> None:
    write = 0
    for x in nums:
        if x != 0:
            nums[write] = x       # (1)
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0               # (2)

a = [0, 1, 0, 3, 12]
move_zeros(a)
print(a)   # → [1, 3, 12, 0, 0]

(1) Pack the non-zeros at the front. Their order does not change, because we copy them in the order we meet them.

(2) Everything after them must be a zero.

Swap instead of copy ​

Swap each non-zero into the write position. The zero that was there goes to where the non-zero came from.

python
def move_zeros_swap(nums: list[int]) -> None:
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]   # (1)
            write += 1

a = [0, 1, 0, 3, 12]
move_zeros_swap(a)
print(a)   # → [1, 3, 12, 0, 0]

(1) Everything between write and read is a zero. Swapping moves the non-zero to the front edge of that block of zeros, and moves a zero to its back edge. The non-zeros stay in their original order.

This version makes one pass instead of two. It also never writes a value that is already in place, which matters if writes are expensive, such as on flash memory.

Why not just sort? sorted(nums, key=lambda x: x == 0) does work. Python's sort is stable, meaning equal keys keep their order. All non-zeros have key False and stay in order, then come the zeros. But it costs O(n \log n) instead of O(n), and it builds a new list. It is a clever one-liner to mention, not the answer.

Complexity ​

Every version here is O(n) time and O(1) extra memory. Each element is read once and written at most once.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Why not use del nums[i] inside a loop?" Each delete moves every later element one place left. That is O(n) per delete, and O(n^2) in total. Deleting while looping over the same list also makes the loop skip elements.

"Keep at most two copies of each value." Compare the new value with nums[write - 2]. If they are equal, two copies are already kept, so skip it. For "at most k", compare with nums[write - k].

"Does your move-zeros keep the other numbers in order?" Yes. Both versions copy or swap the non-zero numbers in the order they appear.

One thing to volunteer: "The write pointer is just a filter. The front of the list is the output, and write is its length."

Next: 4.0.19 Merge Two Sorted Arrays. Two pointers that walk two different arrays, and the step at the heart of merge sort.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet