LeetCode 80.

Intuition

An intuitive thought: iterate the given array and record the steps that number on current index needed to be replaced forward. Then, this implementation’s time complexity will be O(n).

Approach

• set a variable to record the previous duplicated number
• set another variable to count current duplicated number of values
• set a variable to record how many steps to move value on current index to targeted index
• set a pointer to iterate the given array

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

class Solution {
    public int removeDuplicates(int[] nums) {
        int prev = 10001, count = 0;
        int pt = -1, move = 0;
        while (++pt < nums.length) {
            if (nums[pt] == prev) {
                if (++count > 2) {
                    move++;
                }
            }else{
                prev = nums[pt];
                count = 1;
            }
            nums[pt - move] = nums[pt];
        }
        return nums.length - move;
    }
}

Check out the description of this problem at LC 80.