NeetCode #197LC-80MediumTwo Pointers
← Back to All Problems#197 · #80 · Remove Duplicates from Sorted Array II(删除有序数组中的重复项 II)
📌 Problem Statement & Constraints
Given an integer array
nums sorted in non-decreasing order, remove duplicates in place so that each unique element appears at most twice. Return the new length k; the first k slots must hold the result. Constraints: 1 <= nums.length <= 3 * 10^4, -10^4 <= nums[i] <= 10^4.💡 Core Algorithmic Approaches
- Generalise the Remove Duplicates template: a write pointer
kmarks the next output slot. - For each read element, write it only if it differs from the element two positions before the write pointer, i.e.
nums[k-2]. - That comparison allows each value to appear at most twice, because the third occurrence would equal
nums[k-2]. - The first two elements are always kept, so
kstarts at 2 (or at the array length if it is shorter).
💻 Benchmark Python3 Implementation
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)
k = 2 # the first two elements are always kept
for i in range(2, len(nums)):
if nums[i] != nums[k - 2]: # allow at most two occurrences
nums[k] = nums[i]
k += 1
return k⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): in place.
⚠️ Interview Pitfalls & Follow-ups
- Comparing with
nums[i-2]: this uses the read stream rather than the write stream, so it fails once elements start being skipped. Compare withnums[k-2]. - Initialising
kto 0: the first two elements need no comparison, sokstarts at 2 and the loop at index 2. - Using
nums[k-1]instead ofnums[k-2]: that enforces at most one occurrence, degenerating to the basic version. - Handling arrays of length 1 or 2: both are already valid, so the early return avoids index errors on
nums[k-2].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.