Leetcode 26 Solution

Leetcode Question Link

https://leetcode.com/problems/remove-duplicates-from-sorted-array

Thinking Process

The most straightforward solution is to iterate the array, and remove element whenever you see it is the same as the previous one. If there are N elements in the array, the time complexity will be O(N^2).

Apparently, removing the element is a O(N) operation, which is very time consuming. But is that really needed? If we were to think about it, all we need here is to iterate the rest of the array, so why not just use another pointer (or index) pointing the rest of the array? By using a pointer, we don’t need to remove the original element, which is a O(1) time complexity.

Time & Space Complexity

Assuming there are N nodes in the list:

• Time complexity: O(N)
• Space complexity: O(1)

Solution

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = 0;
        for (int r = 0; r < nums.size(); r++)
            if (r + 1 >= nums.size() || nums[r] != nums[r + 1])
                swap(nums[l++], nums[r]);
        return l;
    }
};