[Leetcode] 80. Remove Duplicates from Sorted Array II

Medium level

 

Intuition:

Seems like a straight forward question (leaning to an easy level). Since in Python you can't alter the legth of the array, we are going to iterate the given array while tracking the duplicate numbers, the position to insert, and the compared number.

 

My Solution:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        tmp = 0
        idx = 1
        dup = False
        for i, num in enumerate(nums):
            if i == 0:
                tmp = num
                continue
            
            if tmp == num:
                if not dup:
                    dup = True
                    nums[idx] = num
                    idx += 1
            else:
                tmp = num
                dup = False
                nums[idx] = num
                idx += 1
        return idx

Code is pretty self-explanatory and follows the intuition. And averages around 55ms runtime.

Time complexity: O(n)

Space complexity: O(1)

 

Crowdsourced solution:

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

Most upvoted and claims to beat 100%, but actual runtime is pretty much the same. This one is a lot simpler because it doesn't track the duplicates by having another variable track it - instead just checking the cur_idx - 2 index.