Remove Duplicates from Sorted Array

Easy Arrays & Hashing Two Pointer Original on LeetCode

Remove Duplicates from Sorted Array is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers, in place), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy distinct values out and back) up.

Problem

You are given an integer array nums sorted in non-decreasing order. Remove the repeated values in place so that each distinct value appears once, keeping the values in their original relative order.

Return k, the number of distinct values. The first k slots of nums must hold those values; whatever is left in the slots after them is ignored. Do it with O(1) extra memory.

Examples

Example 1

Input
nums = [2, 2, 5, 7, 7, 7, 9]
Output
4, nums = [2, 5, 7, 9, _, _, _]
Why
There are four distinct values. They must fill the first four slots in their original order; what is left after them does not matter.

Example 2

Input
nums = [-3, -3, -3]
Output
1, nums = [-3, _, _]
Why
Only one distinct value remains.

Example 3

Input
nums = [1, 4, 6]
Output
3, nums = [1, 4, 6]
Why
No duplicates, so the array is already in its final form.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (copy distinct values out and back)O(n)O(n)
Optimal (two pointers, in place)O(n)O(1)

1Brute force (copy distinct values out and back)

TimeO(n)One pass to collect and one pass to copy back.
SpaceO(n)The extra list can hold up to n values, which the in-place requirement wants to avoid.

Collect the distinct values in order into a separate list (or an ordered set), then copy them back to the front of nums.

  1. Walk the array and add each value to a list if it differs from the last value added.
  2. Copy the list into nums[0 … k - 1].
  3. Return k, the size of the list.
class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> distinct = new ArrayList<>();
        for (int x : nums) {
            if (distinct.isEmpty() || distinct.get(distinct.size() - 1) != x) {
                distinct.add(x);
            }
        }
        for (int i = 0; i < distinct.size(); i++) {
            nums[i] = distinct.get(i);
        }
        return distinct.size();
    }
}

2Optimal (two pointers, in place)

TimeO(n)Each element is read once.
SpaceO(1)Only the two indices; the array is rewritten in place.

Use write as the length of the deduplicated prefix. Scan with read; whenever nums[read] differs from the last kept value nums[write - 1], it is a new value, so copy it to nums[write] and grow the prefix.

  1. write = 1 (the first element is always kept).
  2. For read = 1 … n - 1: if nums[read] != nums[write - 1], set nums[write] = nums[read] and increase write.
  3. Return write.
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];
                write++;
            }
        }
        return write;
    }
}

Edge cases to test

  • A single element
  • Every element is the same
  • No duplicates at all
  • Long runs of duplicates at the start or the end

Hints

Hint 1

Because the array is sorted, equal values sit next to each other. A value is new exactly when it differs from the one before it.

Hint 2

Keep a write index for the next free slot of the answer, and a read index that scans the whole array.

FAQ

What is the best time complexity for Remove Duplicates from Sorted Array?

Optimal (two pointers, in place) runs in O(n) time and O(1) extra space. Each element is read once.

Which pattern does Remove Duplicates from Sorted Array use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Remove Duplicates from Sorted Array?

Yes. Brute force (copy distinct values out and back) takes O(n) time and O(n) space. Collect the distinct values in order into a separate list (or an ordered set), then copy them back to the front of nums.

Which edge cases should I test for Remove Duplicates from Sorted Array?

A single element; Every element is the same; No duplicates at all; Long runs of duplicates at the start or the end.