Remove Duplicates from Sorted Array

Compress a sorted array in place so each unique value appears once, then return the new length.

Open concept page Back to problem map

This is a core same-direction pointer problem.

It builds the habit of naming what the processed prefix already guarantees.

Problem intuition

Because duplicates are adjacent in a sorted array, you only need to track the next slot for a new unique value.

A non-optimal solution can still be correct by writing into a helper structure first, but the clean version reuses the array in place.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Copy uniques into a helper list

O(n)O(n)

Scan once, store unique values in a helper list, then copy them back. Correct, but it wastes extra space.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> unique = new ArrayList<>();

        for (int num : nums) {
            if (unique.isEmpty() || unique.get(unique.size() - 1) != num) {
                unique.add(num);
            }
        }

        for (int i = 0; i < unique.size(); i++) {
            nums[i] = unique.get(i);
        }

        return unique.size();
    }
}

Solution 2

Read pointer and write pointer

O(n)O(1)

Keep one pointer on the next write position and copy each newly discovered value into place.

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int write = 1;

        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[read - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }

        return write;
    }
}