# Remove Duplicates from Sorted Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-duplicates-from-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/remove-duplicates-from-sorted-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Flipkart](https://scaleengineer.com/companies/flipkart), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nagarro](https://scaleengineer.com/companies/nagarro), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Siemens](https://scaleengineer.com/companies/siemens), [Uber](https://scaleengineer.com/companies/uber), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
Given an integer array `nums` sorted in **non-decreasing order**, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place%5Falgorithm) such that each unique element appears only **once**. The **relative order** of the elements should be kept the **same**. Then return _the number of unique elements in_ `nums`.

Consider the number of unique elements of `nums` to be `k`, to get accepted, you need to do the following things:

* Change the array `nums` such that the first `k` elements of `nums` contain the unique elements in the order they were present in `nums` initially. The remaining elements of `nums` are not important as well as the size of `nums`.
* Return `k`.

**Custom Judge:**

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be **accepted**.

**Example 1:**

**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).

**Example 2:**

**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).

**Constraints:**

* `1 <= nums.length <= 3 * 104`
* `-100 <= nums[i] <= 100`
* `nums` is sorted in **non-decreasing** order.

# Approaches
## Using an Auxiliary Array
A straightforward approach is to use an auxiliary data structure, like another array or a list, to store only the unique elements. We can iterate through the original sorted array and add an element to our auxiliary array only if it's different from the last element we added. After processing all elements, we copy the contents of the auxiliary array back into the beginning of the original array and return its size.
**Time:** O(N) · **Space:** O(k)
**Pros:** Conceptually simple and easy to follow.; Separates the logic of finding unique elements from modifying the original array.
**Cons:** Requires extra space proportional to the number of unique elements, which can be up to O(N) in the worst case (all elements are unique).; Violates the strict 'in-place' O(1) space complexity constraint of the problem.
### Explanation
This method prioritizes simplicity over space efficiency. It doesn't modify the array in-place directly during the identification of unique elements, but rather uses an intermediate storage.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        List<Integer> uniqueElements = new ArrayList<>();
        uniqueElements.add(nums[0]);

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                uniqueElements.add(nums[i]);
            }
        }

        for (int i = 0; i < uniqueElements.size(); i++) {
            nums[i] = uniqueElements.get(i);
        }

        return uniqueElements.size();
    }
}
```
### Algorithm
- Check for the edge case where the input array `nums` is empty. If so, return 0.
- Create a new `ArrayList<Integer>` called `uniqueElements`.
- Add the first element of `nums` (`nums[0]`) to `uniqueElements`.
- Iterate through the `nums` array from the second element (`i = 1` to `nums.length - 1`).
- For each element `nums[i]`, compare it with the previous element `nums[i-1]`.
- If `nums[i]` is not equal to `nums[i-1]`, it's a new unique element, so add it to the `uniqueElements` list.
- After the loop finishes, the `uniqueElements` list contains all the unique items in the correct order.
- Copy the elements from `uniqueElements` back to the original `nums` array. Iterate from `j = 0` to `uniqueElements.size() - 1` and set `nums[j] = uniqueElements.get(j)`.
- Finally, return the size of the `uniqueElements` list, which is the count of unique elements `k`.

## Two-Pointer In-Place Approach
The optimal solution uses a two-pointer technique to solve the problem in-place, adhering to the O(1) space complexity constraint. We use a 'slow' pointer to track the position for the next unique element and a 'fast' pointer to scan the array. Since the array is sorted, all duplicate elements will be grouped together. We can overwrite the duplicates with the next unique element found by the fast pointer.
**Time:** O(N) · **Space:** O(1)
**Pros:** Extremely efficient in terms of space, using O(1) extra space.; Solves the problem in a single pass, resulting in an optimal time complexity of O(N).; Directly modifies the array in-place as required.
**Cons:** The in-place modification can be slightly harder to reason about for beginners compared to using an auxiliary array.
### Explanation
This approach modifies the array in-place. The slow pointer, let's call it `insertIndex`, effectively divides the array into two parts: the processed part with unique elements `[0...insertIndex-1]` and the unprocessed part `[insertIndex...n-1]`. The fast pointer iterates through the entire array to find elements to be placed in the processed part.

```java
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        // insertIndex is the slow-runner pointer, indicating the next position for a unique element.
        int insertIndex = 1;
        
        // i is the fast-runner pointer that scans the array.
        for (int i = 1; i < nums.length; i++) {
            // If the current element is different from the previous one, it's a new unique element.
            if (nums[i] != nums[i-1]) {
                // Place it at the next available position for unique elements.
                nums[insertIndex] = nums[i];
                // Increment the count of unique elements found so far.
                insertIndex++;
            }
        }
        return insertIndex;
    }
}
```
### Algorithm
- Handle the edge case: if the array has 0 or 1 elements, no duplicates can exist, so return its length.
- Initialize a slow pointer `insertIndex` to 1. The element at index 0 is considered the first unique element and is already in its correct place.
- Initialize a fast pointer `i` to 1.
- Iterate with the fast pointer `i` from 1 to the end of the array (`nums.length - 1`).
- In each iteration, compare the current element `nums[i]` with the previous element `nums[i-1]`.
- If `nums[i]` is different from `nums[i-1]`, it means we've found a new unique element.
- Place this unique element at the position indicated by the slow pointer: `nums[insertIndex] = nums[i]`.
- Increment the slow pointer `insertIndex` to mark the new end of the unique elements subarray.
- If `nums[i]` is the same as `nums[i-1]`, it's a duplicate. We do nothing but let the fast pointer `i` advance, effectively skipping the duplicate.
- After the loop completes, `insertIndex` will be the count of unique elements, `k`. The first `k` elements of `nums` will be the unique elements. Return `insertIndex`.

# Solutions
### CSharp

```csharp
public class Solution { public int RemoveDuplicates ( int [] nums ) { int k = 0 ; foreach ( int x in nums ) { if ( k == 0 || x != nums [ k - 1 ]) { nums [ k ++] = x ; } } return k ; } }
```

### Java

```java
class Solution {
public
  int removeDuplicates(int[] nums) {
    int k = 0;
    for (int x : nums) {
      if (k == 0 || x != nums[k - 1]) {
        nums[k++] = x;
      }
    }
    return k;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var removeDuplicates =
  function (nums) {
    let k = 0;
    for (const x of nums) {
      if (k === 0 || x !== nums[k - 1]) {
        nums[k++] = x;
      }
    }
    return k;
  };

```

### CPP

```cpp
class Solution {
public:
  int removeDuplicates(vector<int> &nums) {
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    return nums.size();
  }
};

```

### Python

```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int: k = 0 for x in nums: if k == 0 or x != nums[k - 1]: nums[k] = x k += 1 return k

```