Leetcode 26. Remove Duplicates from Sorted Array

Problem Explanation:

In this problem, you are given an array that is sorted and has duplicate values. Your task is to remove the duplicates in-place and return the new length of the modified array. Since the operation should be done in-place, you are not allowed to use additional space for another array. Additionally, the time complexity should be O(1), meaning the solution should not iterate over every element more than once.

Important to note is that we're provided with a sorted array, this means repeating values will be adjacent to each other. This is a key insight to solving this problem more efficiently by checking only the preceding value to determine if the current value is a duplicate.

Example Walkthrough:

Suppose we have a sorted array [1,1,2,3,3,4,5,5]

The algorithm starts with initializing a counter i to 0. The algorithm then iterates over the array. For each value (num):

• If the counter is less than 1 (i.e., we're examining the first element), or the value is greater than the last written value nums[i-1],
  • It writes the value at the current position in the new array and increments the counter.

At the end of the algorithm, i will be the count of unique elements and the array's first i values will be unique.

This will result in an array like this: [1,2,3,4,5,...] and the function will return the length of the unique sequence, which is 5.

Approach Explanation:

This is a two-pointer technique problem. One pointer is used to iterate through the array, while the other pointer points to the location where the next unique element needs to be placed.

Python Solution:

1
2python
3class Solution:
4    def removeDuplicates(self, nums):
5        if len(nums) == 0: return 0
6
7        i = 0
8        for j in range(1, len(nums)):
9            if nums[i] != nums[j]:
10                i += 1
11                nums[i] = nums[j]
12
13        return i + 1

Java Solution:

1
2java
3class Solution {
4    public int removeDuplicates(int[] nums) {
5        if (nums.length == 0) return 0;
6        int i = 0;
7        for (int j = 1; j < nums.length; j++) {
8            if (nums[j] != nums[i]) {
9                i++;
10                nums[i] = nums[j];
11            }
12        }
13        return i + 1;
14    }
15}

Javascript Solution:

1
2javascript
3let removeDuplicates = function(nums) {
4    if (nums.length === 0) return 0;
5    let i = 0;
6    for (let j = 1; j < nums.length; j++) {
7        if (nums[j] != nums[i]){
8            i++;
9            nums[i] = nums[j];
10        }
11    }
12    return i + 1;
13};

C++ Solution:

1
2c++
3class Solution {
4public:
5    int removeDuplicates(vector<int>& nums) {
6        if (nums.size() == 0) return 0;
7        int i = 0;
8        for (int j = 1; j < nums.size(); j++) {
9            if (nums.at(j) != nums.at(i)) {
10                i++;
11                nums.at(i) = nums.at(j);
12            }
13        }
14        return i + 1;
15    }
16};
17

C# Solution:

1
2c#
3public class Solution {
4    public int RemoveDuplicates(int[] nums) {
5        if (nums.Length == 0) return 0;
6        int i = 0;
7        for (int j = 1; j < nums.Length; j++) {
8            if (nums[j] != nums[i]) {
9                i++;
10                nums[i] = nums[j];
11            }
12        }
13        return i + 1;
14    }
15}

In conclusion, the key to solving this problem lies in efficient manipulation of the given sorted array, utilizing the pointers technique to rewrite over the redundant elements and therefore reduce storage duplication as per the problem's constraints.

It's important to point out that this solution doesn't completely eliminate the duplicate values from the array, but rather overwrites them. This maintains the original length of the array, but allows us to ignore the remaining unoverwritten duplicate entries, hence "removing" duplicates in-place.

Remember, this solution is specifically optimal when dealing with a sorted array, since we can rely on repeated values being adjacent to each other. For unsorted arrays, a different approach involving hashing or sorting the array first may be needed.

Each of these different language solutions tackles the problem in the same way, differing only in syntax. They all start with checking if the array is empty, then iterate through the array using two pointers: one to track the location of the last non-duplicate, and one to find the next non-duplicate. The non-duplicate number is then moved to the position right after the last non-duplicate. These steps repeat until the end of the array is reached. By returning the last non-duplicate's location plus one, we effectively gain the count of unique elements in the array, ignoring any remaining old duplicates. This is how our in-place removal of duplicates works.