Remove Duplicates from Sorted Array Two Pointer in DSA Go

Mental Model

Use two pointers to overwrite duplicates in a sorted array, keeping only unique elements at the front.

Analogy: Imagine sorting your books on a shelf and removing extra copies by sliding unique books forward to fill gaps.

[1, 1, 2, 3, 3, 4, 5]
 ↑   ↑
left right

Dry Run Walkthrough

Input: array: [1, 1, 2, 3, 3, 4, 5]

Goal: Remove duplicates so the array starts with unique elements only

Step 1: Initialize left=0, right=1 to start comparing

[1, 1, 2, 3, 3, 4, 5]
 ↑   ↑
left right

Why: We need two pointers to compare adjacent elements

Step 2: Compare array[left]=1 and array[right]=1, they are equal, move right forward

[1, 1, 2, 3, 3, 4, 5]
 ↑       ↑
left     right

Why: Skip duplicate by moving right pointer

Step 3: Compare array[left]=1 and array[right]=2, different values found

[1, 1, 2, 3, 3, 4, 5]
 ↑       ↑
left     right

Why: Found a new unique element

Step 4: Increment left to 1 and copy array[right]=2 to array[left]

[1, 2, 2, 3, 3, 4, 5]
    ↑    ↑
   left  right

Why: Overwrite duplicate position with new unique element

Step 5: Move right to 3, compare array[left]=2 and array[right]=3, different

[1, 2, 2, 3, 3, 4, 5]
    ↑       ↑
   left     right

Why: Next unique element found

Step 6: Increment left to 2 and copy array[right]=3 to array[left]

[1, 2, 3, 3, 3, 4, 5]
       ↑    ↑
      left  right

Why: Place unique element next in line

Step 7: Move right to 4, compare array[left]=3 and array[right]=3, equal, move right forward

[1, 2, 3, 3, 3, 4, 5]
       ↑         ↑
      left       right

Why: Skip duplicate

Step 8: Compare array[left]=3 and array[right]=4, different

[1, 2, 3, 3, 3, 4, 5]
       ↑           ↑
      left         right

Why: New unique element found

Step 9: Increment left to 3 and copy array[right]=4 to array[left]

[1, 2, 3, 4, 3, 4, 5]
          ↑        ↑
         left      right

Why: Overwrite duplicate with unique element

Step 10: Move right to 6, compare array[left]=4 and array[right]=5, different

[1, 2, 3, 4, 3, 4, 5]
          ↑           ↑
         left         right

Why: Next unique element found

Step 11: Increment left to 4 and copy array[right]=5 to array[left]

[1, 2, 3, 4, 5, 4, 5]
             ↑        ↑
            left      right

Why: Place unique element next in line

Step 12: Right pointer reached end, stop

[1, 2, 3, 4, 5, 4, 5]
             ↑
            left

Why: All unique elements moved to front

Result:

[1, 2, 3, 4, 5, 4, 5]
Unique elements count = 5

Annotated Code

DSA Go

package main

import "fmt"

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    left := 0
    for right := 1; right < len(nums); right++ {
        if nums[right] != nums[left] {
            left++
            nums[left] = nums[right]
        }
    }
    return left + 1
}

func main() {
    nums := []int{1, 1, 2, 3, 3, 4, 5}
    length := removeDuplicates(nums)
    fmt.Printf("%v\n", nums[:length])
    fmt.Printf("Unique elements count = %d\n", length)
}

if len(nums) == 0 { return 0 }

handle empty array edge case

left := 0

initialize left pointer at start

