Leetcode: Remove Duplicates from Sorted Array II
This question is asked very commonly on Facebook and Microsoft. It is another question where we are supposed to modify an array in place.
Given the sorted array nums, I want to remove the duplicates in place such that the duplicates appear at most twice, and return the length. I'm not allowed to allocate extra space for another array.
Here are the examples:
Example 1:
Input : nums = [1, 1, 1, 2, 2, 3]
Output: 5, nums = [1, 1, 2, 2, 3]
The length is 5 because we delete the repeated elements
Example 2:
Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
Output: 7, nums = [0, 0, 1, 1, 2, 3, 3]
The solution that I want to enumerate here is to pop the unwanted duplicates. The input array is sorted and all the duplicates are next to each other. For each number of an array if we declare the number of duplicates is over 2 we simply remove them from the list of elements.
We want to start at index 1. In the array, we want to process one element at a time. If we find the current element is the same as a previous element, we increment count, and see if count is greater than 2, and if so, we have encountered an unwanted duplicate, which we need to remove from the array. We can use the pop() delete() or remove() operation what we can code seperately to remove the element and shift everything from the right side of an array to the left.
We then after processing the elements, need to return the length of the final array. The following is the code on how to do things:
class Solution {
public int[] remElement(int[] arr, int index) {
//shift all the elements to the left.
for(int i = index + 1; i < arr.length; i++) {
arr[i - 1] = arr[i];
}
return arr;
}
public int removeDuplicates(int[] nums) {
int i = 1;
int count = 1;
int length = nums.length;
while(i < length) {
//increment the count
if(nums[i] == nums[i - 1]) {
count++;
//remove an element and shift all the elements to the left and decrement array length
if(count > 2) {
this.remElement(nums, i);
i--;
length--;
}
} else {
//reset the count
count = 1;
}
i++;
}
return length;
}
}
The next approach I want to go over is overwriting unwanted duplicates, which is inspired by the fact that the problem statement asks us to return the new length of an array from the function. If all we had to do was remove elements we don't actually need to remove elements from the array.
We need a two-pointer approach where one pointer iterates over the original set of elements and another one keep track of the next empty location in the array to overwrite. We also keep a variable, count that keeps track of the count of a particular element of an array. Start at index 1 and process one element at a time in the array.
We iterate through the array and first see if the current element is the same as the previous element if so, we increment the count, but if the value of count > 2 then we move forward and increment i not j for progress.
If we encounter the current element is not the same, we increment both i and j, and reset the count to 1 and copy the location to the j location, also known as an overwrite. J will always be the location where the next element can be copied into an array. Hopefully, the code will make more sense by now.
class Solution {
public int removeDuplicates(int[] nums) {
int j = 1;
int count = 1;
for(int i = 1; i < nums.length; i++) {
if(nums[i] == nums[i - 1]) {
count++;
} else {
count = 1;
}
//"delete" the elements by replacing the j with the i pointer ahead, then move the j pointer.
if(count <= 2) {
nums[j] = nums[i];
j++;
}
}
return j;
}
}
Comments
Post a Comment