Dare2Solve
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.
k
to 0. This will keep track of the position in the array where the next unique element should be placed.k
. If they are different, increment k
and update the element at position k
with the current element.k + 1
will be the number of unique elements in the array.k + 1
.The time complexity is O(n), where n
is the length of the array. This is because we iterate through the array once.
class Solution {
public:
int removeDuplicates(vector<int>& 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;
}
};
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
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;
}
}
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;
};