Remove Duplicates from Sorted Array II

📋

Problem

Imagine you have a sorted list of customer IDs, but due to system glitches, some IDs appear more than twice. You want to clean this list so that each ID appears at most twice, preserving order and doing it efficiently.

Given a sorted integer array nums, remove duplicates in-place such that each element appears at most twice and return the new length. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory. The relative order of the elements should be kept the same.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is sorted in non-decreasing order

Edge cases: Array with all identical elements → length should be 2Array with no duplicates → length equals original lengthArray with exactly two duplicates per element → length equals original length

</>

IDE

def remove_duplicates(nums: list[int]) -> int:public int removeDuplicates(int[] nums)int removeDuplicates(vector<int>& nums)function removeDuplicates(nums)

def remove_duplicates(nums):
    # Write your solution here
    pass

class Solution {
    public int removeDuplicates(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function removeDuplicates(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Length greater than expected due to allowing more than two duplicatesNot checking if nums[i] != nums[j-2] before copying element, allowing unlimited duplicates✅ Add condition: if j < 2 or nums[i] != nums[j-2], then nums[j] = nums[i]; j++

Wrong: Length less than expected due to removing duplicates even when count is twoRemoving duplicates when count equals two instead of only when count > 2✅ Allow duplicates up to two by only removing when count > 2

Wrong: Crashes or incorrect output on empty inputNo check for empty array before accessing elements✅ Add early return if nums is empty: if not nums: return 0

Wrong: TLE on large inputsUsing nested loops or repeated shifting causing O(n^2) complexity✅ Use two-pointer O(n) approach without shifting elements repeatedly

Wrong: Incorrect length due to off-by-one errors in pointer incrementsIncrementing write pointer incorrectly or copying wrong elements✅ Ensure write pointer increments only when element is copied; carefully check conditions

✓

Test Cases

Try testing your code on empty and minimal arrays to catch base case bugs.

Consider tricky inputs with many duplicates or mixed signs to expose logic errors.

Optimize your approach to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,1,1,2,2,3]}

Expected5

⏱ Performance - must finish in 2000ms

After removing extra duplicates, the array becomes [1,1,2,2,3]. The length is 5.

💡 Use two pointers to track the position to write and count duplicates.

💡 Allow each element to appear at most twice by checking previous two elements.

💡 If nums[i] != nums[j-2], copy nums[i] to nums[j] and increment j.

Why it failed: Returned length incorrect due to not limiting duplicates to two; fix by checking nums[i] != nums[j-2] before copying.

✓ Correctly limits duplicates to two and returns proper length.

t1_02basic

Input{"nums":[0,0,1,1,1,1,2,3,3]}

Expected7

⏱ Performance - must finish in 2000ms

After removing extra duplicates, array becomes [0,0,1,1,2,3,3]. Length is 7.

💡 Track count of duplicates while iterating with two pointers.

💡 Only copy element if it doesn't exceed two occurrences.

💡 Check if nums[i] != nums[j-2] before copying to position j.

Why it failed: Fails to handle multiple duplicates correctly; duplicates exceed two. Fix by enforcing max two duplicates via comparison with nums[j-2].

✓ Duplicates limited to two and array length updated correctly.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array input returns length 0.

💡 Check for empty input before processing.

💡 Return 0 immediately if nums is empty.

💡 No elements means length is zero.

Why it failed: Code crashes or returns non-zero for empty input; fix by adding early return for empty array.

✓ Handles empty input gracefully with length 0.

t2_02edge

Input{"nums":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array returns length 1 unchanged.

💡 Single element arrays should return length 1.

💡 No duplicates possible with one element.

💡 Ensure code handles small arrays without errors.

Why it failed: Fails on single element input by removing or miscounting; fix by handling arrays with length < 3 properly.

✓ Correctly returns length 1 for single element array.

t2_03edge

Input{"nums":[2,2]}

Expected2

⏱ Performance - must finish in 2000ms

Array with exactly two duplicates per element returns original length 2.

💡 Allow up to two duplicates without removal.

💡 Check that duplicates count does not exceed two.

💡 Do not remove elements if count <= 2.

Why it failed: Incorrectly removes duplicates when count is exactly two; fix by allowing duplicates up to count 2.

✓ Correctly retains two duplicates and returns length 2.

t3_01corner

Input{"nums":[1,1,1,1,1,1]}

Expected2

⏱ Performance - must finish in 2000ms

All identical elements reduced to two occurrences, length 2.

💡 Check if code handles large runs of identical elements.

💡 Avoid removing too few or too many duplicates.

💡 Ensure only two duplicates remain by comparing with nums[j-2].

Why it failed: Fails to limit duplicates to two, returns length > 2; fix by enforcing max two duplicates via nums[j-2] check.

✓ Correctly limits all duplicates to two and returns length 2.

t3_02corner

Input{"nums":[-3,-3,-3,-2,-1,-1,0,0,0,0,1,1,2,2,2]}

Expected12

⏱ Performance - must finish in 2000ms

Mixed negative and positive numbers with duplicates limited to two, length 12.

💡 Handle negative numbers correctly as well as positive.

💡 Duplicates count logic should be independent of value sign.

💡 Use two pointers and compare with nums[j-2] to limit duplicates.

Why it failed: Fails on negative numbers or mixed signs, duplicates not limited; fix by applying same logic regardless of sign.

✓ Correctly handles negative and positive duplicates limiting to two.

t3_03corner

Input{"nums":[1,1,2,2,3,3,3,4,4,4,4,5,5]}

Expected11

⏱ Performance - must finish in 2000ms

Multiple elements with some having more than two duplicates, length 11 after removal.

💡 Watch for off-by-one errors when copying elements.

💡 Ensure duplicates beyond two are removed properly.

💡 Check that j pointer increments only when element allowed.

Why it failed: Off-by-one error causes incorrect length or array content; fix by careful pointer increment and condition check.

✓ Correctly removes extra duplicates and returns correct length.

t4_01performance

Input{"nums":[-10000,-10000,-10000,-9999,-9999,-9999,-9998,-9998,-9998,-9997,-9997,-9997,-9996,-9996,-9996,-9995,-9995,-9995,-9994,-9994,-9994,-9993,-9993,-9993,-9992,-9992,-9992,-9991,-9991,-9991,-9990,-9990,-9990,-9989,-9989,-9989,-9988,-9988,-9988,-9987,-9987,-9987,-9986,-9986,-9986,-9985,-9985,-9985,-9984,-9984,-9984,-9983,-9983,-9983,-9982,-9982,-9982,-9981,-9981,-9981,-9980,-9980,-9980,-9979,-9979,-9979,-9978,-9978,-9978,-9977,-9977,-9977,-9976,-9976,-9976,-9975,-9975,-9975,-9974,-9974,-9974,-9973,-9973,-9973,-9972,-9972,-9972,-9971,-9971,-9971,-9970,-9970,-9970,-9969,-9969,-9969,-9968,-9968,-9968,-9967,-9967,-9967,-9966,-9966,-9966,-9965,-9965,-9965]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100, duplicates in runs of three, must complete in O(n) time within 2 seconds.

💡 Use O(n) two-pointer approach to avoid TLE.

💡 Avoid nested loops or repeated shifting of elements.

💡 Check duplicates by comparing with nums[j-2] to maintain O(n) complexity.

Why it failed: TLE due to O(n^2) approach with nested loops or shifting; fix by using two-pointer O(n) method.

✓ Efficient O(n) solution passes performance test.

Practice

1. Given a sorted array of integers (which may include negatives), you need to return a new array containing the squares of each number, also sorted. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Traverse the array once, square elements in place, and rely on the input being sorted to keep the order.

B. Square each element and then sort the resulting array using a standard sorting algorithm.

C. Use a dynamic programming approach to build the squared array based on previous computations.

D. Use two pointers starting at both ends of the array, compare absolute values, and fill the output array from the end.

Solution

1. Step 1: Understand the problem constraints

   The input array is sorted but contains negative numbers, so squaring can disrupt order.

2. Step 2: Identify the approach that leverages sorted input

   Two pointers from both ends compare absolute values and fill the output array from the end, ensuring sorted squares in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two-pointer approach uses input order optimally [OK]

Hint: Two pointers from ends handle negatives optimally [OK]

Common Mistakes:

• Assuming squaring preserves order
• Using sorting after squaring without leveraging input order
• Confusing DP with this problem

2. Consider the following buggy code for merging two sorted arrays in-place. Which line contains the subtle bug that causes missing elements in the final merged array?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Missing copying remaining nums2 elements

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

medium

A. Line 12: Missing while loop to copy remaining nums2 elements

B. Line 9: nums1[k] = nums2[j]

C. Line 4: i = m - 1

D. Line 7: if nums1[i] > nums2[j]:

Solution

1. Step 1: Analyze the main merging loop

   The main loop merges elements from the back correctly but stops when either i or j is negative.

2. Step 2: Identify missing step

   There is no loop copying remaining elements from nums2 if any remain, causing missing elements in nums1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without copying leftover nums2 elements, final array is incomplete [OK]

Hint: Always copy leftover nums2 elements after main loop [OK]

Common Mistakes:

• Forgetting leftover nums2 copy
• Overwriting nums1 elements too early

3. Suppose the problem changes so that elements can be reused multiple times in triplets (i.e., indices can repeat). Which modification to the two-pointer approach correctly counts the number of triplets with sum less than target?

hard

A. Keep the same two-pointer approach but allow left and right pointers to be equal and count accordingly.

B. Use three nested loops to consider all triplets with possible repeated indices.

C. Sort the array and for each i, use two pointers starting at i to allow reuse, adjusting counting logic accordingly.

D. Sort the array and for each i, use a single pointer to count pairs with sum less than target minus nums[i], allowing reuse.

Solution

1. Step 1: Understand reuse of elements

   Allowing repeated indices means pairs can include the same element multiple times, so two-pointer approach must adapt.

2. Step 2: Adjust approach for reuse

   Using a single pointer to count pairs with sum less than target - nums[i] allows counting with reuse, since two pointers crossing is no longer valid.

3. Step 3: Why other options fail

   Allowing left == right breaks two-pointer logic (A). Three nested loops (B) is correct but inefficient. Starting two pointers at i (C) is incorrect because it counts invalid pairs.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Single pointer counting with reuse is correct and efficient [OK]

Hint: Reuse requires counting pairs with single pointer or adjusted logic [OK]

Common Mistakes:

• Allowing pointers to cross causing invalid counts
• Using naive triple loops ignoring efficiency
• Starting two pointers incorrectly leading to missed counts

4. Suppose the 3Sum problem is modified so that elements can be reused multiple times in a triplet (e.g., triplet [0,0,0] is valid if zeros exist). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Remove the duplicate skipping for fixed element i and inner pointer j, allowing repeated elements.

B. Use three nested loops to allow repeated indices and check sums directly.

C. Keep the same code but remove the sorting step to allow duplicates naturally.

D. Modify the hash set approach to not skip duplicates and allow complement to be equal to nums[j].

Solution

1. Step 1: Understand reuse means duplicates allowed in triplets

   Allowing reuse means complement can be equal to nums[j], so skipping duplicates must be adjusted.

2. Step 2: Modify hash set approach accordingly

   Do not skip duplicates; allow complement == nums[j]; sorting still needed to avoid unordered duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Allowing complement == nums[j] and no skipping duplicates handles reuse correctly [OK]

Hint: Allow complement == nums[j] and no skipping duplicates for reuse [OK]

Common Mistakes:

• Removing sorting breaks uniqueness
• Using triple loops is inefficient
• Removing duplicate skipping blindly causes duplicates

5. Suppose you want to reverse a string but the input is a very large immutable string (e.g., Python str) instead of a mutable list. Which approach correctly handles this constraint efficiently?

hard

A. Convert the string to a list, reverse it using two pointers, then join back to a string.

B. Use a brute force approach creating a new reversed string by concatenation in a loop.

C. Use the recursive two-pointer approach on the string directly, swapping characters in-place.

D. Use a dynamic programming approach to build the reversed string from substrings.

Solution

1. Step 1: Understand immutability constraint

   Strings are immutable in Python, so in-place swaps are impossible directly on the string.

2. Step 2: Choose efficient workaround

   Converting to a list allows in-place two-pointer swaps, then joining back creates the reversed string efficiently in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Convert the string to a list, reverse it using two pointers, then join back to a string. respects immutability and is efficient [OK]

Hint: Immutable strings require conversion to mutable type for in-place reversal [OK]

Common Mistakes:

• Trying to swap characters in immutable string
• Using inefficient string concatenation in loop
• Misapplying DP to string reversal