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


  • 103
    T

    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


  • 0
    L

    excellent! merely using assignment makes the code was to read


  • 0
    M

    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


  • 0
    K

    simple and elegant!


  • 0
    F

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


  • 0
    L

    Vert concise solution, thank you!


  • 8
    R

    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;
        
        }

  • 2
    C

    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;
        }
    

  • 0

    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
    

  • 1

    Walking through two examples to help you understand this solution:

    alt text


  • 0
    K

    @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;
        }
    }
    

  • 0
    K

    @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;
        }
    }
    

Log in to reply
 

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