Leetcode 80. Remove Duplicates from Sorted Array II

Problem Explanation

You have to remove the extra occurrences of elements from a sorted array, such that each element appears at most twice.

Your task is to do this in-place which uses O(1) space complexity. Meaning you can't make another copy of the array.

For example,

Let's consider a list nums = [0,0,1,1,1,1,2,3,3]

then after removing the extra duplicates, the list should be 0, 0, 1, 1, 2, 3 and 3 with a length of 7.

The task is to return the length of the list after processing it.

Solution Approach

In this solution, we use two pointers. The first pointer i is used to point to the last processed element and the second one is used to scan through the rest of the array.

Let me illustrate the above explanation with following example.

Example

Consider an array as nums = [1,1,1,2,2,3].

We start with assumption that 0 and 1 index elements are unique. So, we initialize i = 2. Then we check for every element in nums starting from the third number, if it is greater (not equal) to the number at index i-2. If it is then we copy it to index i and increment i. At the end i will be the new length of the array.

1
2plaintext
3nums = [1,1,1,2,2,3]
4After first iteration, nums = [1, 1, 1, 2, 2, 3], i = 2
5After second iteration, nums = [1, 1, 1, 2, 2, 3], i = 3
6After third iteration, nums = [1, 1, 2, 2, 2, 3], i = 4
7After fourth iteration, nums = [1, 1, 2, 2, 3, 3], i = 5

So, the length will be 5.

Python Solution

1
2python
3class Solution:
4    def removeDuplicates(self, nums):
5        i = 0
6        for num in nums:
7            if i < 2 or num > nums[i - 2]:
8                nums[i] = num
9                i += 1
10        return i

Java Solution

1
2java
3class Solution {
4    public int removeDuplicates(int[] nums) {
5        int i = 0;
6        for (int num : nums) {
7            if (i < 2 || num > nums[i - 2]) {
8                nums[i++] = num;
9            }
10        }
11        return i;
12    }
13}

Javascript Solution

1
2javascript
3class Solution {
4    removeDuplicates(nums) {
5        let i = 0;
6        for (let num of nums) {
7            if (i < 2 || num > nums[i - 2]) {
8                nums[i++] = num;
9            }
10        }
11        return i;
12    }
13}

C++ Solution

1
2C++
3class Solution {
4public:
5    int removeDuplicates(vector<int>& nums) {
6        int i = 0;
7        for (int num : nums) {
8            if (i < 2 || num > nums[i - 2]) {
9                nums[i++] = num;
10            }
11        }
12        return i;
13    }
14};

C# Solution

1
2C#
3public class Solution {
4    public int RemoveDuplicates(int[] nums) {
5        int i = 0;
6        foreach (int num in nums) {
7            if (i < 2 || num > nums[i - 2]) {
8                nums[i++] = num;
9            }
10        }
11        return i;
12    }
13}

In all the solutions presented above, we keep iterating over the elements in the arrays and keep updating the array in-place such that at any given instance, we only keep at most two occurrences of any given number. This way, we can refactor the array to suit the conditions mentioned.## Further Explanation

This problem involves updating the input array in-place with no extra space used. The idea is simple. We need to check three numbers at a time, so our index i has to be less than the length of the array subtracted by 2 (nums.length - 2). If the current number is less than the number two steps ahead (nums[i] < nums[i+2]), then we keep the current number and move on to check the next number. If the current number is not less than the number two steps ahead, then we need to remove the current number from the array.

In all these solutions, we are leveraging the fact that the input array is sorted. If it wasn't sorted, we'd have to sort it first, which would add to the time complexity of the overall procedure.

The time complexity for each of these solutions is O(n), where n is the size of the input array. This is because we are scanning through the entire list once.

As mentioned, no extra space is used, and hence, the space complexity for each of these solutions is O(1).

These solutions are efficient and satisfy the problem constraints. However, we still have to be careful with the handling of arrays, especially when modifying them in-place.

In summary, this problem serves as a good exercise in understanding the use of the two-pointer technique in solving problems, where you seek to modify the input list or array in-place, in order to save on space complexity.

Remember, the goal here is to ensure we only have at most two occurrences of each element in the sorted array, and we achieve this by comparing the current element with the element two steps ahead and update our array accordingly.