LeetCode 80: Remove Duplicates from Sorted Array II (Keep At Most Two)

Today we solve LeetCode 80 - Remove Duplicates from Sorted Array II.

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

English

Problem Summary

Given a non-decreasing array nums, remove duplicates in-place so each unique value appears at most twice. Return the new length k. The first k elements must be the valid result.

Key Insight

Maintain a write pointer w. For each number x, keep it if either we have written fewer than 2 elements, or x != nums[w - 2]. This single condition guarantees no value is written more than twice.

Brute Force and Why Insufficient

Brute force can count frequencies and rebuild a new array, then copy back. It works but uses extra space. The problem asks for in-place modification with O(1) extra space.

Optimal Algorithm (Step-by-Step)

1) Initialize w = 0.
2) Iterate each x in nums.
3) If w < 2 or x != nums[w - 2], write nums[w] = x and increment w.
4) At the end, return w.

Complexity Analysis

Time: O(n).
Space: O(1) extra space.

Common Pitfalls

- Comparing with nums[w - 1] instead of nums[w - 2] (would keep only one copy).
- Forgetting the w < 2 guard, causing index errors.
- Returning array length instead of w.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int removeDuplicates(int[] nums) {
        int w = 0;
        for (int x : nums) {
            if (w < 2 || x != nums[w - 2]) {
                nums[w++] = x;
            }
        }
        return w;
    }
}

func removeDuplicates(nums []int) int {
    w := 0
    for _, x := range nums {
        if w < 2 || x != nums[w-2] {
            nums[w] = x
            w++
        }
    }
    return w
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int w = 0;
        for (int x : nums) {
            if (w < 2 || x != nums[w - 2]) {
                nums[w++] = x;
            }
        }
        return w;
    }
};

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        w = 0
        for x in nums:
            if w < 2 or x != nums[w - 2]:
                nums[w] = x
                w += 1
        return w

var removeDuplicates = function(nums) {
  let w = 0;
  for (const x of nums) {
    if (w < 2 || x !== nums[w - 2]) {
      nums[w++] = x;
    }
  }
  return w;
};

中文

题目概述

给你一个非递减数组 nums，要求原地删除重复元素，使每个数字最多出现两次，返回新长度 k。并保证前 k 个元素为最终结果。

核心思路

维护写指针 w。遍历当前元素 x 时，如果 w < 2（前两个元素直接保留）或 x != nums[w - 2]，就把 x 写到 nums[w] 并 w++。这样每个值最多保留两次。

朴素解法与不足

可以先统计频次，再构建新数组并拷回原数组。该做法逻辑直观，但需要额外空间，不符合题目“原地 + 常数额外空间”的要求。

最优算法（步骤）

1）初始化写指针 w = 0。
2）按顺序遍历每个元素 x。
3）若 w < 2 或 x != nums[w - 2]，写入 nums[w] = x 并 w++。
4）遍历结束返回 w。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1) 额外空间。

常见陷阱

- 误用 nums[w - 1] 比较，会把“最多两次”错误变成“最多一次”。
- 忘记处理 w < 2 的边界，导致越界。
- 返回值写错成原数组长度而不是 w。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int removeDuplicates(int[] nums) {
        int w = 0;
        for (int x : nums) {
            if (w < 2 || x != nums[w - 2]) {
                nums[w++] = x;
            }
        }
        return w;
    }
}

func removeDuplicates(nums []int) int {
    w := 0
    for _, x := range nums {
        if w < 2 || x != nums[w-2] {
            nums[w] = x
            w++
        }
    }
    return w
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int w = 0;
        for (int x : nums) {
            if (w < 2 || x != nums[w - 2]) {
                nums[w++] = x;
            }
        }
        return w;
    }
};

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        w = 0
        for x in nums:
            if w < 2 or x != nums[w - 2]:
                nums[w] = x
                w += 1
        return w

var removeDuplicates = function(nums) {
  let w = 0;
  for (const x of nums) {
    if (w < 2 || x !== nums[w - 2]) {
      nums[w++] = x;
    }
  }
  return w;
};