Reference: LeetCode
Difficulty: Easy

## Problem

Given a sorted array nums, 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 by modifying the input array in-place with $O(1)$ extra memory.

Example:

## Analysis

### Brute-Force

The code is adapted from EPI 5.5 using List class. Basically, we just remove duplicates, but if we use array we need to implement the remove() code by ourselves.

Note:

• remove() takes $O(N)$ time.
• Use equals rather than ==.
• A.size() is dynamic, which means it is always changing.

Time: $O(N^2)$
Space: $O(1)$

### Moving to Subarray

Use an index idx to store the processed element.

Time: $O(N)$
Space: $O(1)$

### Two Pointers

This is a solution in LeetCode, but I think it is not clear. Also, using this solution needs processing corner case (n == 0).

## Variants

Variant 1:

Implement a function which takes an input an array and a key, and updates the array so that all occurrences of the input key have been removed and the remaining elements have been shifted left to fill the emptied indices. Return the number of remaining elements. There are no requirements as to the values stored beyond the last element.

Variant 2:

Write a program which takes as input a sorted array $A$ of integers and a positive integer $m$, and updates $A$ so that if $x$ appears $m$ times in $A$ it appears exactly min(2, m) times in $A$. The update to $A$ should be performed in one pass, and no additional storage may be allocated.

• $m \geq 2$: If the count == m, reduce to $2$.
• $m = 1$: Not changing.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.