# Remove Duplicates from Sorted Array
# Links
Remove Duplicates from Sorted Array
Get the code & notes on
# Problem Description
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.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
# Examples
Ex 1) Input: nums = [1, 1, 2]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Ex 2) Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
# Constraints
nums is sorted in non-decreasing order.
# What does In-Place mean?
Let's start by defining in-place which is an algorithm that transforms input using no auxiliary data structure.
So, we cannot allocate extra space for another array, a hash table, or any other data structure.
Another way of saying this is we must use O(1) extra memory.
# Removing (or Moving) Duplicates & Maintaining Relative Order
In JavaScript we can change the length of an array by adding or removing elements, but in other languages like C for example we cannot change the length of an array after it's created.
So, to get around this we're told we can place the result in the first part of nums.
Recall the formal description from earlier: if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result, and it doesn't matter what is left after the first k elements.
The examples from earlier should make this clearer:
Ex 1) Input: nums = [1, 1, 2]
Notice:
The output maintains the relative order for nums by keeping the elements we care about in non-decreasing order.
Also, recall if we're moving the duplicates it doesn't matter what we leave after the kth element, so those elements were denoted with underscores.
Ex 2) Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Notice:
The output maintains the relative order again for nums by keeping the elements we care about in non-decreasing order.
And again, recall if we're moving the duplicates it doesn't matter what we leave after the kth element, so those elements were denoted with underscores.
# How to Modify nums In-Place?
We're told we can only modify nums in-place.
Let's start with nums = [1, 1, 1, 2, 2], and see if we can come up with some way to move around the elements to get our desired output.
Let's start by taking our 1st element in nums and compare it with the 2nd element, then we can compare the 2nd element with the 3rd and so on...
1st Iteration:
- 2nd Iteration:
- 3rd Iteration:
- 4th Iteration:
After the 4th iteration, there's nothing left to compare nums[4] with, so that's the last iteration we need.
During our iterations we had to keep track of our current element in nums which we'll call nums[i] and the next element in nums which will be nums[i + 1].
We also had to keep track of which element we needed to replace in nums if we ran into an element we hadn't seen before which we'll call nums[j].
So, to implement this we'll loop over nums from the beginning to the length of nums - 1 since when we get to the last element there's nothing else for us to compare it with.
On each iteration we'll compare the current element of nums which is nums[i] with the next element of nums which is nums[i + 1].
If they're not equal then we'll set nums[j] = nums[i + 1] where j gets initialized to 1, and we'll increment j every time nums[i] doesn't equal nums[i + 1].
We also need to remember the case of nums.length = 0 which means we have no elements in our array, so we'll just return 0.
# Implementation
var removeDuplicates = function(nums) {
const numsLength = nums.length;
if (numsLength === 0) {
return 0;
}
let j = 1;
for (let i = 0; i < numsLength - 1; i++) {
if (nums[i] !== nums[i + 1]) {
nums[j] = nums[i + 1];
j++;
}
}
return j;
};
nums = [1, 1, 1, 2, 2];
console.log('k =', removeDuplicates(nums), 'nums =', nums);