Remove Duplicates From Sorted Array

EASY✓ CHIP-TIMEDLC #26 — FULL STATEMENT ↗

The drill: Compact a sorted array so each value keeps exactly one copy, packed at the front in order, and report how many survived. Judged here on the returned count — the reader-writer packing is the lesson itself.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A sorted array arrives with some values repeated, and the task is to compact it so every distinct value appears exactly once, packed at the front in the same ascending order.

Whatever sits past the compacted prefix doesn't matter — it's never checked. The one required output besides the mutated array is the count of unique values now living at the front.

Because the input is already sorted, every run of a repeated value is contiguous; nothing equal ever appears out of sequence.

EX 01

nums = [2, 2, 3, 7, 7, 7, 9]

→ 4

UNIQUES 2, 3, 7, 9

EX 02

nums = [1]

→ 1

SINGLE ELEMENT

EX 03

nums = [5, 5]

→ 1

array length runs from zero up to around thirty thousand
values arrive already sorted in non-decreasing order
duplicates can repeat any number of times in a row
the returned count is the number of unique values now at the front

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The array is sorted, so duplicates always sit side by side. A hash set to remember what you've seen is paying for a problem adjacency already solved.

HINT 2 THE STRUCTURE

Keep a boundary: to its left lives the answer built so far. A new value deserves to cross the boundary only if it differs from the last value that did.

HINT 3 ONE STEP FROM THE ANSWER

Reader ahead, writer behind. When the reader's value differs from nums[writer−1], write it there and advance the writer. Where the writer ends up IS the count.

COACH'S BOARD — THE PATTERN, STEP BY STEP

READER AND WRITERPATTERN · TWO POINTERS, IN-PLACE COMPACTIONnums = [2, 2, 3, 7, 7, 7, 9]

STEP 1

Writer w starts at 1; nums[0]=2 is the first unique value, already banked.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/remove-duplicates-from-sorted-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        w = 1  # nums[:w] is the deduped prefix
        for i in range(1, len(nums)):
            if nums[i] != nums[w - 1]:
                nums[w] = nums[i]
                w += 1
        return w

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 8 LN

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        uniq = []
        for v in nums:
            if not uniq or uniq[-1] != v:
                uniq.append(v)
        nums[:len(uniq)] = uniq  # pack the survivors into the front
        return len(uniq)

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int removeDuplicates(int[] nums) {
        int w = 1; // nums[0..w) is the deduped prefix
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[w - 1]) {
                nums[w++] = nums[i];
            }
        }
        return w;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 11 LN

class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> uniq = new ArrayList<>();
        for (int v : nums) {
            if (uniq.isEmpty() || uniq.get(uniq.size() - 1) != v) {
                uniq.add(v);
            }
        }
        for (int i = 0; i < uniq.size(); i++) {
            nums[i] = uniq.get(i); // pack the survivors into the front
        }
        return uniq.size();
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED