Remove Duplicates from Sorted Array II

▶

Steps

setup

Initialize write_index to 0

We start by setting write_index to 0, indicating the position where the next valid element will be written.

💡 Initializing write_index is crucial because it tracks the length of the processed array and where to place allowed elements.

Line:

write_index = 0

💡 write_index starts at 0, meaning no elements have been written yet.

traverse

Start iterating read_index at 0

Begin the for loop with read_index at 0 to examine the first element of the array.

💡 read_index scans each element to decide if it should be kept or skipped.

Line:

for read_index in range(len(nums)):

💡 read_index starts scanning from the first element.

compare

Check if write_index < 2 or nums[read_index] != nums[write_index - 2]

Since write_index is 0, which is less than 2, the condition is true, so we copy nums[read_index] to nums[write_index].

💡 This condition allows the first two elements to be copied without comparison to avoid index errors and allow up to two duplicates.

Line:

if write_index < 2 or nums[read_index] != nums[write_index - 2]:

💡 The first two elements are always kept to allow up to two duplicates.

insert

Copy nums[read_index] to nums[write_index] and increment write_index

Copy the element at read_index 0 (value 1) to write_index 0, then increment write_index to 1.

💡 Copying the element ensures the first element is kept; incrementing write_index moves the boundary forward.

Line:

nums[write_index] = nums[read_index]
write_index += 1

💡 write_index now points to the next position to write a valid element.

compare

Move read_index to 1 and check condition

read_index moves to 1. Since write_index is 1 (still less than 2), the condition is true and we will copy the element.

💡 The first two elements are always copied to allow up to two duplicates.

Line:

if write_index < 2 or nums[read_index] != nums[write_index - 2]:

💡 The algorithm allows the first two elements without comparison.

insert

Copy nums[read_index] to nums[write_index] and increment write_index

Copy element at read_index 1 (value 1) to write_index 1, then increment write_index to 2.

💡 This copies the second '1', allowing two duplicates.

Line:

nums[write_index] = nums[read_index]
write_index += 1

💡 write_index now points to the next position after two allowed duplicates.

compare

Move read_index to 2 and check condition

read_index moves to 2. Now write_index is 2, so we check if nums[2] != nums[0] (nums[write_index - 2]).

💡 This condition prevents more than two duplicates by comparing current with the element two positions behind.

Line:

if write_index < 2 or nums[read_index] != nums[write_index - 2]:

💡 The third '1' is a duplicate beyond allowed two, so it will be skipped.

traverse

Skip copying the third '1' and move read_index forward

Since the condition was false, we do not copy the element at read_index 2 and just move read_index forward.

💡 Skipping prevents more than two duplicates from being written.

Line:

for read_index in range(len(nums)):
    if write_index < 2 or nums[read_index] != nums[write_index - 2]:
        nums[write_index] = nums[read_index]
        write_index += 1

💡 The algorithm efficiently skips unwanted duplicates without extra space.

compare

Check condition for read_index 3 (value 2)

Check if nums[3] != nums[write_index - 2] which is nums[1]. Since nums[3] = 2 and nums[1] = 1, condition is true.

💡 Different value means we can copy this element to write_index.

Line:

if write_index < 2 or nums[read_index] != nums[write_index - 2]:

💡 New number detected, so it is allowed to be copied.

insert

Copy nums[read_index] to nums[write_index] and increment write_index

Copy element 2 at read_index 3 to write_index 2, then increment write_index to 3.

💡 This writes the first '2' after the allowed duplicates of '1'.

Line:

nums[write_index] = nums[read_index]
write_index += 1

💡 write_index moves forward to include the new element.

compare

Move read_index to 4 and check condition

Check if nums[4] != nums[write_index - 2] which is nums[1]. nums[4] = 2 and nums[1] = 1, so condition is true.

💡 Second '2' is allowed as it is different from the element two positions behind.

Line:

if write_index < 2 or nums[read_index] != nums[write_index - 2]:

💡 Allows up to two duplicates of '2'.

insert

Copy nums[read_index] to nums[write_index] and increment write_index

Copy element 2 at read_index 4 to write_index 3, then increment write_index to 4.

💡 This writes the second '2' allowed in the array.

Line:

nums[write_index] = nums[read_index]
write_index += 1

💡 write_index now includes two '2's after the two '1's.

compare

Move read_index to 5 and check condition

Check if nums[5] != nums[write_index - 2] which is nums[2]. nums[5] = 3 and nums[2] = 2, so condition is true.

