# Remove Duplicates from Sorted Array Leetcode Solution

Difficulty Level Easy

## Problem Statement

The Remove Duplicates from Sorted Array Leetcode Solution – says that you’re given an integer array sorted in non-decreasing order. We need to remove all duplicate elements and modify the original array such that the relative order of distinct elements remains the same and, report the value of k which denotes the first k elements of the original array containing only distinct elements.

Note that after the first k elements, it doesn’t matter what the elements are, but the first k elements of the original array must contain all distinct elements of the input array with the relative order of distinct elements being the same.

## Example:

`Input: nums = [3,3,4,4]`
```Output: 2
nums = [3,4,_,_]```

Explanation:

• All unique elements are:- [3,4], Hence k = 2.
• Fill all unique elements from the beginning of the input array keeping the relative order of unique elements the same.
• [3,4,_,_] is the modified array where _ denotes any element.
• Note that, we need to take care that all unique elements must be placed among the first k place of the input array.
`Input: nums = [1,1,2]`
```Output: 2
nums = [1,2,_]```

Explanation:

• All unique elements are placed at the first 2 positions of the input array.
• k = 2 is our answer.

## Approach

### Idea:

1. The main idea is to solve this problem is to consider all subarrays one by one having the same elements.
2. Keep an index k = 0, which states that the first k elements are already taken.
3. Consider a subarray [i,j-1] where all elements have same value(x). Substitute nums[k] = x, and increment the index k by 1 since we are done with the current unique element and had placed this at the correct position. Also, change index i to j.
4. Repeat step 2 until we’re done with all the unique elements.
5. Finally, return k which is our answer (number of unique elements). Also, note that all unique elements are placed at first k positions and their relative order remains the same.

## Code

### Remove Duplicates from Sorted Array Leetcode C++ Solution:

```class Solution {
public:
int removeDuplicates(vector<int>& nums)
{
int k = 0,n = nums.size();
for(int i=0;i<n;i++){
int j = i;
while(j<n and nums[i]==nums[j]){
j++;
}
nums[k++] = nums[i];
i = j -1;
}
return k;
}
};```

### Remove Duplicates from Sorted Array Leetcode Java Solution:

```class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length,k = 0;
for(int i=0;i<n;i++){
int j = i;
while(j<n && nums[i]==nums[j]){
j++;
}
nums[k++] = nums[i];
i = j - 1;
}
return k;
}
}```

## Complexity Analysis for Remove Duplicates from Sorted Array Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N) since, we are iterating for every element twice, hence O(2N) = O(N).

### Space Complexity

The space complexity of the above code is O(1) since we’re not taking any extra space like a vector or an array to solve this problem.

Translate »