26.remove-duplicates-from-sorted-array.md

26. Remove Duplicates from Sorted Array

Two Pointers

It's sorted array, the duplicate will be always adjacent, we can use two pointers to solve this problem.

We can use read and write pointer to check the duplicate and remove it. We iterate all elements by read pointer, and if it is not duplicate, then write to the write pointer.

[1, 2, 2, 2]
// 1st iteration
[1, 2, 2, 2]
    R
    W
// 2nd iteration
[1, 2, 2, 2]
       R
       W
// 3rd iteration
[1, 2, 2, 2]
          R
       W 

def removeDuplicates(self, nums: List[int]) -> int:
    read = 1
    # It's the next position to write
    write = 1
    while read < len(nums):
        if nums[write - 1] != nums[read]:
            nums[write] = nums[read]
            write += 1
        read += 1
    return write

# Or different definition of write pointer
def removeDuplicates(self, nums: List[int]) -> int:
    read = 1
    # The current written position 
    write = 0
    while read < len(nums):
        if nums[write] != nums[read]:
            write += 1
            nums[write] = nums[read]
        read += 1
    return write + 1

fun removeDuplicates(nums: IntArray): Int {
    var write = 0 // The current written position
    for (read in 1 until nums.size) {
        if (nums[write] != nums[read]) {
            write++
            nums[write] = nums[read]
        }
    }
    return write + 1
}

// Or different definition of write pointer
fun removeDuplicates(nums: IntArray): Int {
    var write = 1 // The next position to write
    for (read in 1 until nums.size) {
        if (nums[write - 1] != nums[read]) {
            nums[write++] = nums[read]
        }
    }
    return write
}

• Time Complexity: O(n) for only one for-loop.
• Space Complexity: O(1) for modify the array in-place.