Leetcode: Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Analysis:
The problem is closed to the remove duplicates from the sorted array. The mainly difference is here we allow duplicates at most twice. 

Solution:
We can borrow the idea from the last post, removing duplicates from sorted array. That is, we can use two pointers, one is ahead of the other at beginning. We say j pointer is ahead of i. The major difference is we can use a counter to count how many duplicates. 

Code (Java):

public class Solution {
    public int removeDuplicates(int[] A) {
        // for array size less than 3, we just return the length
        if (A.length < 3) return A.length;
        
        int i = 0; 
        int j = 1;
        int count = 1;
        
        while (j < A.length) {
            if (A[i] == A[j] && count == 1) {
                i++;
                A[i] = A[j];
                j++;
                count++;
            } else if (A[i] == A[j] && count > 1) {
                j++;
            } else {
                i++;
                A[i] = A[j];
                j++;
                count = 1;
            }
        }
        
        return i + 1;
    }
}

Discussion:
Since the j pointer iterates the array only once, the time complexity is O(n). The space complexity is O(1) due to the in place operations. Note that in Line 13, the first time duplicates occurred, we must assign A[j] to A[i] as well. One example to explain is A = [1, 1, 1, 1, 2, 2]. If not assigned, the A would be A= [1, 1, 2, 1] instead of A = [1, 1, 2, 2].

Summary:
This problem itself is not very difficult. Remember the two pointers method in future questions. It provides us a good way to handle many string/array/linked list problems. 

Update on 9/29/14:

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int i = 0;
        int j = 1;
        int count = 1;
        
        while (j < A.length) {
            if (A[j] == A[j - 1] && count == 1) {
                A[++i] = A[j++];
                count++;
            } else if (A[j] == A[j - 1] && count > 1) {
                j++;
            } else {
                count = 1;
                A[++i] = A[j++];
            }
        }
        
        return i + 1;
    }
}

Update on 11/20/14:

public class Solution {
 public int removeDuplicates(int[] A) {
     if (A == null || A.length == 0) {
         return 0;
     }
     int i = 1;
     int j = 1;
     //int len = A.length;
     int count = 1;

     while (j < A.length) {
         if (A[j] != A[j - 1]) {
             A[i++] = A[j++];
             count = 1;
            } else {
             if (count < 2) {
                 A[i++] = A[j++];
                 count++;
                } else {
                 A[i] = A[j++];
                 //len--;
                }
            }
        }
        return i;
    }
}

Update on 9/18/15:

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int count = 1;
        int len = nums.length;
        
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
                if (count <= 2) {
                    nums[j++] = nums[i];
                } else {
                    len--;
                }
            } else {
                nums[j++] = nums[i];
                count = 1;
            }
        }
        
        return len;
    }
}