Remove Duplicates from Sorted Array Two Pointer in DSA Go - Deep Dive

Overview - Remove Duplicates from Sorted Array Two Pointer

What is it?

Removing duplicates from a sorted array means changing the array so that each number appears only once, without changing the order. The two-pointer technique uses two positions moving through the array to find and skip duplicates efficiently. This method changes the array in place, so no extra space is needed. It returns the new length of the array after duplicates are removed.

Why it matters

Without removing duplicates, data can be messy and cause wrong results in programs, like counting or searching. Doing this efficiently saves time and memory, especially with large data. If we didn't have this method, programs would be slower or need more memory to handle duplicates. This technique helps keep data clean and fast to use.

Where it fits

Before learning this, you should understand arrays and basic loops. After this, you can learn about more complex array problems, like merging sorted arrays or sliding window techniques. This is a stepping stone to mastering efficient data manipulation.

Mental Model

Core Idea

Use two pointers to track unique elements and overwrite duplicates in a sorted array, keeping only one copy of each number.

Think of it like...

Imagine walking through a line of people sorted by height, and you want to keep only one person of each height. One hand points to the last unique person you kept, and the other hand scans ahead to find the next new height to keep.

Array: [1, 1, 2, 3, 3, 4]

Pointers:
  i -> last unique index
  j -> current scanning index

Process:
Start: i=0 (points to 1), j=1

Step 1: Compare arr[j]=1 with arr[i]=1 -> duplicate, move j
Step 2: j=2, arr[j]=2 != arr[i]=1 -> i=1, arr[i]=2
Step 3: j=3, arr[j]=3 != arr[i]=2 -> i=2, arr[i]=3
Step 4: j=4, arr[j]=3 == arr[i]=3 -> duplicate, move j
Step 5: j=5, arr[j]=4 != arr[i]=3 -> i=3, arr[i]=4

Result array front: [1, 2, 3, 4]

Build-Up - 6 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why duplicates appear consecutively.

A sorted array is a list of numbers arranged from smallest to largest. Because it's sorted, any duplicates will be next to each other. For example, in [1, 1, 2, 3, 3], the duplicates 1 and 3 are side by side. This property helps us find duplicates easily by comparing neighbors.

Result

Duplicates are always next to each other in a sorted array.

Knowing duplicates are consecutive lets us check only neighbors, making duplicate removal simpler and faster.

2

Foundation

Basics of Two Pointer Technique

Concept: Introduce two pointers moving through an array to track and process elements.

Two pointers are like two fingers on the array. One pointer (i) marks the position of the last unique element found. The other pointer (j) scans ahead to find new unique elements. When j finds a new number different from arr[i], we move i forward and copy arr[j] there. This way, i always points to the last unique number.

Result

Two pointers can separate unique and duplicate elements by scanning and overwriting.

Using two pointers avoids extra space and lets us update the array in place efficiently.

3

Intermediate

Implementing Two Pointer Duplicate Removal

🤔Before reading on: do you think the first pointer moves only when a new unique element is found, or on every step? Commit to your answer.

Concept: Apply two pointers to remove duplicates by overwriting duplicates with unique elements found ahead.

Start with i=0 (first element) and j=1 (second element). While j is less than array length, compare arr[j] with arr[i]. If different, increment i and set arr[i] = arr[j]. If same, just move j forward. After the loop, the first i+1 elements are unique.

Result

The array front contains unique elements, and the function returns the count of unique elements.

Understanding that i only moves when a new unique element is found prevents overwriting unique data and keeps the array clean.

4

Intermediate

Handling Edge Cases in Duplicate Removal

🤔Before reading on: do you think an empty array or single-element array needs special handling? Commit to your answer.

Concept: Learn how to handle arrays with zero or one element safely.

If the array is empty, return 0 because there are no elements. If it has one element, return 1 because it's already unique. This prevents errors like accessing elements that don't exist.

Result

The function safely handles empty and single-element arrays without errors.

Knowing edge cases prevents runtime errors and ensures your code works for all inputs.

5

Advanced

In-Place Modification and Return Value

🤔Before reading on: do you think the function returns the modified array or just the count of unique elements? Commit to your answer.

Concept: Understand that the function modifies the array in place and returns the new length of unique elements.

The function does not create a new array but changes the original one by moving unique elements to the front. It returns the count of unique elements, so the caller knows how many elements to consider. The rest of the array beyond this count can be ignored.

Result

The array front holds unique elements, and the returned length tells how many to use.

Returning the length instead of a new array saves memory and fits common programming patterns.

6

Expert

Performance and Memory Efficiency Analysis

🤔Before reading on: do you think this method uses extra memory proportional to input size? Commit to your answer.

Concept: Analyze time and space complexity of the two-pointer method for duplicate removal.

The method scans the array once, so time complexity is O(n), where n is the array length. It uses only a few variables for pointers, so space complexity is O(1), constant space. This is optimal because every element must be checked at least once, and no extra storage is needed.

Result

Efficient duplicate removal with linear time and constant space.

Understanding complexity helps choose the best method for large data and resource-limited environments.

Under the Hood

