Remove Duplicates from Sorted Array - LeetCode Solution in C++, Java, Python

1. Introduction

In this blog post, we will provide a LeetCode solution for the "Merge Sorted Array" problem in C++, Java, and Python languages.

The "Remove Duplicates from Sorted Array" problem involves modifying a sorted array in-place to remove all duplicates. The goal is to have each unique element appear only once and return the new length of the array without duplicates.

2. Problem

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. Then return the number of unique elements in nums.

3. Solution in C++

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int i = 0; // Pointer for placing the next unique element
    for (int j = 1; j < nums.size(); j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1; // Length of the array without duplicates
}

Explanation:

1. Iterate through nums with two pointers i and j.

2. If nums[j] is different from nums[i], increment i and copy nums[j] to nums[i].

3. The process ensures that duplicates are skipped, and only unique elements are retained.

4. The final value of i + 1 gives the count of unique elements.

4. Solution in Java

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

Explanation:

1. Use two pointers i and j to traverse the array.

2. When a new unique element is found at j, increment i and copy that element to nums[i].

3. This procedure effectively keeps unique elements and removes duplicates.

4. The count of unique elements is given by i + 1.

5. Solution in Python

def removeDuplicates(nums):
    if not nums:
        return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

Explanation:

1. Iterate over the array with two indices i and j.

2. If a new unique element is encountered at j, increase i and update nums[i] with nums[j].

3. This approach maintains the order of unique elements and excludes duplicates.

4. The number of unique elements is i + 1.


Comments