Leetcode: 26. Remove Duplicates from Sorted Array (Double Index)

Removing Duplicates from a Sorted Array in Place

Given an integer array nums sorted in non-decreasing order, we need to remove the duplicates in-place so that each unique element appears only once. The relative order of the elements should be kept the same. Additionally, we need to return the number of unique elements in nums.

Algorithm

To solve this problem, we can use a two-pointer approach. We will maintain one pointer called insertedIndex that will keep track of the index where we want to insert the next unique element. Starting from index 1, we iterate through the array comparing each element with its previous element. If the current element is different from the previous one, it means we have found a new unique element, so we update the array at insertedIndex with this element and increment insertedIndex by 1. By the end of the loop, insertedIndex will contain the number of unique elements in nums.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int insertedIndex = 1; 
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i-1] != nums[i])
            {
                nums[insertedIndex] = nums[i];
                insertedIndex++;
            }
        }
        return insertedIndex;
    }
}

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array nums. This is because we iterate through the array once to compare each element with its previous element. Since the array is already sorted, the comparison operation takes constant time.

Conclusion

In this blog post, we explored a simple and efficient algorithm to remove duplicates from a sorted array in place while maintaining the relative order of the elements. The algorithm has a time complexity of O(n), making it an optimal solution for this problem.