LeetCode Problem

Problem Description

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

Examples

Input: [1,1,2]
Output: 2

Input: [0,0,1,1,1,2,2,3,3,4]
Output: 5

Constraints

0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in non-decreasing order.

Follow-up

Approach to Solve

Use two pointers to remove duplicates in-place.

Code Implementation

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

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int writeIndex = 1;
        for (int readIndex = 1; readIndex < nums.length; readIndex++) {
            if (nums[readIndex] != nums[readIndex - 1]) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int writeIndex = 1;
        for (int readIndex = 1; readIndex < nums.size(); readIndex++) {
            if (nums[readIndex] != nums[readIndex - 1]) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }

Explanation

This solution uses two pointers to remove duplicates in-place. Here's a detailed explanation of the algorithm:

Check if the array is empty: If the input array is empty, return 0.
Initialize the write index: Start with a write index of 1, which points to the first position where a new unique element can be written.
Iterate through the array: Use a read index to traverse the array starting from the second element.
Compare elements: For each element, compare it with the previous element (nums[readIndex - 1]). If it's different, write it to the position indicated by the write index and increment the write index.
Return the new length: After the loop, the write index will be at the position where the last unique element was written. This value represents the new length of the array after duplicates have been removed.

This approach ensures that the duplicates are removed in-place and the relative order of the elements is preserved. The time complexity is O(n), where n is the length of the array, because each element is processed exactly once.

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1), as we only use a constant amount of extra space for the write index.

Complexity

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

LeetSolved

Remove Duplicates from Sorted Array