[LeetCode] 80. Remove Duplicates from Sorted Array II

1. Question

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place 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 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).

2. Thoughts

1. Use DP
2. Save value of last 3 values.
3. Add only if current + before before is better than before.

3. Tips learned

3.1. Infinity

# Defining a positive infinite integer
positive_infinity = float('inf')
print('Positive Infinity: ', positive_infinity)
# Defining a negative infinite integer
negative_infinity = float('-inf')
print('Negative Infinity: ', negative_infinity)

3.1. Index

>>> a = [123, 421, 212, 11, 24, 102, 29, 92, 10]
>>> a.index(421)
1

4. My solution

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        minus_inf = float("-inf")
        cur_num, cur_count, dup = minus_inf, 1, 0

        for i, num in enumerate(nums):
            if cur_num != num:
                cur_num = num
                cur_count = 1
            else:
                cur_count += 1

                if cur_count > 2:
                    nums[i] = minus_inf
                    dup += 1
        if dup == 0:
            return len(nums)

        for i, num in enumerate(nums):
            if num != minus_inf:
                minus_one = nums.index(minus_inf)
                if minus_one < i:
                    nums[i], nums[minus_one] = nums[minus_one], nums[i]

        return len(nums) - dup

166/166 cases passed (63 ms)
Your runtime beats 29.81 % of python3 submissions
Your memory usage beats 8.54 % of python3 submissions (17.5 MB)

5. AI Solution and Improvements

Your current algorithm works, but it can be optimized. The current algorithm has a time complexity of O(n^2) because of the index() method inside the second loop. We can improve this to O(n) by using two pointers.

Here is the improved algorithm:

Initialize two pointers, i and j. i is the slow-runner while j is the fast-runner.
As long as j is within the array, we repeatedly increment j to skip the duplicate.
When we encounter nums[j] != nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until j reaches the end of array.
Here is the improved code:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for j in range(len(nums)):
            if j < 2 or nums[j] != nums[i - 2]:
                nums[i] = nums[j]
                i += 1
        return i

This code works by maintaining a slow pointer i that represents the location where the next unique element should be moved to. The fast pointer j scans through the array. If the element at the fast pointer is different from the element at the position two places before the slow pointer, it means this element can be included in the final array (since it's not a third duplicate), so we move it to the position pointed to by the slow pointer, and increment the slow pointer.