Intuition 🤔

sliding window of size 3를 사용해야했다.
window에 2개까지의 같은 숫자가 들어올땐 slow pointer과 fast pointer 둘 다 움직인다. 하지만 3개째에서는 fast pointer만 움직여 non-duplicate number를 찾는다.

Deep dive 🙏

[a, a, b]의 sliding window와 c를 가리키는 fast pointer는 가능할까?

만약 가능하다면 c는 b를 overwrite해 non-duplicate인 element를 없애는 것이다.

3가지 경우의 수가 있다.
1. 처음 시작할때부터 [a, a, b] 와 fastPointer = c로 시작한다.
불가능하다. 왜냐하면 처음 시작할땐 fastPointer == slowPointer이기 때문이다.

2. slow pointer과 fast pointer이 둘 다 이동한 후 이 상태에 다다름.

이 경우 fast pointer는 b의 duplicate check를 하지 않은채 c로 스킵한 것이 된다. b < c 이기 때문에 바로 전 상태의 window는
[?, a, a] 와 fastPointer = b <= 여야 한다. 하지만 a < b이기 때문에 ? 는 무조건 <= a < b이다. 그 뜻은 window[2]에 b가 overwrite 되어야한다는 뜻이지만 그렇지 않았다. 그러므로 이 경우도 불가능하다.

3. fast pointer 만 이동한 후 이 상태에 다다름.
   그 뜻은 전의 window 상태도 [a, a, b]라는 뜻이다. 그 뜻은 if check에서 window[0]과 fastPointer의 값이 같았다는 뜻인데, sorted array이기 때문에 a 후 b, 다음 다시 a가 나오는 것은 불가능하다.

그러므로 이 상태의 window에 다다를 수 없다.

답안

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 3) {
            return nums.length;
        }

        int slowPointer = 2; 

        for (int fastPointer = 2; fastPointer < nums.length; fastPointer++) {
            if (nums[fastPointer] != nums[slowPointer - 2]) {
                nums[slowPointer] = nums[fastPointer]; 
                slowPointer++; 
            }
        }
        
        return slowPointer; 
    }
}