Share my O(N) time and O(1) space , short and simple solution when duplicates are allowed at most K times .


  • 6
    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 this 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;
        
        }

  • 0
    M

    good explanation !! thanks for share


  • 0
    F

    I still cannot understand why we have to look k steps backward in new updated array, why [nums[i-k]!=nums[i]] is not right?


Log in to reply
 

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