Leetcode: Remove Duplicates from Sorted Array (32ms) (two pointers) analysis and solution

Problem:

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.

Hide Tags

 Array Two Pointers

Analysis:

A classical two pointer (TP) problem. Usually, TP is used when extra space is not allowed to be used. The key to use the TP is to get a clear idea about the logic of the problem first. Different problem can have different logic. The logic for this problem can be shown as following (you may use other logic!):
(click to see large and clear image)

s and i are two pointers used to mark left position and going sweeping position, respectively. 

///////////////////////////////////////

//code 32ms

class Solution {

public:

       int removeDuplicates(vector<int>& nums) {

              int s = 0, n = nums.size();

              if (n<2)return n;

              for (int i = 1; i<n;){

                     if (nums[i] != nums[s]){

                           if (i - s>1)nums[s + 1] = nums[i];

                           s++;

                           i++;

                     }

                     else i++;

              }

              return s + 1;

       }

};

by erasing the extra elements inside (39ms)

//////////////////////////////////////////////

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //edge case
        if (nums.size()<2)return nums.size();
        
        vector<int>::iterator ite=nums.end(), iteTmp=ite;
        iteTmp--;ite--;ite--;
        for (;iteTmp!=nums.begin();iteTmp--,ite--){
            if ( iteTmp!=nums.begin() &&*ite==*iteTmp){
                nums.erase(ite);
            }
            if (ite==nums.begin())break;
        }
        return nums.size();
    }
};

if only need to return the number of distinct elements without revising the vector nums:

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

};