LeetCode 26 Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1, 1, 2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Diffculty
Easy

Analysis

1. Sorted array

For sorted array, duplicates are in contiguous position. Since it is not allowed to allcoation new space, operations must be in place, we need to a indexer to point to the i + 1 index of visited element. Use another indexer j to iterate over the array.

if A[i] is duplicate with A[i-1], let's stay at i position, and keep moving j, until encouter an element that's not duplicate with A[i], then, replace A[i] with A[j], then i++.

At the end, index i points to the end of the new array, return it.

2. Non-sorted array

Use set or map to save unique values, since this need to use extra space, this can't be done in place.

Solutions

1. Cpp solution

class Solution {
public:
    int removeDuplicates(vector<int> &A) {
        const int n = A.size();
        if(n < 2) return n;

        int end = 1; // end denotes the slot that we are going to put the A[i] into
                     // if A[i] != A[end - 1], we can put A[i] at index end

        // end also denotes the end of the new array.
        // for example: A{1, 1, 2, 2, 3}, initially end should be at 1, and then 3
        for(int i = 1; i < n; ++i){
            if(A[end - 1] != A[i]){
                A[end++] = A[i];
            }
        }
        return end;
    }
};

1. For unsorted array, some cpp solutions.

   • vector, sort + unique

     sort(vec.begin(), vec.end()); iter = unique(vec.begin(), vec.end()); vec.erase(iter, vec.end()); len = distance(vec.begin(), iter);

   • set

     set s(vec.begin(), vec.end()); vec.assign(s.begin(), s.end());

   • unordered_set unordered_set s(vec.begin(), vec.end()); vec.assign(s.begin(), s.end()); sort(vec.begin(), vec.end());

Summary: unordered_set has best time complexity in the above 3 solutions!

• std::unique() Remove consecutive duplicates in range

  std::vector myvector {10, 20, 20, 20, 30, 30, 20, 20, 10}; std::vector::iterator it; it = std::unique (myvector.begin(), myvector.end()); // 10 20 30 20 10 - - - - myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30 20 10

1. Go solution

   func removeDuplicates(nums []int) int {
    if len(nums) < 2 {
        return len(nums)
    }
    i := 1
    for j := 1; j < len(nums); j++ {
        if nums[i-1] != nums[j] {
            nums[i] = nums[j]
            i++
        }
    }
    return i
   }
   

Reference