Friday, June 19, 2015

Remove Duplicates from Sorted Array II | Leetcode

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

For example,
Given sorted 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.

---

Solution: Keep an index of the last element that you want to keep as part of the de-duplicated array. Keep the last seen character and also the count of the number of times the same character has been seen. Traverse through the array, moving valid numbers to the index of the last valid element. When done iterating, the current index is the length of the new sub-array.
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int lastNum = nums[0];
        int lastIndex = 1;
        for (int i = 1, count = 1; i < nums.length; i++) {
            if (nums[i] == lastNum) {
                if (++count > 2) continue;
            } else {
                count = 1;
                lastNum = nums[i];
            }
            nums[lastIndex++] = lastNum;
        }
        return lastIndex;
    }
}

No comments: