# Share my O(N) time and O(1) solution when duplicates are allowed at most K times

• I think both Remove Duplicates from Sorted Array I and II could be solved in a consistent and more general way by allowing the duplicates to appear k times (k = 1 for problem I and k = 2 for problem II). Here is my way: we need a count variable to keep how many times the duplicated element appears, if we encounter a different element, just set counter to 1, if we encounter a duplicated one, we need to check this count, if it is already k, then we need to skip it, otherwise, we can keep this element. The following is the implementation and can pass both OJ:

``````int removeDuplicates(int A[], int n, int k) {

if (n <= k) return n;

int i = 1, j = 1;
int cnt = 1;
while (j < n) {
if (A[j] != A[j-1]) {
cnt = 1;
A[i++] = A[j];
}
else {
if (cnt < k) {
A[i++] = A[j];
cnt++;
}
}
++j;
}
return i;
}
``````

For more details, you can also see this post: LeetCode Remove Duplicates from Sorted Array I and II: O(N) Time and O(1) Space

• excellent! merely using assignment makes the code was to read

• I wonder if the solution listed below is correct:
class Solution{
public:
int removeDuplicates(int []A,int n, int k){
if(n <= k){
return n;
}
for(int i = k; i < n; ++i){
if(A[i] != A[index-k]){
A[index++] = A[i];
}
}
return index;
}

many thanks

• simple and elegant!

• clear solution. how about write it in while loop for j?

• Vert concise solution, thank you!

• This is my short and easy to understand solution for the problem where duplicates are allowed at most `k` times.
My approach is to remain first `k` elements as it is . Now start from `k'th index` and check if the element at the position `current index - k` is
the same as new arriving element then skip this element and continue with next element . here the condition `nums[j-k]!=nums[i]` is very important because
if i will use i in place of j i.e. `nums[i-k]!=nums[i]` then it will give wrong answer because we have to look k steps backward in new updated array.

please comment if any test case fails

`````` int removeDuplicates(vector<int>& nums,int k) {
if(nums.size()<k) return nums.size(); // if array size is less than k then return the same
int i,j;
for(i=k,j=k ; i<nums.size();i++)
if(nums[j-k]!=nums[i]) nums[j++]=nums[i];
return j;

}``````

• Same concept, just some of the lines were repeated for both equal and unequal values, I have removed that.

``````public int removeDuplicates(int[] nums) {
int count=1;
int innerCount=1;
for(int i=1;i<nums.length;i++){
if(nums[i]==nums[i-1]){
innerCount++;
if(innerCount>2)
continue;
}
else{
innerCount=1;
}
nums[count++]=nums[i];
}
return count;
}
``````

• Same idea. My python version.

``````class Solution(object):
def removeDuplicates(self, nums):
if not nums: return 0
slow = 1
count = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
count += 1
if count > 2:
continue
else:
count = 1
nums[slow] = nums[i]
slow += 1
return slow
``````

• @tech-wonderland.net Here's my solution, which may actually be easier to understand for many people, but is not nearly as good as yours:

``````public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int removed = 0;

int value = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i ++) {
if (nums[i] == value) {
count ++;
} else {
count = 1;
value = nums[i];
}

// System.out.printf("value: %d, count: %d\n", value, count);

if (count > 2) {
nums[i] = Integer.MAX_VALUE;
removed ++;
}
}

Arrays.sort(nums);
return nums.length - removed;
}
}
``````

• @tech-wonderland.net Here's one that uses the same concept, but might be a little easier to parse for newcomers:

``````public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int last = 0;
int count = 1;

for (int candidate = 1; candidate < nums.length; candidate ++) {
// put the candidate into position at the end of the list we're building
nums[last + 1] = nums[candidate];

// determine if the candidate is equal to the last element in our list
boolean equal = nums[last] == nums[last + 1];

// if the candidate isn't equal to the last element in our list,
// or if the count is less than 2,
// we can append the candidate to the end of our list
if (!equal || count < 2) {
// append the candidate to the end of the list
last ++;

// update the count
count = !equal ? 1 : count + 1;
}
}

return last + 1;
}
}
``````

• My another solution can be also applied to allows k duplicates, just set int duplicates = k

``````public int removeDuplicates(int[] nums) {
int duplicates = 2, allows = duplicates;
if(nums.length==0) return 0;
int left = 1; //left pointer points to the tail of the kept elements.
for(int right = 0; right<nums.length-1; right++)
if(nums[right]!=nums[right+1]) {
nums[left++]=nums[right+1]; //update the tail of the kept elements and set left++;
allows = duplicates;//reset the number of allowed duplicates back to 2
}
else if(--allows==1) nums[left++]=nums[right+1];  //if we just met the second duplicates, update the tail of the kept elements and set left++;
return left;
}``````

• @rakesh_joshi really brilliant solution! I thought as the same as first but I keep comparing nums[i] with nums[i - k], which will give me wrong result since nums[i - k] 's value is changing along the way.

Thank you so much!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.