# [LeetCode] Top Interview 150 Problems Solving # 80 Remove Duplicates from Sorted Array II

# **Understanding the Problem**

An integer list of `nums` has numbers that could be either duplicate or non-duplicate. It is to leave 1-2 values for each number in the list in-place, which means it is nothing to do with returning any value from the method.

```python
# example 1
Input: nums = [1, 1, 1, 2, 2, 3, 3, 4]
Output: nums = [1, 1, 2, 2, 3, 3, 4] # it is not a returned value. Must fix nums list from the parameter
```

# **Approach**

I had an experience of removing duplicates from the given list. It was pretty much the same though. But this time it allowed each unique element to have 2 duplicates.

I was going to have the unique values with `set()` method and iterate from this.

# **Solution**

The problem solving steps are as below.

1. I get the unique values into `unique_n` with `set(nums)`
    
2. Then I would check each element with `n`
    
3. If `n` has more duplicates than 2, remove in the `while` loop
    

```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        unique_n = set(nums)
        for n in unique_n:
            while nums.count(n) > 2:
                nums.remove(n)
```

# **Reflection**

This solution is not the best I could tell as the time complexity scored 4017ms! An amusing runtime number I had not seen before. There are two loops `for` and `while`, which will be close to *O(n²)* at worst.

People had it done in a different way with double pointer.

```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:

        k = 2

        for i in range(2, len(nums)):
            if nums[i] != nums[k - 2]:
                nums[k] = nums[i]
                k += 1 

        return k
```

With this solution `k-2`th and `i`th index values are compared. The code could be visualised step by step like this.

```python
# step 1
nums = [1, 1, 1, 2, 2, 3]
 idx => 0  1  2  3  4  5
        i     k
# i is 0 and k is at 2
# nums[i] != nums[k - 2] this condition is False

# step 2
nums = [1, 1, 1, 2, 2, 3]
 idx => 0  1  2  3  4  5
           i  k
# i is 1 and k is at 2
# nums[i] != nums[k - 2] this condition is False

# step 3
nums = [1, 1, 1, 2, 2, 3]
 idx => 0  1  2  3  4  5
              i
              k
# i is 2 and k is at 2
# nums[i] != nums[k - 2] this condition is False

# step 4
nums = [1, 1, 1, 2, 2, 3]
 idx => 0  1  2  3  4  5
              k  i
# i is 3 and k is at 2
# nums[i] != nums[k - 2] this condition is True
# nums[k] is updated, and k is updated
nums = [1, 1, 2, 2, 2, 3]
 idx => 0  1  2  3  4  5
                 k  i
```

This process goes until the end. It is quite a tricky algorithm without visualisation. With double pointers the time complexity will be close to *O(n).*