Remove Duplicates from Sorted Array solution using TypeScript
Below is my TypeScript solution to the LeetCode "Remove Duplicates from Sorted Array" question.
This solution iterates over the array using a two-pointer approach. When the second pointer encounters a duplicate value, it just iterates past it. When the second pointer encounters a non-duplicate value, any duplicate values encountered between the first pointer and second pointer will be spliced out of the array. The first pointer will then move to the same value as the second pointer, which will be offset to account for the smaller array.
Time Complexity:
In the worst case, this algorithm will need to iterate over each element in the array once and splice the array once for every set of duplicates. For example, [0, 0, 0, 1, 2, 3]
has one set of duplicates, [0, 0 ,0]
, which means the array will be iterated over once and one splice operation will occur. The Array.splice
method has a time complexity of O(n). This makes the time complexity of this solution O(m * n) where m represents the number of duplicate sets and n represents the number of items in the array.
Space Complexity: The following approach uses a constant amount of space, making the space complexity O(1).
/**
* Remove Duplicates from Sorted Array
* Given a sorted array nums, remove the duplicates
* in-place such that each element appear only once
* and return the new length.
*
* Space Complexity: O(1)
* Time Complexity: O(m * n)
* m = the sets of duplicates plus 1: [1,1,1,2] has m of 2
* n = the number of elements in the array
*
* removeDuplicates([1]) // 1, array = [1]
* removeDuplicates([1,1,1,2,2]) // 2, array = [1,2]
*/
function removeDuplicates(nums: number[]): number {
// create two pointers
let ptr1 = 0;
let ptr2 = 0;
// handle 0 and 1 base case
if (nums.length < 2) {
return nums.length;
}
// iterate over the array from left to right
while(ptr2 < nums.length) {
ptr2 += 1;
// when a non-duplicate value is found
if (nums[ptr1] !== nums[ptr2]) {
// splice out any prior duplicate values
let duplicates = ptr2 - ptr1 - 1;
if (duplicates) {
nums.splice(ptr1, duplicates);
}
// reset the pointers to account for smaller array
ptr2 = ptr2 - duplicates;
ptr1 = ptr2;
}
}
return nums.length;
}