LeetCode 27: Remove Element (Two Pointers Overwrite)

Today we solve LeetCode 27 - Remove Element.

Source: https://leetcode.com/problems/remove-element/

English

Problem Summary

Given an integer array nums and an integer val, remove all occurrences of val in-place and return the number of remaining elements k. The first k positions of nums should contain the kept values.

Key Insight

Maintain a write pointer k for the next kept slot. Scan each number once: if it is not val, write it to nums[k] and increment k. This keeps the prefix [0, k) always valid.

Brute Force and Why Insufficient

A naive way repeatedly deletes elements or shifts the tail each time we see val. In worst case this causes many shifts and can degrade toward O(n^2). The overwrite-pointer method does a single linear pass.

Optimal Algorithm (Step-by-Step)

1) Initialize k = 0.
2) Iterate every element x in nums.
3) If x != val, set nums[k] = x and increment k.
4) Return k after traversal.

Complexity Analysis

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

Common Pitfalls

- Forgetting that only the first k elements matter after processing.
- Incrementing k even when current number equals val.
- Trying to preserve original tail order beyond k (not required).

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

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for (int x : nums) {
            if (x != val) {
                nums[k++] = x;
            }
        }
        return k;
    }
}

func removeElement(nums []int, val int) int {
    k := 0
    for _, x := range nums {
        if x != val {
            nums[k] = x
            k++
        }
    }
    return k
}

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int x : nums) {
            if (x != val) {
                nums[k++] = x;
            }
        }
        return k;
    }
};

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        k = 0
        for x in nums:
            if x != val:
                nums[k] = x
                k += 1
        return k

var removeElement = function(nums, val) {
  let k = 0;
  for (const x of nums) {
    if (x !== val) {
      nums[k++] = x;
    }
  }
  return k;
};

中文

题目概述

给定整数数组 nums 和整数 val，要求原地删除所有等于 val 的元素，并返回剩余元素个数 k。处理后只要求数组前 k 个位置是保留值。

核心思路

用写指针 k 表示“下一个可写入的保留位置”。遍历每个元素：若不等于 val，就写到 nums[k]，再 k++。这样能保证区间 [0, k) 始终是有效结果。

朴素解法与不足

朴素做法是每遇到一个 val 就把后面的元素整体左移，或做删除操作。最坏情况下会频繁移动数据，复杂度可能退化到 O(n^2)。双指针覆盖写入只需一次线性扫描。

最优算法（步骤）

1）初始化 k = 0。
2）顺序遍历数组中的每个元素 x。
3）若 x != val，执行 nums[k] = x，然后 k++。
4）遍历结束后返回 k。

复杂度分析

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

常见陷阱

- 忘记题目只关心前 k 个元素，后半段内容可忽略。
- 遇到 val 时仍错误递增 k。
- 误以为必须保持 k 之后的顺序或值。

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

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for (int x : nums) {
            if (x != val) {
                nums[k++] = x;
            }
        }
        return k;
    }
}

func removeElement(nums []int, val int) int {
    k := 0
    for _, x := range nums {
        if x != val {
            nums[k] = x
            k++
        }
    }
    return k
}

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int x : nums) {
            if (x != val) {
                nums[k++] = x;
            }
        }
        return k;
    }
};

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        k = 0
        for x in nums:
            if x != val:
                nums[k] = x
                k += 1
        return k

var removeElement = function(nums, val) {
  let k = 0;
  for (const x of nums) {
    if (x !== val) {
      nums[k++] = x;
    }
  }
  return k;
};