Introduction
LeetCode 80: Remove Duplicates from Sorted Array II is a variation of the classic duplicate removal problem. The twist? Each element may appear at most twice instead of just once. Your task is to modify the input array in-place and return the new length.
This problem is perfect for mastering the two-pointer pattern and in-place editing of arrays in Go.
Problem Statement
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice.
Return the new length of the array after the modifications.
Do not allocate extra space; do this in-place with O(1) extra memory.
Example:
go
Input: nums = [1,1,1,2,2,3]
Output: 5, nums becomes [1,1,2,2,3,_]
go
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums becomes [0,0,1,1,2,3,3,_]
Approach: Two Pointers
Use a slow pointer (k) to track the position of the next valid element.
Iterate with a fast pointer, and for each element:
- If it's one of the first two elements, accept it (it can appear at most twice).
- Otherwise, check if the current element is not equal to the element at
k - 2. If it’s different, it means it hasn’t appeared more than twice, so keep it.
Go Implementation
go
func removeDuplicates(nums []int) int {
if len(nums) <= 2 {
return len(nums)
}
k := 2 // Start from index 2
for i := 2; i < len(nums); i++ {
if nums[i] != nums[k-2] {
nums[k] = nums[i]
k++
}
}
return k
}
Explanation
- The condition
nums[i] != nums[k-2] ensures no element appears more than twice.
- We're overwriting the array from the front, ensuring the first
k elements are valid.
- No extra space is used—just simple index manipulation.
Time and Space Complexity
MetricComplexityTime ComplexityO(n)Space ComplexityO(1)
Where n is the length of the input array.
Edge Cases
- If the array has 2 or fewer elements → return its length directly.
- All elements are unique → keep all.
- All elements are the same → keep only 2.
Conclusion
LeetCode 80 is a smart test of your understanding of in-place algorithms and pointer techniques. It enhances your ability to work with sorted arrays and constraints around frequency.
Solving this in Go gives you clear insights into slice handling, memory-safe operations, and zero-allocation strategies—which are critical for writing efficient Go code.