Remove Duplicates from Sorted Array

Easy Problem 17 of 151 Java and Python

Problem

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place so each unique value appears once, keeping their order. Return k, the number of unique values.

The first k elements of nums must hold the unique values. What is left after them does not matter.

Example 1

Input: nums = [1, 1, 2]
Output: k = 2, nums starts with [1, 2]

Example 2

Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: k = 5, nums starts with [0, 1, 2, 3, 4]

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-100 ≤ nums[i] ≤ 100
nums is sorted in non-decreasing order.

Explanation

Because the array is sorted, duplicates are next to each other. A value is new exactly when it differs from the last value you kept.

Use a slow write pointer for the end of the kept part and a fast pointer to read. Copy each new value to write.

Approach 1 · Naive

Collect the unique values first

Time O(n)
Space O(n)

Gather the unique values into a separate list (an ordered set works too), then copy them back to the front of the array.

Walk the array and add each value that differs from the previous one to a list.
Copy the list into the start of nums and return its size.

Java

import java.util.*;

class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> unique = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                unique.add(nums[i]);
            }
        }
        for (int i = 0; i < unique.size(); i++) {
            nums[i] = unique.get(i);
        }
        return unique.size();
    }
}

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        unique = []
        for i, num in enumerate(nums):
            if i == 0 or num != nums[i - 1]:
                unique.append(num)
        nums[:len(unique)] = unique
        return len(unique)

Approach 2 · Optimal

Read and write pointers

Time O(n)
Space O(1)

Keep the first element. For each later element, if it differs from the last kept value nums[write - 1], write it at write and advance.

Set write = 1.
For read from 1 to n – 1: if nums[read] != nums[write - 1], set nums[write] = nums[read] and increment write.
Return write.

Java

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

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        write = 1
        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1
        return write

Complexity compared

Approach	Time	Space
Naive Collect the unique values first	O(n)	O(n)
Optimal Read and write pointers	O(n)	O(1)

Key takeaways

Comparing with the last kept value (nums[write - 1]) generalises: compare with nums[write - 2] to allow each value twice.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem