Remove Duplicates from Sorted Array II (LeetCode 80) — Simple Explanation

This problem is a great extension of the basic two-pointer technique.

Problem Understanding

We are given a sorted array.
-> We must remove duplicates in-place
-> But each element can appear at most twice

Example

Input: -> [1,1,1,2,2,3]

Output: -> [1,1,2,2,3]

Return: -> k = 5

Idea (Very Simple)

We use two pointers:

j -> reads elements
k -> writes valid elements

Key Condition
if (k < 2 || nums[j] != nums[k - 2])

What does this mean?
First 2 elements are always allowed

After that:
Compare current element with 2 positions before

If same -> skip 
If different -> include 

Why k - 2?

Because we allow maximum 2 duplicates so we check “Did we already take this number twice?”

C++ Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;

        for (int j = 0; j < nums.size(); j++) {
            if (k < 2 || nums[j] != nums[k - 2]) {
                nums[k] = nums[j];
                k++;
            }
        }

        return k;
    }
};

Dry Run (Important)

Input: -> [1,1,1,2,2,3]

j	nums[j]	k	Action	Result
0	1	0	take	[1]
1	1	1	take	[1,1]
2	1	2	skip	[1,1]
3	2	2	take	[1,1,2]
4	2	3	take	[1,1,2,2]
5	3	4	take	[1,1,2,2,3]

Complexity

Time Complexity : O(n)

Space Complexity : O(1)

No extra array used

What I Learned

• Two-pointer technique is very powerful
• Instead of counting duplicates, we can control placement
• k - 2 trick ensures at most 2 duplicates