for right := 1; right < len(nums); right++ {

iterate right pointer through array

if nums[right] != nums[left] {

check if current right element is unique

left++

move left pointer forward to place unique element

nums[left] = nums[right]

overwrite duplicate with unique element

return left + 1

return count of unique elements

Output

[1 2 3 4 5]

Unique elements count = 5

Complexity Analysis

Time: O(n) because we scan the array once with two pointers

Space: O(1) because we modify the array in place without extra space

vs Alternative: Naive approach uses extra space to store unique elements, increasing space to O(n)

Edge Cases

empty array

returns 0 without error

DSA Go

if len(nums) == 0 { return 0 }

array with all duplicates

returns 1 and array starts with the single unique element

DSA Go

if nums[right] != nums[left] {

array with no duplicates

returns original length and array unchanged

DSA Go

if nums[right] != nums[left] {

When to Use This Pattern

When you see a sorted array and need to remove duplicates in place, use two pointers to overwrite duplicates efficiently.

Common Mistakes

Mistake: Incrementing left pointer even when elements are duplicates
Fix: Only increment left pointer when a new unique element is found

Mistake: Not handling empty array input
Fix: Add a check to return 0 if array length is zero

Summary

Removes duplicates from a sorted array by overwriting duplicates with unique elements using two pointers.

Use when you want to remove duplicates in place without extra space.

The key is to move one pointer to track unique elements and the other to scan through the array.

Practice

1. What is the main purpose of using two pointers in the Remove Duplicates from Sorted Array problem?

easy

A. To efficiently track unique elements and overwrite duplicates in-place

B. To sort the array before removing duplicates

C. To create a new array with unique elements

D. To count the total number of duplicates in the array

Solution

1. Step 1: Understand the two-pointer approach

   One pointer tracks the position to place the next unique element, the other scans the array. This method avoids extra space by overwriting duplicates directly in the original array.

2. Final Answer:

   To efficiently track unique elements and overwrite duplicates in-place -> Option A

3. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers move to overwrite duplicates without extra space [OK]

Common Mistakes:

• Thinking two pointers create a new array
• Assuming sorting is needed inside the method
• Confusing counting duplicates with removing them

2. Which of the following Go code snippets correctly initializes the two pointers for removing duplicates from a sorted array named nums?

easy

A. i, j := 0, 1

B. i, j := 1, 0

C. i, j := 0, 0

D. i, j := 1, 1

Solution

1. Step 1: Identify pointer roles and correct initialization

   Pointer i tracks last unique index starting at 0 (first element), pointer j scans from the next element at 1 to compare adjacent elements.

2. Final Answer:

   i, j := 0, 1 -> Option A

3. Quick Check:

   i=0, j=1 starts correct two-pointer scan [OK]

Hint: Start i at 0 and j at 1 to compare neighbors [OK]

Common Mistakes:

• Swapping i and j initialization
• Starting both pointers at 0
• Starting both pointers at 1

3. What will be the content of the array nums and the returned length after running the two-pointer duplicate removal on nums := []int{1, 1, 2, 3, 3, 4}?

medium

A. nums = [1, 2, 3, 3, 4, 4], length = 3

B. nums = [1, 1, 2, 3, 4, 4], length = 5

C. nums = [1, 2, 3, 4, 4, 4], length = 4

D. nums = [1, 2, 3, 4, 3, 4], length = 4

Solution

1. Step 1: Trace two-pointer process

   Start i=0, j=1; compare nums[j] with nums[i]. When different, increment i and set nums[i]=nums[j]. Unique elements placed at start: 1, 2, 3, 4; length = 4; leftover elements remain unchanged. Final array: [1, 2, 3, 4, 3, 4].

2. Final Answer:

   nums = [1, 2, 3, 4, 3, 4], length = 4 -> Option D

3. Quick Check:

   Unique elements count = 4, array start updated [OK]

Hint: Overwrite duplicates, keep unique at front, count unique [OK]

Common Mistakes:

• Assuming leftover elements are removed
• Counting duplicates as unique
• Misplacing unique elements

4. Identify the error in the following Go code snippet for removing duplicates from a sorted array nums:

func removeDuplicates(nums []int) int {
    i := 0
    for j := 1; j < len(nums); j++ {
        if nums[j] != nums[i] {
            i = j
            nums[i] = nums[j]
        }
    }
    return i + 1
}

medium

A. Loop should start from j = 0 instead of 1

B. Pointer i is incorrectly updated to j instead of incrementing

C. Return statement should be i instead of i + 1

D. Comparison should be nums[j] == nums[i] instead of !=

Solution

1. Step 1: Analyze pointer update logic

   Pointer i should move forward by one (i++) to place unique element, not jump to j (i = j). Correct code uses i++ then nums[i] = nums[j] to overwrite duplicates properly.

2. Final Answer:

   Pointer i is incorrectly updated to j instead of incrementing -> Option B

3. Quick Check:

   i must increment, not jump to j [OK]

Hint: Increment i to place unique, don't assign i = j [OK]

Common Mistakes:

• Setting i = j causes skipping elements
• Starting loop at wrong index
• Wrong return value calculation

5. Given a sorted array nums := []int{0,0,1,1,1,2,2,3,3,4}, what will be the final array state and length after applying the two-pointer duplicate removal method?

hard

A. nums = [0,1,1,2,3,4,4,3,3,4], length = 5

B. nums = [0,0,1,2,3,4,3,3,4,4], length = 6

C. nums = [0,1,2,3,4,2,2,3,3,4], length = 5

D. nums = [0,1,2,3,4,0,1,1,2,2], length = 4

Solution

1. Step 1: Apply two-pointer logic step-by-step

   Start with i=0, j=1; move j forward, when nums[j] != nums[i], increment i and set nums[i]=nums[j]. Unique elements are 0,1,2,3,4 placed at start; length = 5; rest of array remains unchanged: [0,1,2,3,4,2,2,3,3,4].

2. Final Answer:

   nums = [0,1,2,3,4,2,2,3,3,4], length = 5 -> Option C

3. Quick Check:

   Unique count 5, array start updated correctly [OK]

Hint: Place unique elements at front, count unique length [OK]

Common Mistakes:

• Assuming leftover elements are removed
• Miscounting unique elements
• Overwriting wrong indices