💡 New number '3' is different from the element two positions behind, so it can be copied.

Line:

if write_index < 2 or nums[read_index] != nums[write_index - 2]:

💡 New distinct number is allowed to be copied.

insert

Copy nums[read_index] to nums[write_index] and increment write_index

Copy element 3 at read_index 5 to write_index 4, then increment write_index to 5.

💡 This writes the '3' to the array, completing the allowed elements.

Line:

nums[write_index] = nums[read_index]
write_index += 1

💡 write_index now marks the length of the array with duplicates removed.

reconstruct

End of iteration, return write_index as new length

The loop ends and the function returns write_index, which is 5, the length of the array with duplicates removed.

💡 Returning write_index gives the new length of the processed array.

Line:

return write_index

💡 The final length is 5, meaning the first 5 elements are valid.

def remove_duplicates(nums):
    write_index = 0  # STEP 1: Initialize write_index
    for read_index in range(len(nums)):  # STEP 2: Iterate read_index
        if write_index < 2 or nums[read_index] != nums[write_index - 2]:  # STEP 3 & 7 & 9 & 11 & 13: Condition check
            nums[write_index] = nums[read_index]  # STEP 4 & 6 & 10 & 12 & 14: Copy element
            write_index += 1  # STEP 4 & 6 & 10 & 12 & 14: Increment write_index
    return write_index  # STEP 15: Return new length

if __name__ == '__main__':
    arr = [1,1,1,2,2,3]
    length = remove_duplicates(arr)
    print(length)  # Expected: 5
    print(arr[:length])  # Expected: [1,1,2,2,3]

📊

Remove Duplicates from Sorted Array II - Watch the Algorithm Execute, Step by Step

Watching each pointer move and decision helps you understand how the algorithm efficiently overwrites duplicates in-place without extra space.

setup

write_index

1

0

1

1

1

2

2

3

2

4

3

5

Result: 0

traverse

read_index

1

0

1

1

1

2

2

3

2

4

3

5

Result: 0

compare

read_index

1

0

1

1

1

2

2

3

2

4

3

5

Result: 0

insert

read_index

1

0

write_index

1

1

1

2

2

3

2

4

3

5

Result: 1

compare

1

0

read_index

1

1

1

2

2

3

2

4

3

5

Result: 1

insert

1

0

read_index

1

1

write_index

1

2

2

3

2

4

3

5

Result: 2

compare

1

0

1

1

read_index

1

2

2

3

2

4

3

5

Result: 2

move_right

1

0

1

1

write_index

1

2

read_index

2

3

2

4

3

5

Result: 2

compare

1

0

1

1

write_index

1

2

read_index

2

3

2

4

3

5

Result: 2

insert

1

0

1

1

2

2

read_index

2

3

2

4

3

5

Result: 3

compare

1

0

1

1

2

2

write_index

2

3

read_index

2

4

3

5

Result: 3

insert

1

0

1

1

2

2

2

3

read_index

2

4

3

5

Result: 4

compare

1

0

1

1

2

2

2

3

write_index

2

4

read_index

3

5

Result: 4

insert

1

0

1

1

2

2

2

3

3

4

read_index

3

5

Result: 5

reconstruct

1

0

1

1

2

2

2

3

3

4

write_index

3

5

Result: 5

Key Takeaways

✓ The algorithm uses two pointers moving in the same direction to overwrite duplicates in-place.

This insight is hard to see from code alone because the pointer roles and their interaction are subtle without visualization.

✓ The condition comparing the current element with the element two positions behind ensures at most two duplicates are kept.

This condition is the core logic that prevents extra duplicates, which is clearer when watching each comparison.

✓ write_index only increments when a valid element is copied, effectively tracking the new length of the array.

Understanding how write_index marks the boundary of the processed array is easier when you see it move step-by-step.

Practice

1. You are given a string and need to determine if it reads the same forwards and backwards, ignoring case and non-alphanumeric characters. Which approach guarantees an optimal O(n) time and O(n) space solution for this problem?

easy

A. Reverse the original string and compare it directly to the input string without any preprocessing.

B. Use dynamic programming to check all substrings for palindrome properties.

C. Use a greedy approach to skip characters that don't match and try to fix mismatches on the fly.

D. Preprocess the string by removing non-alphanumeric characters and converting to lowercase, then use two pointers from opposite ends to compare characters.

Solution

1. Step 1: Understand problem constraints

   The problem requires ignoring case and non-alphanumeric characters, so direct comparison or naive reversal won't work correctly.

