/ Data Structure and Algorithms  

Leetcode 80. Remove Duplicates from Sorted Array II

Question



Remove duplicates from a sorted array in-place, such that duplicates appears at most twice.

Similar Questions

Solution

Make use of 2 pointers. Slow pointer point to the element that satisfy the condition (appears at most twice). Fast pointer always move forward and loop through the array. We can use a variable to record how many times the element of slow pointer have occurred.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int slow = 0;
int fast;
// count to mark number of same number
int count = 1;

// fast pointer always increase
for (fast = 1; fast < nums.length; fast++) {
    if (nums[slow] == nums[fast]) {
        // 2 pointers point to same number, but count = 1
        // we can increase slow pointer
        if (count < 2) {
            slow++;
            nums[slow] = nums[fast];
            count++;
        }
    // 2 pointers point to different number
    // reset count = 1
    } else {
        slow++;
        nums[slow] = nums[fast];
        count = 1;
    }
}

return slow + 1;