The two-pointer method works by maintaining a slow pointer (i) that marks the position of the last unique element and a fast pointer (j) that scans ahead. When arr[j] differs from arr[i], it means a new unique element is found. The algorithm increments i and copies arr[j] to arr[i], effectively overwriting duplicates. This process continues until j reaches the end. The array is modified in place, and the first i+1 elements are unique.

Why designed this way?

This approach was designed to optimize both time and space. Since the array is sorted, duplicates are adjacent, allowing a single pass to detect them. Using two pointers avoids extra memory allocation for a new array, which is important in memory-constrained environments. Alternatives like using hash sets require extra space and are slower for sorted arrays.

Start:
arr: [1, 1, 2, 3, 3, 4]

Pointers:
 i -> index 0 (value 1)
 j -> index 1 (value 1)

Loop:
 j moves forward:
  - If arr[j] == arr[i], j++ (skip duplicate)
  - Else i++, arr[i] = arr[j]

End:
 i=3, arr[:i+1] = [1, 2, 3, 4]

Array after removal:
[1, 2, 3, 4, 3, 4]
Only first i+1 elements matter.

Myth Busters - 4 Common Misconceptions

Quick: Does the two-pointer method require extra arrays to store unique elements? Commit yes or no.

Common Belief: You need to create a new array to store unique elements because you can't modify the original safely.

Reality: The two-pointer method modifies the original array in place without extra arrays.

Why it matters: Using extra arrays wastes memory and slows down the program, especially with large data.

Quick: Does the method work correctly if the array is not sorted? Commit yes or no.

Common Belief: The two-pointer method works on any array, sorted or not.

Reality: It only works correctly on sorted arrays because duplicates must be adjacent to detect them by comparing neighbors.

Why it matters: Using it on unsorted arrays leads to incorrect results, missing duplicates or removing unique elements.

Quick: After removal, are the elements beyond the new length guaranteed to be removed or zeroed out? Commit yes or no.

Common Belief: Elements beyond the returned length are removed or set to zero automatically.

Reality: Elements beyond the new length remain unchanged but should be ignored by the program.

Why it matters: Assuming those elements are removed can cause bugs if the program reads beyond the new length.

Quick: Does the slow pointer (i) move forward on every iteration? Commit yes or no.

Common Belief: The slow pointer moves forward on every step through the array.

Reality: The slow pointer only moves forward when a new unique element is found.

Why it matters: Moving the slow pointer incorrectly can overwrite unique elements or leave duplicates.

Expert Zone

1

The slow pointer (i) always points to the last unique element, so its position is crucial for correct overwriting.

2

The method relies heavily on the array being sorted; even a single unsorted element breaks correctness.

3

The elements beyond the returned length are not cleared, so the caller must respect the returned size to avoid bugs.

When NOT to use

Do not use this method on unsorted arrays; instead, use hash sets or sorting first. Also, if you need to preserve the original array, create a copy before modifying. For linked lists, use different techniques since random access is not available.

Production Patterns

This method is widely used in coding interviews and production code where memory efficiency is critical. It is a common pattern in data cleaning pipelines, search algorithms, and anywhere sorted data must be deduplicated quickly without extra space.

Connections

Sliding Window Technique

Both use multiple pointers moving through an array to solve problems efficiently.

Understanding two pointers helps grasp sliding windows, which also track ranges with pointers for sums or patterns.

In-Place Algorithms

This method is an example of in-place modification to save memory.

Knowing in-place techniques helps write memory-efficient code in many data structure problems.

Data Compression

Removing duplicates is a simple form of reducing data size, similar to compression.

Understanding duplicate removal aids in grasping how data compression algorithms reduce redundancy.

Common Pitfalls

#1 Moving the slow pointer on every iteration, not only when a new unique element is found.

Wrong approach:

for j := 1; j < len(nums); j++ {
i++
nums[i] = nums[j]
}

Correct approach:

for j := 1; j < len(nums); j++ {
if nums[j] != nums[i] {
i++
nums[i] = nums[j]
}
}

Root cause:

Misunderstanding that the slow pointer should only move when a new unique element is detected.

#2 Applying the method on an unsorted array without sorting first.

Wrong approach:

nums := []int{3, 1, 2, 3, 1}
// Apply two-pointer duplicate removal directly

Correct approach:

sort.Ints(nums)
// Then apply two-pointer duplicate removal

Root cause:

Not realizing the method depends on duplicates being adjacent in a sorted array.

#3 Ignoring the returned length and using the entire array after removal.

Wrong approach:

for _, v := range nums {
fmt.Println(v)
}

Correct approach:

length := removeDuplicates(nums)
for i := 0; i < length; i++ {
fmt.Println(nums[i])
}

Root cause:

Assuming the array is physically shortened or cleared beyond the unique elements.

Key Takeaways

Removing duplicates from a sorted array is efficient because duplicates are next to each other.

The two-pointer technique uses one pointer to track unique elements and another to scan ahead, modifying the array in place.

This method runs in linear time and constant space, making it optimal for large data.

Always handle edge cases like empty or single-element arrays to avoid errors.

The returned length tells how many elements are unique; elements beyond that should be ignored.

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