Problem¶

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];
}

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 * 10**4
• -10**4 <= nums[i] <= 10**4
• nums is sorted in non-decreasing order.

Solve¶

from collections import defaultdict

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # return self.counting(nums)
        return self.sliding(nums)

Counting¶

O(n)

A normal loop through all available number in nums array, I keep a cache that store total appearance on all of the number.

With that, I then adding the number in to nums array base on how many times they appear

    def counting(self, nums):
        count = defaultdict(int)
        for n in nums:
            count[n] += 1

        a = list(count.keys())
        a.sort()
        index = 0
        for k in a:
            if count[k] >= 2:
                nums[index] = nums[index+1] = k
                index += 2
            elif count[k] == 1:
                nums[index] = k
                index += 1
        for i in range(index, len(nums)):
            nums.pop()

Sliding pointer¶

O(n)

Using the above counting method, we isn’t consider the array is sorted in non-decreasing order: Equal number is right next each other. So, we only need to check the next following number on every number value change to count total appearance of value.

Which mean, we can effectively update the nums array by using two index, faster pointer, follow 3 rules:

• A base index pointer, which point to the need to be update nums
• index pointer only change to next one, unless it’s correspond nums array value is update to the correct value.
• A faster pointer, which is the current nums we process.

Because index increase slower than faster pointer, we can store directly into nums array without losing any unprocessed data

    def sliding(self, nums):
        index, faster = 0, 0
        count = 0
        value = None
        for i, n in enumerate(nums):
            if i == 0:
                index, faster = 0, 0
                value = n
                count = 1
                continue

            if n == value:
                count += 1
            else:
                value = n
                count = 1

            if count <= 2:
                index += 1

            faster += 1
            nums[index] = nums[faster]

        for i in range(index+1, len(nums)):
            nums.pop()

By keeping track of total appearance of current number (value) using count. We make sure update the nums less than or equal 2 times each number

I also convert it to c code and java code:

• In c code, i try using a boolean instead of int, as count only in the value of 1 or 2 in the first implementation

• I also using initiation directly to process the first index of number, skip it on the next for loop
  

  int removeDuplicates(int* nums, int numsSize){
      int index = 0;
      bool count = false;
      int value = nums[0];
      for (int i = 1; i < numsSize; i++){
          if (nums[i] == value){
              if (!count) index ++;
              count = true;
          } else {
              value = nums[i];
              index ++;
              count = false;
          }
  
          nums[index] = nums[i];
      }
      return index+1;
  }
  

• But in java, i can’t seep to find way to slice the array, so I just leave it like this instead
  

  class Solution {
      public int removeDuplicates(int[] nums) {
          int index = -1;
          boolean count = false;
          int value = nums[0];
          for (int n : nums) {
              if (index == -1) {
                  index += 1;
                  continue;
              }
              if (n == value){
                  if (!count) index += 1;
                  count = true;
              } else {
                  value = n;
                  index += 1;
                  count = false;
              }
              nums[index] = n;
          }
          return index+1;
      }
  }