Remove Duplicates From Sorted Array - Leetcode Solution

The problem is to remove duplicates from a sorted array in place and return the new length of the array. Here is a detailed solution to the problem:

Approach: We can use two pointers to traverse the array and remove duplicates in place. We'll traverse the array from left to right. If we come across an element that's not a duplicate, we'll move it to the left and update the length of the array. If we come across a duplicate, we'll skip it and move the pointer until we find the next non-duplicate element.

Algorithm:

1. If the length of the array is less than 2, return the length of the array.
2. Initialize a pointer i to 0 and a pointer j to 1.
3. Traverse the array from left to right until j reaches the end of the array.
4. If the element at the current position j is not equal to the element at the position i, copy the element at j to the position i+1, increment i and update the length of the array.
5. If the element at the current position j is equal to the element at the position i, skip the duplicate and continue iterating.
6. Return the updated length of the array.

Code:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2) {
            return nums.size();
        }
        int i = 0, j = 1;
        while (j < nums.size()) {
            if (nums[j] != nums[i]) {
                nums[++i] = nums[j];
            }
            j++;
        }
        return i + 1;
    }
};

Time Complexity: The time complexity of the solution is O(n) because we traverse the array only once.

Space Complexity: The space complexity of the solution is O(1) because we modify the array in place and do not use any extra space.

1