LC26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

How does the sorted array help us

With sorted array, we know numbers that have the same value will be all next to each other and we can know how many duplicates are there by scanning forward till we see a different numbers.

Accumulated displacement

Each time we see a duplicate, we need to “squeeze” duplicates into the first appearance of the number. This squeeze will make empty space in the array.
EG: [1,2,2,3, 3] -> [1,2, EMPTY, EMPTY,3]
We need to fill the empty by the number after the duplicate.

This is done by moving all numbers after by the number of EMPTY.

We also need to accumulate the changes. If we see a duplicate at location i and squeeze it into the first appearance at location i – 1, we then need to shift all numbers after by 1. We implement this idea by shifting every number by the number of EMPTY at the beginning of the iteration.
“`python
def removeDuplicates(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
pos = 0
disp = 0
length = len(nums)

    while pos < length:
        nums[pos - disp] = nums[pos]
        while pos < length - 1 and nums[pos] == nums[pos + 1]:
            pos += 1
            disp += 1

        pos += 1

    return length - disp

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax