Remove Duplicates from Sorted Array

+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.

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

In an unsorted array you would have to remember every value seen. Sorting puts all copies of a value in one run, so a value is new exactly when it differs from the last value you kept. One pass with a read index and a write index does the job in place.

Remember seen values in a hash set

Intuition

Walk through nums and keep a set of the values already in the answer. Append a value the first time you meet it and skip it after that, so each value appears once, in the order you meet it. This never uses the sort order and works on any array.

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

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

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, so nums[k-1] is the last value kept. The read index i visits every value. A value equal to nums[k-1] is another copy of a run you already kept; a different one starts a new run and goes to nums[k].

On [1, 1, 2, 3, 3, 3], i = 1 skips the second 1, i = 2 writes 2 to index 1, i = 3 writes 3 to index 2, and the last two 3s are skipped. The first three slots read [1, 2, 3].

Since k never passes i, a write never overwrites a value you have not read. The pass is O(n) time with two integers of 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

Comparing nums[i] with nums[i+1] while i runs to the last index. The last comparison reads one past the end.
Starting k at 0. The first value is then 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] comes back as [1, 2, 2].
Building the answer by iterating a hash set. Most hash sets keep no order, so the values can come out scrambled.
In Lua and R, arrays start at 1. The kept part is nums[1] to nums[k], and you compare with nums[k].

Frequently asked questions3

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 comparing with the last kept value is enough. In an unsorted array a copy can appear anywhere, so you need a hash set of every value seen, which costs O(n) extra space.

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].

def removeDuplicates(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

[1, 2, 3]