80. Remove Duplicates From Sorted Array

Problem Statement in English

You’re given a sorted array nums.

Your task is to ensure that any element appears at most twice, and preserve the overall order of elements while doing so.

You must modify the array in-place, and return an integer that indicates the length of nums that contains the answer. You must use 1 based indexing instead of 0 indexing.

Approach

This problem is a slight variation of another one that I’ve covered.

Our approach will be to use 2 pointers, l and r, to iterate over the sorted array. We’ll also use a variable strike to keep track of the number of times the last element appeared.

We’ll use l to keep track of the last element that we’ve modified. Because of this, l indicates the size of the modified array.

Anytime we want to modify the array, we’ll increment l by 1, and make the value pointed to by l (basically the last value) the same as the value pointed to by r.

Now, as we move r, a couple things can happen:

• When the elements pointed to by the l and r pointers are the same, and strike is 1, we’ll move the l pointer forwards, and make the value pointed to by the l pointer the same as the value pointed to by the r pointer - we’ve now seen that element twice.

• When strikehits 2, we’ll ignore the element pointed to by the r pointer, and move the r pointer forwards.

• When the elements pointed to by the l and r pointers are different, we’ll move the l pointer forwards, and make the value pointed to by the l pointer the same as the value pointed to by the r pointer - essentially copying the value of the r pointer into the spot that the l pointer points to.

Example

Consider the array [1, 1, 1, 2, 2, 3]. Each diagram depicts what happens after an iteration.

• strike = $1$

  1	1	1	2	2	3
  L	R

• strike = $2$

  1	1	1	2	2	3
  	L	R

• strike = $1$

  1	1	2	2	2	3
  		L	R

• strike = $2$

  1	1	2	2	2	3
  			L	R

• strike = $1$

  1	1	2	2	3	3
  				L	R

And we return $5$ (l + $1$ = $4 + 1 = 5$).

Solution in Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # edge case
        if len(nums) == 1:
            return 1

        # init pointers
        l, r = 0, 1

        # indicates the number of times the last element appeared
        strike = 1

        # run the code while the right pointer is within range of the list
        while r < len(nums):
            # if the 2 pointers are pointing at the same element, and we've seen this element before
            if nums[r] == nums[l] and strike == 1:
                # indicate that we've seen this element twice now
                strike = 2
                # move the left pointer forwards
                l += 1
                # make the value pointed to by the left pointer the same as the right pointer
                # copy the value pointed to be r to the new l position
                nums[l] = nums[r]
            # if the elements are the same, and we've already seen this element twice, then do nothing
            elif nums[r] == nums[l] and strike == 2:
                pass
            # if the characters are not the same
            elif nums[l] != nums[r]:
                # indicate that this is the first time that we're seeing this character
                strike = 1
                # move the left pointer forwards
                l += 1
                # make the value pointed to by the left pointer the same as that pointed to by the right pointer
                # copy the value pointed to be r to the new l position
                nums[l] = nums[r]
            # move the right pointer forwards
            r += 1

        # since we must use 1 indexing instead of 0 indexing,
        # increment answer by 1
        return l + 1

Complexity

• Time: $O(n)$
  Since we iterate over $n$ elements at most.

• Space: $O(1)$
  Since we only use a few integer variables.

And we are done.