[leetcode #80] Remove Duplicates from Sorted Array II

Problem

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

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

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.

It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

・ 1 <= nums.length <= 3 * 10⁴
・ -10⁴ <= nums[i] <= 10⁴
・ nums is sorted in non-decreasing order.

Idea

Space Complexity를 O(1)로 하고 모든 원소가 최대 2개만 가질 수 있도록 만드는 문제다. 주어진 배열은 오름차순으로 정렬이 되어 있으며 새로운 배열을 만들지 않고 주어진 배열의 값을 바꿔야 한다는 제약사항이 있다.

Space Complexity가 O(1)이므로 index를 잘 조정해서 array의 값을 바꿔주면 된다. 인접한 원소의 값이 똑같은 경우가 3번 이상일 때는 탐색할 findIndex를 인접한 값이 다를 때까지로 설정한다. 매번 배열을 탐색할 때마다 1씩 증가하는 replaceIndex와 findIndex가 있기 때문에 findIndex가 가리키는 값을 항상 replaceIndex가 가리키는 값으로 설정하면 된다.

마지막으로 replaceIndex가 가리키는 값을 리턴하면 된다.

Solution

class Solution {
    public int removeDuplicates(int[] nums) {
        int replaceIndex = 0;
        int findIndex = 0;
        int cnt = 0;

        while (findIndex < nums.length) {
            if (findIndex < nums.length-1 && nums[findIndex] == nums[findIndex+1]) {
                cnt++;
                if (cnt > 1) {
                    while (findIndex < nums.length-1 && nums[findIndex] == nums[findIndex+1]) {
                        findIndex++;
                    }
                    cnt = 0;
                }
            } else {
                cnt = 0;
            }
            nums[replaceIndex] = nums[findIndex];
            findIndex++;
            replaceIndex++;
        }

        return replaceIndex;
    }
}

Reference

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/