LC26. Remove Duplicates from Sorted Array¶

Problem Description¶

LeetCode Problem 26: 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.

Return k after placing the final result in the first k slots of nums.

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

Clarification¶

Sorted integer array
Remove duplicate in-place
Keep the relative order
Empty array?

Assumption¶

Input array has at least 2 elements.

Solution¶

Approach - Two Pointers¶

Since the array is sorted, duplicates will show up together in neighbor. Take advantage of this pattern, we will use two pointers:
- One pointer i to track the index of unique element
- The other pointer j to track the index of current element
Essentially, once an element is encountered, simply bypass its duplicates and move on to the next unique element. So
- When nums[i] == nums[j], increase j to skip the duplicate
- When nums[i] != nums[j], the duplicate ends and copy the value to nums[i+1] and increase i

C++Python

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) return 0; // later j starts with 1.

        int i = 0;
        for (int j = 1; j < nums.size(); j++) { // (1)
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }

        return i + 1; // (2)
    }
};

j starts from 1
Return number of elements instead of index

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

i starts from 1
Return number of elements instead of index

Complexity Analysis¶

Time complexity: \(O(n)\)
Iterate the whole array once.
Space complexity: \(O(1)\)
Only use two pointers.