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.

# 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

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.

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-2th and ith index values are compared. The code could be visualised step by step like this.

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