## 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.

## Analysis

We can use an integer (validIdx) to keep track of current valid length, then we traverse the array

– when nums[i] has been repeated, continue

– otherwise, write it to the array, and advance validIdx

Time complexity: O(n)

Space complexity: O(n)

## Solution

class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size() == 0) return 0; int validIdx = 0; int curr = nums[0]; for(int i=0; i<nums.size(); i++){ //if repeat continue if(nums[i] == curr){ continue; } //otherwise write the array, and move index else{ nums[validIdx] = curr; curr = nums[i]; validIdx=validIdx+1; } } nums[validIdx] = curr; return (validIdx+1); } };