Remove Duplicates from Sorted Array - LeetCode

Remove Duplicates from Sorted Array - LeetCode

The problem is taken from 26. Remove Duplicates from Sorted Array - LeetCode.

Approach

The approach is very simple. Let's have two pointers pointing to the first two elements respectively(suppose nums.length >=2). There might be two possibilities -

  1. Both numbers are same - Increment the second pointer by 1 place. That is we are searching for next greater number.
  2. Both numbers are different - Again here we get two possibilities. They are -
    1. If both numbers are placed consecutively - In this case, we increment both pointers by 1 place.
    2. If both numbers are not consecutively placed - This is where we replace numbers. We increment the first pointer by 1 and replace this number with the number pointed by second pointer. And increment second pointer by 1.

Keep doing this until the second the second pointer has no elements to point to.

Code - C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0; // contains final ans
        int n = nums.size();

        if(n==0)
            return 0;
        if(n==1)
            return 1;

        int i=0, j=1;
        int ans=1;

        while(j<n) {
            // for consecutive diff. nums
            if((nums[i] != nums[j]) && (j-1 == i)) {
                i++, j++;
                ans++;
            }
            // non-consecutive diff. nums
            else if((nums[i] != nums[j]) && (j-1 != i)) { 
                i++; // modify the next num
                nums[i] = nums[j];
                j++;
                ans++;
            }
            else {
                // if nums[i] == nums[j]
                j++;
            }
        }

        return ans;
    }
};

Time complexity - O(n), as we visited each element of the array at most two times. Space complexity - O(1), as we removed duplicates in-place.