Devin's Blog

Remove Duplicates From Sorted Array

2 min read

TARGET DECK: Leetcode FILE TAGS: Easy

Intuition

  • You want to move each element that occurred to its proper position.
  • To do so, notice:
    • The first element is always in its proper position (since the array is sorted, so the first element will always remain there).
    • The first element of each grouping of duplicate elements belongs in the next position of the resultant array.
    • We do not care about the rest of the elements past the sorted position.
  • Therefore, move the first element of every new number to the position following the currently sorted positions.
  • This works since the array is sorted, since otherwise it wouldn’t be known where to stop.

Question

If you started insert_pos at 0, would it still work?

  • No, since the first element would occur in the second position (you are moving everything except the first element, and you do not check the first element).

Complexity

Runtime

Space

Code

Move End of Each Number to Proper Position

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        # 0th element is always in the correct position
        insert_pos = 1
        for i in range(n - 1):
            # Last element of the duplicate elements can be inserted into its proper position
            if nums[i] != nums[i + 1]:
                nums[insert_pos] = nums[i + 1]
                insert_pos += 1
 
        return insert_pos

Move Beginning of Each Number to Proper Position

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        # 0th element is always in the correct position
        insert_pos = 1
        for i in range(1, n):
            # First element of the duplicate elements can be inserted into its proper position
            if nums[i] != nums[i - 1]:
                nums[insert_pos] = nums[i]
                insert_pos += 1
 
        return insert_pos

Move All Duplicates to End

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

Notes

Cards

START Basic Front: Remove Duplicates From Sorted Array Back: Move the first element of every number to its proper position, starting at position 1.

END

References

Graph View