26.Remove_Duplicates_from_Sorted_Array_(Easy).md

26. Remove Duplicates from Sorted Array (Easy)

Date and Time: Jun 5, 2024, 1:44 AM (EST)

Link: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Question:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.

• Return k.

Example 1:

Input: nums = [1, 1, 2]

Output: 2, nums = [1, 2,_]

Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.

Example 2:

Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

Output: 5, nums = [0, 1, 2, 3, 4,,,,,_]

Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.

Solution 1:

We start from 1 because the first element has to be in order since nums in non-decreasing order. Then we only increment k when there is a "gap" between two elements that are different to each other, and replace the kth element with the new element in nums. This approach saves space complexity since we don't need to create a dP like the previous solution.

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

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2:

Leave k to replace the duplicate element at kth position. And use curr to keep track of current element, if they are not equal we update curr = val.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Use two variables to keep track of duplicate elem's index and duplicate element
        # When prev != n, means we need to replace the current duplicate elem's index

        # TC: O(n), SC: O(1)
        k = 1
        prev = nums[0]
        for n in nums:
            if n != prev:
                nums[k] = n
                k += 1
                prev = n
        return k

Time Complexity: O(n)
Space Complexity: O(1)

dp Solution:

Similar to 27.Remove Element. My logic is to leave a index k to keep track of the repeating char, and we only replace it with the next non-repeating char showing in nums.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        dP = {}
        k = 0
        for i in range(len(nums)):
            if nums[i] not in dP:
                nums[k] = nums[i]
                k += 1
            dP[nums[i]] = i
        return k

Time Complexity: O(n)
Space Complexity: O(n)