## DEV Community is a community of 891,295 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Remove Duplicates from Sorted Array ### Problem statement

Given a sorted array nums, remove the duplicates in-place such that each element
appears only once and returns the new length.

Do not allocate extra space for another array,
you must do this by modifying the input array in-place with O(1) extra memory.

Problem statement taken from: https://leetcode.com/problems/remove-duplicates-from-sorted-array

Example 1:

``````Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.
``````

Example 2:

``````Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: 5, nums = [0, 1, 2, 3, 4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.
``````

Constraints:

``````- 0 <= nums.length <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in ascending order.
``````

### Explanation

#### Brute force

Well, the problem says to solve it without any extra space, but the first
brute force approach we get is to count the occurrence of distinct elements
and store it in a hash (or object).

The key will be the array element and, the value will be the number of times
the element appeared in the array.

We then iterate over the hash and store the keys in a new array.

The solution requires extra space for a new array and a new hash.

#### Two pointers

To improve the above approach, we can take the advantage of a sorted array here.
We can use two pointers i and j.
We keep incrementing j till the time nums[i] == nums[j].

Let's check the algorithm below:

``````- return if nums size <= 1

- set i = 0

- Loop for j = 1; j < nums.size(); j++
- if nums[j] != nums[i]
- i++
- nums[i] = nums[j]

- return i + 1
``````

The time complexity of the above approach is O(N) and, space complexity is O(1).

##### C++ solution
``````class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 1){
return nums.size();
}

int i = 0;

for(int j = 1; j < nums.size(); j++){
if(nums[j] != nums[i){
i++
nums[i] = nums[j];
}
}

return i + 1;
}
};
``````
##### Golang solution
``````func removeDuplicates(nums []int) int {
length := len(nums)

if length <= 1 {
return length
}

i := 0

for j := 1; j < length; j++ {
if nums[i] != nums[j] {
i++
nums[i] = nums[j]
}
}

return i + 1
}
``````
##### Javascript solution
``````var removeDuplicates = function(nums) {
const length = nums.length;

if( length <= 1 ){
return length;
}

let i = 0;

for(let j = 1; j < length; j++){
if( nums[i] != nums[j] ){
i++;
nums[i] = nums[j];
}
}

return i + 1;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````nums = [0,0,1,1,1,2,2,3,3,4]

Step 1: length = nums.size()
= 10

Step 2: length <= 1
10 <= 1
false

Step 3: i = 0

Step 4: Loop for j = 1; 1 < 10
nums[i] != nums[j]
nums != nums
0 != 0
false

j++
j = 2

Step 5: Loop for j = 2; 2 < 10
nums[i] != nums[j]
nums != nums
0 != 1
true

i++
i = 1

nums[i] = nums[j]
nums = nums
nums = 1

j++
j = 3

Step 6: Loop for j = 3; 3 < 10
nums[i] != nums[j]
nums != nums
1 != 1
false

j++
j = 4

Step 7: Loop for j = 4; 4 < 10
nums[i] != nums[j]
nums != nums
1 != 1
false

j++
j = 5

Step 8: Loop for j = 5; 5 < 10
nums[i] != nums[j]
nums != nums
1 != 2
true

i++
i = 2

nums[i] = nums[j]
nums = nums
nums = 2

j++
j = 6

Step 9: Loop for j = 6; 6 < 10
nums[i] != nums[j]
nums != nums
2 != 2
false

j++
j = 7

Step 10: Loop for j = 7; 7 < 10
nums[i] != nums[j]
nums != nums
2 != 3
true

i++
i = 3

nums[i] = nums[j]
nums = nums
nums = 3

j++
j = 8

Step 11: Loop for j = 8; 8 < 10
nums[i] != nums[j]
nums != nums
3 != 3
false

j++
j = 9

Step 12: Loop for j = 9; 9 < 10
nums[i] != nums[j]
nums != nums
3 != 4
true

i++
i = 4

nums[i] = nums[j]
nums = nums
nums = 4

j++
j = 10

Step 13: Loop for j = 10; 10 < 10
false

Step 14: return i + 1
return 4 + 1 = 5
``````