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.

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        var idx = 2;
        for(var i = 2; i < nums.length; i++) {
            if(nums[i] != nums[idx - 2]) {
                nums[idx++] = nums[i];
            }
        }
        return idx;
    }
}

Kotlin

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        var idx = 2
        for(i in 2 until nums.size) {
            if(nums[i] != nums[idx - 2]) {
                nums[idx++] = nums[i]
            }
        }
        return idx
    }
}

Scala

object Solution {
    def removeDuplicates(nums: Array[Int]): Int = {
        var idx = 2
        for(i <- 2 until nums.length) {
            if(nums(i) != nums(idx - 2)) {
                nums(idx) = nums(i)
                idx += 1
            }
        }
        idx
    }  
}

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