package fundamentals.array.lc080_removeduplicatesfromsortedarray2;

/**
 * Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
 * For example, Given sorted fundamentals.array nums = [1,1,1,2,2,3].
 * Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3.
 * It doesn't matter what you leave beyond the new length.
 */
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }

        // Invariant: j points to position ready to insert
        //  property-1: [0,j) elements appear no more than twice
        //  property-2: nums[j] == nums[i] ?
        // Thus
        //  to maintain 2 => must move forward j if nums[i] is different (e.g. 1,1,1(j),1,1,2(i))
        //  to maintain 1 => must copy nums[i] to nums[j] before move j
        //  when loop terminates, [0,j) is what we want
        int j = 1;
        int c = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                if (c < 2) {
                    nums[j] = nums[i];
                    j++;
                }
                c++;
            } else {
                nums[j] = nums[i];
                j++;
                c = 1;
            }
        }
        return j;
    }
}

@@ -414,39 +414,1612 @@
 n %7B%0A
-    public int removeDuplicates
+%0A    // Beautiful solution from stefan%0A    // Idea: keep num if it's different from num%5Bi-k%5D%0A    public int removeDuplicates(int%5B%5D nums) %7B%0A        final int k = 2;%0A        int i = 0;%0A        for (int num : nums) %7B%0A            if (i %3C k %7C%7C nums%5Bi - k%5D %3C num) %7B%0A                nums%5Bi++%5D = num;%0A            %7D%0A        %7D%0A        return i;%0A    %7D%0A%0A    // My 2nd: use counter to count duplicate times. O(N) time%0A    public int removeDuplicates2(int%5B%5D nums) %7B%0A        // Invariant: elements in %5B0,j) appear at most K times%0A        final int k = 2;%0A        int j = 1, count = 1;%0A        for (int i = 1; i %3C nums.length; i++) %7B%0A            if (nums%5Bi%5D == nums%5Bi - 1%5D) %7B%0A                if (++count %3C= k) %7B     // error: ++count, since nums%5Bi%5D should be counted now%0A                    nums%5Bj++%5D = nums%5Bi%5D;%0A                %7D%0A            %7D else %7B%0A                nums%5Bj++%5D = nums%5Bi%5D;%0A                count = 1;%0A            %7D%0A        %7D%0A        return j;%0A    %7D%0A%0A    // My 2nd: copy current and also next number if duplicate%0A    // but it is hard to extend for K times situation%0A    public int removeDuplicates3(int%5B%5D nums) %7B%0A        // Invariant: elements in %5B0,j) appear at most twice.%0A        int j = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B     // error: i and j must start from 0. eg.%5B1,1%5D%0A            if (i == 0 %7C%7C nums%5Bi%5D != nums%5Bi - 1%5D) %7B%0A                nums%5Bj++%5D = nums%5Bi%5D;%0A                if (i %3C nums.length - 1 && nums%5Bi + 1%5D == nums%5Bi%5D) %7B%0A                    nums%5Bj++%5D = nums%5B++i%5D;%0A                %7D%0A            %7D%0A        %7D%0A        return j;%0A    %7D%0A%0A    // My 1st%0A    public int removeDuplicates1
 (int

leetcode-080 remove duplicates from sorted array 2