Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 80] Remove Duplicates From Sorted Array II

Question

link

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].

Stats

Frequency 2
Difficulty 2
Adjusted Difficulty 3
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an easy question

Code

my first code

public int removeDuplicates(int[] A) {
    if (A.length == 0) return 0;
    int insert = 1, pre = 0, cur = 1, count = 1;
    while (cur < A.length) {
        if (A[pre] == A[cur]) {
            if (count == 1) {
                count = 2;
                A[insert] = A[pre];
                insert++;
                pre++;
            }
        } else if (A[pre] != A[cur]) {
            count = 1;
            A[insert++] = A[cur];
            pre = cur;
        }
        cur ++;
    }
    return insert;
}

my second code

public int removeDuplicates(int[] A) {
    int len = A.length;
    if (len < 3) return len;
    int left = 0, right = 0;
    boolean dup = false;
    while (right < len) {
        if (right == 0 || A[right] != A[right - 1]) {
            A[left ++] = A[right ++];
            dup = false;
        } else if (! dup) {
            A[left ++] = A[right ++];
            dup = true;
        } else right ++;
    }
    return left;
}