2. Step 2: Identify approach that handles preprocessing and efficient comparison

   Preprocessing to clean the string and then using two pointers from opposite ends ensures O(n) time and space, and correctly handles all cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Preprocessing + two pointers is standard for palindrome checks ignoring punctuation [OK]

Hint: Preprocess then two pointers is optimal palindrome check [OK]

Common Mistakes:

• Trying to compare original string directly without cleaning
• Using DP which is overkill and slower
• Greedy skipping mismatches leads to incorrect results

2. What is the time complexity of the optimal 3Sum solution that sorts the array and uses a hash set for the two-sum complement search for each fixed element?

medium

A. O(n^3) because of nested loops and hash set operations

B. O(n^2) because for each element, we scan the rest with a hash set lookup in O(1)

C. O(n log n) due to sorting and linear two-pointer scans

D. O(n^2 log n) because sorting and hash set insertions dominate

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n), which is dominated by later steps.

2. Step 2: Analyze nested loops and hash set usage

   Outer loop runs n times; inner loop runs up to n times; hash set operations inside inner loop are O(1) each, but overall complexity is O(n^2).

3. Step 3: Clarify complexity of hash set approach

   The hash set approach inside the inner loop leads to O(n^2) complexity, not O(n^3).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Hash set lookups are O(1), so total is O(n^2) [OK]

Hint: Sorting O(n log n) < O(n²) nested loops dominate [OK]

Common Mistakes:

• Confusing hash set insertions as O(n)
• Thinking sorting dominates
• Assuming triple nested loops remain

3. What is the time complexity of the optimal 4Sum solution that uses a hash map to store all pairs of sums and then finds complementary pairs to form quadruplets?

medium

A. O(n^2 + k^2), where k is the average number of pairs per sum stored in the hash map.

B. O(n^4) because all quadruplets are checked explicitly.

C. O(n^3) due to nested loops over pairs and quadruplets.

D. O(n^2 log n) because sorting dominates the complexity.

Solution

1. Step 1: Analyze pair sum generation

   Generating all pairs sums takes O(n^2) time and space.

2. Step 2: Analyze combining pairs to quadruplets

   For each sum, combining pairs from two lists takes O(k^2) where k is average pairs per sum.

3. Step 3: Consider worst case

   In worst case, k can be O(n), so combining pairs can be O(n^2) per sum, leading to O(n^4) overall.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Worst-case complexity is O(n^4), not O(n^2 + k^2) [OK]

Hint: Worst-case complexity can be O(n^4) due to pair combinations [OK]

Common Mistakes:

• Assuming average case complexity applies to worst case
• Ignoring worst-case pair combination cost

4. What is the time complexity of the optimal two-pointer approach for removing duplicates from a sorted array of length n?

medium

A. O(n) because each element is visited at most twice

B. O(n log n) due to sorting overhead

C. O(n²) due to nested comparisons

D. O(1) since it modifies the array in-place

Solution

1. Step 1: Identify 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 sorting

   No nested loops or sorting steps; each element is compared once or twice, so total time is linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear scan with two pointers yields O(n) time [OK]

Hint: Single pass over array means O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Thinking in-place means O(1) time

5. Examine the following buggy code for removing duplicates from a sorted array:

def remove_duplicates(nums):
    if len(nums) == 0:
        return 0
    uniqueIndex = 0
    for currentIndex in range(1, len(nums)):
        if nums[currentIndex] != nums[uniqueIndex]:
            uniqueIndex += 1
            nums[currentIndex] = nums[uniqueIndex]
    return uniqueIndex + 1

Which line contains the bug that causes incorrect behavior?

medium

A. Line 2: if len(nums) == 0: return 0

B. Line 8: nums[currentIndex] = nums[uniqueIndex]

C. Line 6: if nums[currentIndex] != nums[uniqueIndex]:

D. Line 7: uniqueIndex += 1

Solution

1. Step 1: Identify assignment direction

   The correct code assigns nums[uniqueIndex] = nums[currentIndex] to overwrite duplicates; here it is reversed.

2. Step 2: Understand impact

   Assigning nums[currentIndex] = nums[uniqueIndex] overwrites scanning pointer's value incorrectly, breaking the unique sequence.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Assignment direction error causes wrong array modification [OK]

Hint: Assignment must overwrite uniqueIndex position, not currentIndex [OK]

Common Mistakes:

• Swapping assignment indices
• Forgetting to increment uniqueIndex