I wrote the version with the indices backwards, on purpose, and the borrow checker had nothing to say about it.

That was not the version I meant to write. The version I meant to write is this one, and the interesting part of it is the signature:

pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32

&mut Vec<i32> says the function rearranges the array it was given, and the caller can see it happen. That is not a formality. The in-place requirement is a property of the problem, and the type is where the property gets written down. A function returning a fresh Vec<i32> would be a different function solving a different problem, and the borrow in this signature is the compiler refusing to let that version pretend to be this one.

Inside, the whole algorithm is two counters and one comparison:

pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    let mut curr = 1;
    for next in 1..nums.len() {
        if nums[next] != nums[curr - 1] {
            nums[curr] = nums[next];
            curr += 1;
        }
    }
    curr as i32
}

curr is where the next unique value gets written. next is the scan position. Because the input is sorted, duplicates are adjacent, so the only question at each step is whether the current value differs from the last value written. If it does, it is copied down to curr and curr advances.

The read ends before the write starts

nums[curr] = nums[next]; reads one element and writes another in the same array. That is exactly the shape the borrow checker is built to object to, so it is worth being precise about why it is allowed.

It is allowed because the two accesses do not overlap in time. The read of nums[next] produces an i32, which is Copy, so it is copied out and the borrow ends. The write to nums[curr] takes a fresh mutable borrow afterward. Non-lexical lifetimes make this work: the immutable borrow is dead the instant its value has been read.

The version that does not compile is holding both borrows at once. Here is my own experiment, written to produce that error:

let writer = &mut nums[curr];
let reader = &nums[next];
println!("{} {}", writer, reader);
error[E0502]: cannot borrow `nums` as immutable because it is also borrowed as mutable

The compiler marks the &mut nums[curr] line as the mutable borrow and the &nums[next] line as the conflicting immutable one, and it adds a help line suggesting split_at_mut if you really want two disjoint sub-slices.

That is the whole of the agreement. The borrow checker is not approving the algorithm. It is approving the fact that the algorithm never has two live views into the same array at once.

What the borrow checker does not check

Here is the part I want to be careful about, because it is easy to overclaim.

The borrow checker enforces aliasing, not ordering. It has no idea that curr is supposed to trail next. Here is my own experiment, the same expression with the indices reversed:

let mut nums = vec![1, 1, 2, 2, 3];
let curr = 4usize;
let next = 1usize;
nums[curr] = nums[next];

It compiled with no warnings and produced [1, 1, 2, 2, 1]. The last element got overwritten with the first duplicate. Nothing in the type system objected, because nothing in the type system knows what the indices mean.

I also broke the invariant on purpose by advancing curr twice per iteration. That version compiled clean too, and produced [1, 1, 2, 2, 3] where the correct algorithm produces [1, 2, 3, 2, 3].

So the honest description is: the borrow checker confirmed that the code has no aliasing bug. It confirmed nothing about whether the compaction is correct. That invariant lives in the algorithm, not in the type, and it is the kind of thing that needs a test rather than a type.

Why curr starts at 1

nums[curr - 1] compares against the last value that was written. curr starts at 1, so curr - 1 is never negative. That is not defensive coding. It is load-bearing, and Rust makes the failure mode explicit.

If curr were 0, the subtraction underflows. In the debug profile it panics:

attempt to subtract with overflow

In the release profile the subtraction wraps silently to usize::MAX, and then the panic comes from somewhere else entirely:

index out of bounds: the len is 3 but the index is 18446744073709551615

Same root cause, two different panic messages, because the release profile turned the arithmetic overflow into a wrap and the bounds check caught the result instead. The wrapped value is usize::MAX, which no real vector can hold, so the bounds check always catches it. What the release profile removed was not the failure but the accurate description of it. The usize type does not stop the underflow from happening; it only decides how loudly it happens.

With curr starting at 1, none of this is reachable. The first element is always the first unique value, so there is nothing to compare it against, and the loop starts at index 1.

What the caller ends up with

After the call, the caller’s vector holds the compacted prefix and stale values past it:

caller's vec after the call: k=5 [0, 1, 2, 3, 4, 2, 2, 3, 3, 4] len=10

The length stays at 10 and the tail keeps whatever was there. Only the first k entries are meaningful, which is why the function returns k and the problem statement says the rest can be ignored. Nothing is truncated and nothing is allocated. The array the caller already had is the array that now holds the answer, which is the entire point of doing this in place.

The agreement is narrow

The signature makes the mutation visible to the caller and to the compiler. The borrow checker then confirms the one thing it is good at, which is that the algorithm never holds two views into the array at the same time.

It is a useful agreement, and it is a narrow one. Everything that makes this function correct beyond the aliasing check, the sorted input and the curr trailing next and the curr starting at 1, is invisible to the type system. The compiler vouched for the memory. The algorithm still has to be right.

What I take from it: the borrow checker checked the easy part. The curr trailing next is a property of the algorithm and not of the type, so it belongs in a test and not in a signature, and that test is mine to write.


Next: ASCII Is Not a Vowel Set