# 0026. Remove Duplicates from Sorted Array

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0026-remove-duplicates-from-sorted-array)

**Given an integer array `nums` sorted in non-decreasing order, remove the duplicates** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) **such that each unique element appears only once.** The **relative order** of the elements should be kept the **same**.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.

**Return `k` *****after placing the final result in the first***** `k` *****slots of***** `nums`.**

**Do not allocate extra space for another array. You must do this by modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) **with O(1) extra memory.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `0 <= nums.length <= 3 * 10^4`
* `-100 <= nums[i] <= 100`
* `nums` is sorted in **non-decreasing** order.

```
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: 
Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: 
Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Use two pointers, **one for iterating and the other one for placing.**
{% endhint %}

* If the **place-pointer is at the index 0** (very first beginning), **we place the number and move the place-pointer. `placeP += 1`** <br>
* Besides, **if the current number is different from the previous element pointed by place-pointer** **`nums[moveP] != num[placeP = 1]`**, we also place the number **nums\[placeP] = nums\[moveP]** and move the place-pointer.<br>
* **Otherwise, we increase move-pointer's index. `moveP += 1`**
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # (base case)
        if len(nums) == 0 or len(nums) == 1: return len(nums)
        
        # ==================================================
        #  Array + Two Pointer                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        moveP, placeP = 0, 0
        
        while moveP < len(nums):
            # meet number different from previous placed number
            if placeP == 0 or nums[moveP] != nums[placeP - 1]:
                nums[placeP] = nums[moveP]
                placeP += 1
                
            moveP += 1
        
        return placeP
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */
    
    public int removeDuplicates(int[] nums) {
        /* base case */
        if(nums.length == 0 || nums.length == 1) return nums.length;
        
        int moveP = 0, placeP = 0;
        
        while(moveP < nums.length) {
            int num = nums[moveP];
            
            if(placeP < 1 || num != nums[placeP - 1]) {
                nums[placeP] = num;
                placeP += 1;
            }
            
            moveP += 1;
        }
        
        return placeP;
    }
}
```

{% endtab %}
{% endtabs %}