80 Remove Duplicates from Sorted Array II

Description

You are given a sorted list of integers. Your task is to modify the list in-place so that each unique element appears at most twice.

After the modification, return the new length of the list. The first k elements of the list should contain the allowed values, and the order should remain unchanged.

Elements beyond the first k positions can be ignored.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

---

Example 1

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

---

Example 2

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]

---

Constraints

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• The input list is sorted in ascending order.

---

Start idx at 2 because the first two elements can always stay. Iterate from index 2 onwards. If current element is different from the element at idx - 2, the current element can appear without exceeding 2 occurrences. Copy it to nums[idx] and increase idx. Return idx which is the length.

JavaScript

var removeDuplicates = function(nums) {
    let idx = 2
    for(let i = 2; i < nums.length; i++) {
        if(nums[i] !== nums[idx-2]) {
            nums[idx++] = nums[i]
        }
    }
    return idx
};

TypeScript

function removeDuplicates(nums: number[]): number {
    let idx = 2
    for(let i = 2; i < nums.length; i++) {
        if(nums[i] !== nums[idx - 2]) {
            nums[idx++] = nums[i]
        }
    }
    return idx
};

Time Complexity: O(n)
Space Complexity: O(1)