Classic Interview 150 Problem P80: Remove Duplicates from Sorted Array II

---

Timeline

Timeline

2025-09-29

init

Two pointers

---

Problem:

P80 Remove Duplicates from Sorted Array II

https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150

This simple and direct method can still pass, but it is very inefficient, barely passing.

#include <algorithm>
#include <vector>
using std::vector;

class Solution {
public:
  int removeDuplicates(vector<int> &nums) {
    int i, n;
    n = nums.size();
    i = 0;

    while (i < nums.size()) {
      if (i >= 2 && nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2]) {
        nums.erase(nums.begin() + i);
      } else {
        i++;
      }
    }

    return nums.size();
  }
};

Using the two-pointer method (fast and slow pointers) is more efficient, ‘overwriting’ the extra elements in the original array.

• Slow pointer (slow): points to the end of the current result array.
• Fast pointer (fast): traverses the entire array.
  • If slow < 2, keep it directly (because the first two elements must be kept regardless).
  • If nums[fast] != nums[slow - 2], it means the new number has not appeared more than twice, so overwrite the value at nums[slow].
  • Otherwise, skip it.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};