Remove Duplicates from Sorted Array

📋

Problem

Imagine you have a sorted list of customer IDs and want to keep only unique IDs to avoid duplicate processing.

Given a sorted integer array nums, remove the duplicates in-place such that each element appears only once and returns 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.

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

Edge cases: Array with all unique elements → length remains sameArray with all identical elements → length is 1Array with two elements both duplicates → length is 1

</>

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 equal to original array length even with duplicatesNot removing duplicates or failing to overwrite duplicates in place.✅ Use two pointers: one for iterating and one for placing unique elements; update length accordingly.

Wrong: Length off by one, missing last unique elementOff-by-one error in loop or pointer increments.✅ Ensure loop runs through entire array and unique pointer increments only on new unique elements.

Wrong: Fails on empty array with index error or wrong lengthNo check for empty input before accessing elements.✅ Add a condition to return 0 if array length is zero before processing.

Wrong: Time limit exceeded on large inputUsing nested loops causing O(n^2) complexity.✅ Implement two-pointer approach with O(n) time complexity.

Wrong: Incorrect length for all identical elements (returns >1)Not properly skipping duplicates or incrementing unique pointer incorrectly.✅ Only increment unique pointer when a new unique element is found.

✓

Test Cases

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

Consider tricky inputs with multiple duplicates and all identical elements to find edge bugs.

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

t1_01basic

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

Expected2

⏱ Performance - must finish in 2000ms

After removing duplicates, the first two elements are [1,2]. The function returns length 2.

💡 Use two pointers to track unique elements and overwrite duplicates.

💡 Check if current element differs from last unique element before copying.

💡 Increment unique pointer only when a new unique element is found.

Why it failed: Returned length incorrect due to not properly skipping duplicates. Fix by advancing the unique pointer only when a new unique element is found.

✓ Correctly identifies unique elements and returns correct length.

t1_02basic

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

Expected5

⏱ Performance - must finish in 2000ms

After removing duplicates, the first five elements are [0,1,2,3,4]. The function returns length 5.

💡 Iterate through array comparing current and previous elements.

💡 Use a slow pointer to mark position of last unique element.

💡 Copy new unique elements to slow pointer + 1 position.

Why it failed: Incorrect length due to failing to overwrite duplicates in place. Fix by using two pointers to overwrite duplicates.

✓ Duplicates removed correctly with in-place overwrite and correct length returned.

t2_01edge

