# Remove Duplicates from Sorted Array II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/remove-duplicates-from-sorted-array-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Nykaa](https://scaleengineer.com/companies/nykaa)
---
## Problem
Given an integer array `nums` sorted in **non-decreasing order**, remove some duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place%5Falgorithm) such that each unique element appears **at most twice**. 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%5Falgorithm)** with O(1) extra memory.

**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,1,2,2,3]
**Output:** 5, nums = [1,1,2,2,3,_]
**Explanation:** Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 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,1,2,3,3]
**Output:** 7, nums = [0,0,1,1,2,3,3,_,_]
**Explanation:** Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

**Constraints:**

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

# Approaches
## Brute-Force with In-place Shifting
This approach iterates through the array, identifies groups of duplicate elements, and if a group has more than two elements, it manually shifts the rest of the array to overwrite the excess duplicates. This is an intuitive but inefficient way to solve the problem in-place.
**Time:** O(N^2) · **Space:** O(1)
**Pros:** It correctly solves the problem in-place, adhering to the O(1) extra space requirement.
**Cons:** Highly inefficient with a time complexity of O(N^2) in the worst-case scenario.; The logic for index manipulation and shifting is complex and can be difficult to implement correctly.
### Explanation
The core idea is to process the array in chunks of identical numbers. We use a pointer `i` to mark the beginning of a chunk and another pointer `j` to find its end. The number of elements in the chunk is `count = j - i`.

If `count` is greater than 2, we have `count - 2` excess elements that need to be removed. We achieve this by shifting all subsequent elements (from index `j` to the end) to the left by `count - 2` positions. This overwrites the unwanted duplicates. After shifting, we must also decrease the effective length of the array. The pointer `i` is then advanced by 2, as we keep two elements from the current chunk.

If `count` is 2 or less, no removal is needed, and we simply advance `i` to `j` to start processing the next chunk of numbers.

This method is considered brute-force because the shifting operation can be very time-consuming, especially for arrays with many duplicates at the beginning.

```java
class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            // Find the end of the block of duplicates
            int j = i;
            while (j < n && nums[j] == nums[i]) {
                j++;
            }
            int count = j - i;

            if (count > 2) {
                int numToRemove = count - 2;
                // Shift elements to the left
                for (int k = j; k < n; k++) {
                    nums[k - numToRemove] = nums[k];
                }
                // Update the effective length
                n -= numToRemove;
                // Move i to the next position after the two kept elements
                i += 2;
            } else {
                // Move to the next distinct number
                i = j;
            }
        }
        return n;
    }
}
```
### Algorithm
- Initialize a pointer `i = 0` and the effective length `n = nums.length`.
- Loop while `i` is less than `n`.
- Inside the loop, use another pointer `j` starting from `i` to find the end of the contiguous block of elements equal to `nums[i]`.
- Calculate the `count` of these elements (`j - i`).
- If `count > 2`, it means there are `count - 2` excess duplicates.
  - Shift all elements from index `j` to `n-1` to the left by `count - 2` positions.
  - Decrease the effective length `n` by `count - 2`.
  - Advance `i` by 2, since we've kept two elements.
- If `count <= 2`, no elements are removed. Advance `i` to `j` to process the next distinct number.
- After the loop terminates, return the final effective length `n`.

## Optimal Two-Pointer Approach
This is an optimal and elegant approach that solves the problem in a single pass using two pointers. A 'slow' pointer, `k`, tracks the position for the next valid element, while a 'fast' pointer, `i`, scans the array. This method avoids costly shifting operations by directly overwriting invalid elements.
**Time:** O(N) · **Space:** O(1)
**Pros:** Extremely efficient with a linear time complexity of O(N).; It's an in-place algorithm with O(1) space complexity.; The logic is concise, easy to reason about, and robust.
**Cons:** This approach is optimal, so it has no significant disadvantages.
### Explanation
The two-pointer technique is ideal for in-place array modifications. We maintain a slow pointer `k` that represents the boundary of the processed, valid part of the array. All elements before index `k` (i.e., `nums[0...k-1]`) satisfy the condition that each number appears at most twice.

A fast pointer `i` iterates through the array from the beginning to the end. For each element `nums[i]`, we decide if it should be part of the valid subarray. 

The condition for including `nums[i]` at position `k` is based on the fact that the array is sorted. An element `nums[i]` should be kept if it's not the third consecutive identical number. We can check this by comparing `nums[i]` with the element at `nums[k-2]`. If `nums[i]` is different from `nums[k-2]`, it cannot be a third duplicate. This simple check works because if `nums[i]` were a third duplicate, it would be equal to `nums[k-1]` and `nums[k-2]`. The check also naturally handles new numbers and the first two elements of the array (by initializing `k` appropriately).

We initialize `k=2` and start the fast pointer `i` from 2. If `nums[i]` is different from `nums[k-2]`, we copy `nums[i]` to `nums[k]` and increment `k`. This efficiently builds the result array at the beginning of `nums`.

```java
class Solution {
    public int removeDuplicates(int[] nums) {
        // If the array has 2 or fewer elements, no duplicates need to be removed.
        if (nums.length <= 2) {
            return nums.length;
        }

        // k is the slow pointer. The first two elements are always kept.
        int k = 2;

        // i is the fast pointer, starting from the third element.
        for (int i = 2; i < nums.length; i++) {
            // Compare the current element with the element at k-2.
            // If they are different, it means the current element is not a third duplicate.
            if (nums[i] != nums[k - 2]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}
```
### Algorithm
- Handle the edge case where the array has 2 or fewer elements by returning its length.
- Initialize a slow pointer `k = 2`, as the first two elements are always potentially part of the result.
- Initialize a fast pointer `i = 2` to iterate through the rest of the array.
- Loop with `i` from 2 to the end of the array.
- In each iteration, check if the current element `nums[i]` is different from the element at `nums[k-2]`.
  - The element `nums[k-2]` is the first of the last-seen pair of numbers in the valid part of the array.
- If `nums[i] != nums[k-2]`, it means `nums[i]` is not a third duplicate. So, place it at the next valid position: `nums[k] = nums[i]`, and then increment `k`.
- If `nums[i] == nums[k-2]`, it's a third (or more) duplicate, so we do nothing and just advance the fast pointer `i`.
- After the loop, `k` will be the length of the modified array. Return `k`.

# Solutions
### CSharp

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

### Java

```java
class Solution {
public
  int removeDuplicates(int[] nums) {
    int k = 0;
    for (int x : nums) {
      if (k < 2 || x != nums[k - 2]) {
        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 < 2 || x !== nums[k - 2]) {
        nums[k++] = x;
      }
    }
    return k;
  };

```

### CPP

```cpp
class Solution {
public:
  int removeDuplicates(vector<int> &nums) {
    int k = 0;
    for (int x : nums) {
      if (k < 2 || x != nums[k - 2]) {
        nums[k++] = x;
      }
    }
    return k;
  }
};

```

### Python

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

```