Remove Duplicates from Sorted Array

Q: How do you remove duplicates in place without extra memory?

Keep a write index k next to the read index. The first k slots hold the distinct values so far. When the value you read differs from nums[k-1] , copy it to nums[k] and advance k . The write index never passes the read index, so nothing is overwritten before it is read.

EasyTwo pointers

+10

You get an array of integers nums sorted in non-decreasing order, so equal values sit next to each other. Return the distinct values of nums, each once, in the order they appear. For example, [2, 2, 5] gives [2, 5].

Function

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: the integers, sorted in non-decreasing order
Returnsinteger-array: the distinct values of nums, in increasing order

Constraints

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

Examples

Input: nums = [1, 1, 2, 3, 3, 3]
Output: [1, 2, 3]
Explanation: 1 appears twice and 3 three times. Keeping one of each leaves [1, 2, 3].

Input: nums = [-2, 0, 0, 5]
Output: [-2, 0, 5]
Explanation: Only 0 repeats. Negative values work the same way, so the answer is [-2, 0, 5].

Input: nums = [7, 7, 7]
Output: [7]
Explanation: Every value is 7, so one 7 is all that is left.

+15 hidden tests on Submit

Follow-up

Can you do it with O(1) extra memory, by rewriting nums in place instead of building a second array?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Removing duplicates from an arbitrary array means remembering every value you have seen. Sorted input removes that need: copies of a value are neighbours, so a value is new exactly when it differs from the last one you kept. That turns the job into one pass with two indexes and no extra memory.

Remember seen values in a hash set

Intuition

Walk through nums and keep a set of the values you have already added to the answer. When a value is not in the set, append it to the answer and add it to the set; when it is, skip it. For [1, 1, 2, 3, 3, 3] the answer grows to [1], then [1, 2], then [1, 2, 3], and every later copy is skipped.

Each value is appended the first time it appears and never again, in the order you meet it, so the answer is right. This approach never uses the fact that nums is sorted; it would work on any array.

Set lookups take O(1) on average, so the pass is O(n) time, but the set and the answer can each hold n values: O(n) extra space. In C, with no built-in set, an array of flags for the 2 × 10^4 + 1 possible values does the same job.

Algorithm

Create an empty set seen and an empty list result.
For each value in nums, check whether it is in seen.
If it is not, add it to seen and append it to result.
Return result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Compact in place with a write pointer

Intuition

In sorted input, all copies of a value form one run, so a value is new exactly when it differs from the last value you kept. That needs one comparison, not a set.

Use two indexes. The read index i visits every value. The write index k marks the end of the kept part: nums[0] to nums[k-1] always holds the distinct values found so far. Start with k = 1, since the first value is always kept. When nums[i] differs from nums[k-1], copy it to nums[k] and move k forward.

On [1, 1, 2, 3, 3, 3]: i = 1 reads a second 1 and nothing happens. i = 2 reads 2, which differs from nums[0] = 1, so it goes to index 1 and k becomes 2. i = 3 writes 3 to index 2 and k becomes 3. The last two 3s match nums[2] and are skipped. The first three slots now read [1, 2, 3].

Writing never overtakes reading, because k is always at most i, so you never overwrite a value before you read it. One pass is O(n) time, and apart from the returned values you use two integers: O(1) extra space.

Algorithm

Set k = 1: nums[0] is always kept.
Loop i from 1 to the last index.
If nums[i] differs from nums[k-1], set nums[k] = nums[i] and add 1 to k.
Return the first k values of nums.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Pitfalls and edge cases

The write pointer is short, and its bugs are about which value you compare against.

Comparing nums[i] with nums[i+1] while i runs to the last index. The last comparison reads one past the end of the array.
Starting k at 0. Then the first value is compared with nums[-1], which is out of range or, in Python, the last element.
Returning the whole array instead of its first k values. The tail still holds old values, so [1, 1, 2] would come back as [1, 2, 2].
Building the answer by iterating a hash set. A hash set in most languages keeps no order, so the values can come out scrambled; append each value to a list when you first meet it instead.
In Lua and R, arrays start at 1. The kept part is nums[1] to nums[k], and the comparison is with nums[k], not nums[k-1].

Frequently asked questions4

What is the time complexity of Remove Duplicates from Sorted Array?

The write pointer solution reads each value once, so it runs in O(n) time. Besides the values it returns, it uses O(1) extra space: two indexes.

Why does the array need to be sorted?

Sorting puts every copy of a value in one run, so a value is new exactly when it differs from the last value kept. In an unsorted array a copy can show up far from the first one, and you need a hash set to remember every value seen, which costs O(n) extra space.

How do you remove duplicates in place without extra memory?

Keep a write index k next to the read index. The first k slots hold the distinct values so far. When the value you read differs from nums[k-1], copy it to nums[k] and advance k. The write index never passes the read index, so nothing is overwritten before it is read.

How would you allow each value at most twice?

Compare with the value two places back in the kept part instead of one: copy nums[i] when k < 2 or when it differs from nums[k-2]. If it equals nums[k-2], the kept part already ends with two copies of it. The same idea allows at most m copies with nums[k-m].

Python

def removeDuplicates(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [1, 1, 2, 3, 3, 3]

Expected

[1, 2, 3]