80. Remove Duplicates from Sorted Array II

📝 Problem Details

• Title: 80. Remove Duplicates from Sorted Array II
• Link: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
• Difficulty: Medium
• Tags/Categories: {{tags/categories}}

input array nums sorted in ascending order remove some duplicates in-place such that each unique element appears at most twice relative order of the elements should be kept the same

💡 Explanation of Solution

This problem is a variation of the classic “remove duplicates” problem, but with a twist:
You are allowed to keep at most two duplicates of each number in a sorted array.

We use the two pointers technique:

• One pointer i keeps track of the position where the next valid element should go.
• The other pointer j scans through the array.

*Key Idea:

• Since the array is sorted, all duplicates appear consecutively.
• We allow the first two occurrences of each number and skip the rest.
• If nums[j] != nums[i - 2], it means it’s either:
  • a new number (never seen before),
  • or the second duplicate (which is allowed). So we copy nums[j] to nums[i] and increment i.

⌛ Complexity Analysis

Time Complexity: O(n)
- We iterate through the array once with pointer j.

Space Complexity: O(1)
- We modify the array in-place with no extra space used.

💻 Implementation of Solution

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0; // pointer to place the next valid number
 
        for (int num : nums) {
            // if i < 2, always add the number (first two elements)
            // if current num != num at i - 2, it's allowed
            if (i < 2 || num != nums[i - 2]) {
                nums[i] = num;
                i++;
            }
        }
 
        return i;
    }
};