Loading problems...
TL;DR: To solve this problem in O(N) time and O(1) space, use a two-pointer approach where a "write" pointer builds the valid array and a "read" pointer scans for candidates, only copying numbers that are strictly greater than the element located two positions behind the current write index.
The goal of LeetCode 80, titled Remove Duplicates from Sorted Array II, is to modify a sorted integer array in-place so that duplicates appear at most twice. You must return the new length of the modified array. The relative order of elements must remain unchanged, and you cannot use extra space for a new array.
A naive approach to solving Remove Duplicates from Sorted Array II might involve using a temporary data structure to count frequencies or shifting elements repeatedly.
nums.nums[i] == nums[i+1] == nums[i+2]), remove the element at i+2 and shift all subsequent elements to the left to fill the gap.Pseudo-code (Deletion Approach):
texti = 0 while i < nums.length - 2: if nums[i] == nums[i+1] and nums[i] == nums[i+2]: remove nums[i+2] (shift all elements left) // do not increment i, check same index again else: i++ return nums.length
Why this fails:
The key intuition for the optimal solution lies in the sorted nature of the input. Because the array is sorted, all duplicates are grouped together. We do not need to know the total count of a number; we only need to ensure that for any given number x, we have not already written x twice in our result.
The standard "Remove Duplicates" (LeetCode 26) checks if nums[read] != nums[write - 1]. However, for LeetCode 80, we are allowed two instances. Therefore, the constraint relaxes to checking two positions back.
The Invariant:
We maintain a write pointer such that the subarray nums[0...write-1] contains the valid result at all times. When considering a new element at the read pointer, it is valid to include it if it is different from the element at nums[write - 2].
If nums[read] == nums[write - 2], it implies that nums[read] is also equal to nums[write - 1] (due to the sorted property). This would mean adding nums[read] creates a sequence of three identical values. We skip it.
Visual Description:
Imagine the array is divided into two parts. The left part (indices 0 to write-1) is the "clean" array. The right part is the unprocessed territory. As the read pointer advances, we look back into the "clean" array at index write-2. If the current value is compatible, we copy it to the write index and expand the clean zone.

Consider Input: nums = [1, 1, 1, 2, 2, 3]
Initialization:
write = 2, read = 2.[1, 1, 1, 2, 2, 3] (Indices 0 and 1 are implicitly kept).Iteration 1 (read = 2):
nums[read] (value 1) with nums[write - 2] (index 0, value 1).1 == 1. This is a 3rd duplicate.write remains 2.Iteration 2 (read = 3):
nums[read] (value 2) with nums[write - 2] (index 0, value 1).2 != 1. This is valid.nums[write] = nums[read]. nums becomes [1, 1, 2, 2, 2, 3].write to 3.Iteration 3 (read = 4):
nums[read] (value 2) with nums[write - 2] (index 1, value 1).2 != 1. This is valid.nums[write] = nums[read]. nums becomes [1, 1, 2, 2, 2, 3].write to 4.Iteration 4 (read = 5):
nums[read] (value 3) with nums[write - 2] (index 2, value 2).3 != 2. This is valid.nums[write] = nums[read]. nums becomes [1, 1, 2, 2, 3, 3].write to 5.End:
write = 5.[1, 1, 2, 2, 3].The algorithm guarantees correctness through the invariant that nums[0...write-1] always satisfies the problem constraints.
k=2, the subarray nums[0...1] can contain at most 2 items, which is always valid regardless of values.x at write, we check x != nums[write-2].
x >= nums[write-1] >= nums[write-2].x > nums[write-2], then we cannot have three identical values ending at x. Even if x == nums[write-1], we only have two copies (nums[write-1] and x), which is allowed.x == nums[write-2], then x == nums[write-1] == nums[write-2], which would form a triplet. By rejecting this case, we prevent any element from appearing more than twice.cppclass Solution { public: int removeDuplicates(vector<int>& nums) { // If the array has 2 or fewer elements, it's already valid. if (nums.size() <= 2) { return nums.size(); } // 'write' pointer starts at 2 because the first two elements // are always allowed in the result. int write = 2; // 'read' pointer iterates through the rest of the array. for (int read = 2; read < nums.size(); read++) { // Compare current element with the element two positions back // in the VALID part of the array (write - 2). if (nums[read] != nums[write - 2]) { nums[write] = nums[read]; write++; } } return write; } };
javaclass Solution { public int removeDuplicates(int[] nums) { // Edge case: arrays with length <= 2 require no changes. if (nums.length <= 2) { return nums.length; } // Initialize write pointer at 2. int write = 2; // Iterate with read pointer starting from index 2. for (int read = 2; read < nums.length; read++) { // If the current number is different from the number // located two positions behind in the valid zone, keep it. if (nums[read] != nums[write - 2]) { nums[write] = nums[read]; write++; } } return write; } }
pythonclass Solution: def removeDuplicates(self, nums: List[int]) -> int: # Edge case: small arrays are always valid if len(nums) <= 2: return len(nums) # We can always keep the first two elements write = 2 # Start reading from the third element for read in range(2, len(nums)): # Check against the element two positions back in the *result* array if nums[read] != nums[write - 2]: nums[write] = nums[read] write += 1 return write
Time Complexity:
We traverse the array exactly once with the read pointer. All operations inside the loop (comparison, assignment, increment) are constant time .
Space Complexity:
We modify the array in-place. We only use two integer variables (read and write) for state tracking, regardless of the input size.
The Two Pointers - In-place Array Modification pattern is a fundamental technique for array manipulation questions in interviews.
nums[write - 1].Q: Why does my solution fail with "Output Limit Exceeded" or "Wrong Answer"?
Mistake: Checking nums[read] against nums[read - 2] instead of nums[write - 2].
Explanation: You must compare the current candidate against the constructed valid array, not the original array. The write pointer tracks the valid data. If you compare against read - 2, you are checking against data that might have been skipped or is part of a sequence of invalid duplicates.
Consequence: Correctness failure. You might include more than 2 duplicates.
Q: Why did I get a Time Limit Exceeded (TLE)?
Mistake: Using .pop() or .remove() inside the loop in Python or Java.
Explanation: Removing an element from the middle of an array requires shifting all subsequent elements to the left, which is an operation. Inside a loop, this becomes .
Efficiency fail. The algorithm becomes too slow for large inputs.
Q: Why is my output array shorter than expected?
Mistake: Resetting the count logic incorrectly or using a separate counter variable that doesn't sync with the write pointer.
Explanation: Some candidates try to maintain a count variable for the current number. While possible, it adds complexity (resetting count when number changes). The nums[write-2] check handles this logic implicitly and is less error-prone.
Consequence: Correctness fail.