Remove Duplicates from Sorted Array II
Problem
Given a sorted integer array nums, remove duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array; modify the input array in-place with O(1) extra memory.
- 1 ≤ nums.length ≤ 3 * 10⁴
- −10⁴ ≤ nums[i] ≤ 10⁴
- nums is sorted in non-decreasing order
Example
nums = [1,1,1,2,2,3]5The algorithm allows each element to appear at most twice. Initially, the array has three '1's. The first two '1's are kept, but the third is removed by overwriting. The resulting array is [1,1,2,2,3], and the returned length is 5.
Approach
Straightforward Solution
A naive approach would create a new array or use extra space to track counts, which violates the O(1) space constraint. Alternatively, a brute-force approach would repeatedly shift elements to remove duplicates, resulting in O(n^2) time complexity.
Core Observation
Because the array is sorted, duplicates appear consecutively. The problem reduces to allowing at most two occurrences of each unique element, which can be tracked by comparing the current element with the element two positions before the current write position.
Path to Optimal
The key insight is to use two pointers: one for reading the array and one for writing the allowed elements. By starting the write pointer at index 2, the algorithm compares the current read element with the element at write-2. If they differ, it means the current element can be safely written without violating the 'at most twice' rule. This approach ensures a single pass with O(n) time and O(1) space.
Optimal Approach
Initialize a write pointer at index 2. Iterate through the array starting from index 2. For each element, compare it with the element at write-2. If different, write the current element at the write pointer and increment write. Finally, return the write pointer as the new length of the array.
Time
O(n)
The algorithm makes a single pass through the array, performing constant-time comparisons and writes for each element.
Space
O(1)
Only a few integer variables are used for pointers; no additional data structures are allocated, satisfying the in-place requirement.
Pattern Spotlight
Two Pointers (In-Place Overwrite)
When removing duplicates with constraints on allowed occurrences, use a write pointer to track the position to overwrite and compare the current read element with the element at a fixed offset behind the write pointer to enforce the occurrence limit.
Solution
| 1 | class Solution: |
| 2 | def removeDuplicates(self, nums: List[int]) -> int: |
| 3 | write = 2 |
| 4 | |
| 5 | for i in range(2, len(nums)): |
| 6 | if nums[i] != nums[write - 2]: |
| 7 | nums[write] = nums[i] |
| 8 | write += 1 |
| 9 | |
| 10 | return write |
Step-by-Step Solution
Initialize Write Pointer to Allow First Two Elements
| 3 | write = 2 |
Objective
To set the starting position for writing allowed elements, assuming the first two elements are always valid.
Key Insight
Since duplicates are allowed up to twice, the first two elements can always be kept. Starting the write pointer at index 2 means the algorithm only needs to check from the third element onward whether to overwrite or skip, simplifying boundary conditions and ensuring correctness.
Interview Quick-Check
Core Logic
Starting the write pointer at 2 leverages the problem constraint that up to two duplicates are allowed, so the first two elements are always included.
State & Boundaries
The loop starts from index 2, ensuring the write pointer and read pointer do not overlap incorrectly.
Iterate Through Array and Overwrite Allowed Elements
| 5 | for i in range(2, len(nums)): |
| 6 | if nums[i] != nums[write - 2]: |
| 7 | nums[write] = nums[i] |
| 8 | write += 1 |
Objective
To scan the array from the third element, selectively overwriting elements to maintain at most two duplicates.
Key Insight
By comparing the current element with the element at write-2, the algorithm determines if the current element has appeared fewer than twice in the processed segment. If so, it writes the element at the write pointer and increments it. This ensures that no element appears more than twice while preserving relative order.
Interview Quick-Check
Core Logic
The key condition `nums[i] != nums[write - 2]` enforces the 'at most twice' rule by comparing with the element two positions behind the write pointer.
Common Pitfalls & Bugs
Failing to start the write pointer at 2 or incorrectly comparing elements can lead to allowing more than two duplicates or overwriting incorrectly.
Complexity
This single pass loop ensures O(n) time complexity with O(1) space.
Return the Length of the Modified Array
| 10 | return write |
Objective
To return the count of elements retained after removing excess duplicates.
Key Insight
The write pointer tracks the position where the next allowed element would be written, so it also represents the length of the array segment containing valid elements. Returning this value provides the new length as required.
Interview Quick-Check
Core Logic
Returning the write pointer value gives the length of the array with duplicates allowed at most twice.
Line Analysis
This solution has 1 Critical line interviewers watch for.
if nums[i] != nums[write - 2]:Check if the current element differs from the element two positions before the write pointer.
This comparison enforces the 'at most twice' rule by ensuring that the current element is not a third or further duplicate of the same value already written.
write = 2Initialize the write pointer at index 2 to allow the first two elements by default.
Starting at 2 leverages the problem constraint that up to two duplicates are allowed, so the first two elements are always included without checks.
return writeReturn the write pointer as the new length of the array.
The write pointer indicates the length of the array segment containing allowed elements, fulfilling the problem's requirement to return the new length.
nums[write] = nums[i]Overwrite the element at the write pointer with the current element.
Writing the current element at the write pointer updates the array in-place to maintain the allowed duplicates and preserve order.
write += 1Increment the write pointer to prepare for the next allowed element.
Advancing the write pointer tracks the boundary of the valid array segment and ensures subsequent writes do not overwrite valid data.
for i in range(2, len(nums)):Iterate through the array starting from the third element (index 2).
Beginning iteration at index 2 aligns with the write pointer and ensures that the algorithm only processes elements that might violate the duplicate constraint.
Test Your Understanding
Why does comparing the current element with the element at write-2 ensure that duplicates appear at most twice?
Because the array is sorted, if the current element equals the element at write-2, it means it has already appeared twice in the array segment before the write pointer. Skipping such elements prevents more than two occurrences.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Remove Duplicates from Sorted Array II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove Duplicates from Sorted Array II drill