🎨Now live: Try our Free AI Image Generation Feature

Intuition
Given a sorted array, the task is to remove duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. This can be efficiently done by leveraging the fact that the array is already sorted, which allows us to use a two-pointer technique to identify and overwrite duplicates.
Approach
- If the array is empty, return 0.
- Initialize a variable
k
to 0. This will keep track of the position in the array where the next unique element should be placed. - Iterate through the array starting from the second element.
- For each element, compare it with the element at position
k
. If they are different, incrementk
and update the element at positionk
with the current element. - After the loop,
k + 1
will be the number of unique elements in the array. - Return
k + 1
.
Complexity
The time complexity is O(n), where n
is the length of the array. This is because we iterate through the array once.
Code
C++
class Solution {
public:
int removeDuplicates(vector& nums) {
int n = nums.size();
if (n == 0) return 0;
int k = 0;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[k]) {
nums[++k] = nums[i];
}
}
return k + 1;
}
};
Python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
k = 0
for i in range(1, n):
if nums[i] > nums[k]:
k += 1
nums[k] = nums[i]
return k + 1
Java
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int k = 0;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[k]) {
nums[++k] = nums[i];
}
}
return k + 1;
}
}
JavaScript
var removeDuplicates = function(ar) {
let n = ar.length;
let i = 0, k = 0;
for(let i = 0; i < n; i++)
if(ar[i] > ar[k])
ar[++k] = ar[i];
return k+1;
};