Input{"nums":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has length 0 after removing duplicates.

💡 Check for empty input before processing.

💡 Return 0 immediately if array length is zero.

💡 Handle base case to avoid index errors.

Why it failed: Fails on empty input by accessing elements or returning wrong length. Fix by adding a check for empty array at start.

✓ Handles empty array correctly by returning 0.

t2_02edge

Input{"nums":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array length remains 1 after removing duplicates.

💡 Single element arrays are already unique.

💡 Return length 1 without modification.

💡 Ensure algorithm handles single element without errors.

Why it failed: Fails single element case by returning 0 or modifying array incorrectly. Fix by returning length 1 if array length is 1.

✓ Correctly returns length 1 for single element array.

t2_03edge

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

Expected1

⏱ Performance - must finish in 2000ms

Two elements both duplicates reduce to length 1.

💡 Check adjacent elements for duplicates.

💡 Overwrite duplicates by moving unique pointer.

💡 Return length reflecting unique count.

Why it failed: Fails to reduce duplicates properly for two identical elements. Fix by comparing adjacent elements and updating unique pointer correctly.

✓ Correctly reduces duplicates to length 1.

t3_01corner

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

Expected6

⏱ Performance - must finish in 2000ms

Duplicates removed correctly, unique elements are [1,2,3,4,5,6].

💡 Beware of off-by-one errors when updating pointers.

💡 Ensure slow pointer increments only on new unique elements.

💡 Check loop boundaries carefully to avoid skipping last element.

Why it failed: Off-by-one error causes missing last unique element or incorrect length. Fix by carefully managing loop indices and pointer increments.

✓ Handles multiple duplicates and returns correct unique count.

t3_02corner

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

Expected1

⏱ Performance - must finish in 2000ms

All elements identical, length reduces to 1.

💡 Check that algorithm does not count duplicates multiple times.

💡 Use a single pointer to track unique elements.

💡 Return 1 when all elements are the same.

Why it failed: Fails by counting duplicates multiple times or returning length > 1. Fix by updating unique pointer only when new unique element found.

✓ Correctly returns length 1 for all identical elements.

t3_03corner

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

Expected5

⏱ Performance - must finish in 2000ms

All unique elements, length remains 5.

💡 Verify algorithm does not remove unique elements mistakenly.

💡 Check that unique pointer advances correctly for all elements.

💡 Return original length if no duplicates found.

Why it failed: Incorrectly removes unique elements or returns smaller length. Fix by only removing duplicates when adjacent elements are equal.

✓ Correctly returns original length for all unique elements.

t4_01performance

Input{"nums":[-10000,-9999,-9999,-9998,-9997,-9997,-9997,-9996,-9995,-9995,-9994,-9993,-9993,-9992,-9991,-9991,-9990,-9989,-9989,-9988,-9987,-9987,-9986,-9985,-9985,-9984,-9983,-9983,-9982,-9981,-9981,-9980,-9979,-9979,-9978,-9977,-9977,-9976,-9975,-9975,-9974,-9973,-9973,-9972,-9971,-9971,-9970,-9969,-9969,-9968,-9967,-9967,-9966,-9965,-9965,-9964,-9963,-9963,-9962,-9961,-9961,-9960,-9959,-9959,-9958,-9957,-9957,-9956,-9955,-9955,-9954,-9953,-9953,-9952,-9951,-9951,-9950,-9949,-9949,-9948,-9947,-9947,-9946,-9945,-9945,-9944,-9943,-9943,-9942,-9941,-9941,-9940,-9939,-9939,-9938,-9937,-9937,-9936,-9935,-9935]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 elements, O(n) solution must complete within 2 seconds.

💡 Use two pointers to achieve O(n) time complexity.

💡 Avoid nested loops that cause O(n^2) time.

💡 In-place modification with constant extra space is required.

Why it failed: TLE due to nested loops causing O(n^2) complexity. Fix by implementing two-pointer linear scan.

✓ Algorithm runs in O(n) time and completes within time limit.

Practice

1. Consider the following Python function implementing the optimal approach for counting triplets with sum smaller than target. What is the returned value when calling threeSumSmaller([-2, 0, 1, 3], 2)?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Sort input and initialize variables

   Sorted array is [-2, 0, 1, 3], count=0, n=4.

2. Step 2: Iterate and count triplets

   For i=0 (-2), check if sum of first three elements >= 2? -2+0+1= -1 < 2, continue. Use two pointers left=1, right=3. - curr_sum = -2 + 0 + 3 = 1 < 2 -> count += 3-1=2, left=2 - curr_sum = -2 + 1 + 3 = 2 not < 2 -> right=2 Now left=2, right=2 ends loop. For i=1 (0), sum of nums[1]+nums[2]+nums[3] = 0+1+3=4 >= 2 -> break loop. Total count=2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches expected output from example [OK]

Hint: Count increments by right-left when sum < target [OK]

Common Mistakes:

• Off-by-one in counting pairs
• Not breaking early when minimal sum >= target
• Misusing pointers leading to wrong counts

2. Consider the following Python code that counts pairs with absolute difference at most K using binary search. What is the final output when the input is nums = [1, 2, 5] and K = 3?

import bisect

def count_pairs_binary_search(nums, K):
    count = 0
    n = len(nums)
    for i in range(n - 1):
        target = nums[i] + K
        j = bisect.bisect_right(nums, target, i + 1) - 1
        if j > i:
            count += j - i
    return count

print(count_pairs_binary_search([1, 2, 5], 3))

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Trace iteration i=0

   nums[0] = 1, target = 1 + 3 = 4. bisect_right(nums, 4, 1) returns index 2 (nums[2]=5 >4), so j = 2 - 1 = 1. Count += 1 - 0 = 1.

2. Step 2: Trace iteration i=1

   nums[1] = 2, target = 2 + 3 = 5. bisect_right(nums, 5, 2) returns 3 (end of list), so j = 3 - 1 = 2. Count += 2 - 1 = 1. Total count = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pairs are (1,2) and (2,5) with differences 1 and 3 respectively [OK]

Hint: Check bisect_right returns and subtract 1 carefully [OK]

Common Mistakes:

• Off-by-one error in bisect index adjustment
• Counting pairs where i >= j
• Miscomputing target as nums[i] - K

3. What is the time complexity of the optimal two-pointer approach that removes duplicates allowing at most two occurrences in a sorted array of length n?

medium

A. O(n) because each element is processed once with constant time checks

B. O(n²) because of shifting elements when duplicates are removed

C. O(n log n) due to sorting

D. O(1) since it modifies in-place without extra loops

Solution

1. Step 1: Identify the loops and operations

   The algorithm uses a single for loop iterating over n elements once, with constant time operations inside.

2. Step 2: Confirm no nested loops or costly operations

   No nested loops or shifting; elements are overwritten in-place, so no O(n²) behavior.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant time per element -> O(n) [OK]

Hint: Single pass with constant checks -> O(n) [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring in-place overwrite cost

4. Consider the following buggy code for trapping rain water using two pointers. Which line contains the subtle bug causing incorrect trapped water calculation?

medium

A. Line updating right_max with 'if height[right] >= right_max:'

B. Line updating left_max with 'if height[left] > left_max:'

C. Line adding water with 'water += left_max - height[left]'

D. Line incrementing left pointer with 'left += 1'

Solution

1. Step 1: Compare left_max update condition

   The original correct code uses '>=' to update left_max, but here it uses '>' which skips updating when equal.

2. Step 2: Understand impact

   Not updating left_max when height[left] equals left_max causes undercounting trapped water in some cases.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Changing '>' to '>=' fixes subtle undercount bug [OK]

Hint: Check boundary conditions in max updates carefully [OK]

Common Mistakes:

• Using '>' instead of '>=' for max updates
• Incorrect pointer increments
• Misplaced water addition lines

5. Suppose the problem changes: you want to count pairs with absolute difference at most K, but now the array can contain duplicate elements and you want to count pairs where elements can be reused multiple times (i.e., pairs (i, j) with i ≤ j). Which modification to the binary search approach correctly handles this variant?

hard

A. Start binary search from i instead of i + 1 and count pairs where j ≥ i, adjusting count accordingly.

B. Use brute force nested loops to count all pairs with i ≤ j and difference ≤ K, as binary search cannot handle reuse.

C. Use two pointers with left starting at 0 and right starting at 0, moving right pointer forward and counting pairs including i = j.

D. Keep the same code but change bisect_right to bisect_left to include duplicates and allow i ≤ j pairs.

Solution

1. Step 1: Understand reuse and duplicates impact

   Allowing i ≤ j means pairs with the same element twice are valid; binary search must include current index.

2. Step 2: Modify binary search start index

   Starting bisect_right from i (not i+1) includes pairs where i == j; counting j ≥ i pairs correctly.

3. Step 3: Adjust counting logic

   Count pairs as j - i + 1 if including i == j, or carefully count pairs with j ≥ i.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Starting search at i and counting pairs with j ≥ i handles reuse correctly [OK]

Hint: Start binary search at i to include pairs with i == j [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right incorrectly
• Ignoring pairs where i == j
• Assuming two pointers cannot handle reuse