Remove Duplicates from Sorted Array Two Pointer in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the two-pointer technique for removing duplicates from a sorted array?

Use one pointer to track the position of unique elements and another to scan through the array. When a new unique element is found, move it next to the last unique element.

beginner

In the two-pointer method, what does the 'slow' pointer represent?

The 'slow' pointer marks the position where the next unique element should be placed.

intermediate

Why does the two-pointer approach work efficiently on a sorted array?

Because duplicates are adjacent, so scanning once with two pointers can identify and skip duplicates without extra space.

beginner

What is the time complexity of removing duplicates from a sorted array using the two-pointer technique?

O(n), where n is the length of the array, because each element is visited at most once.

intermediate

How does the two-pointer method modify the input array when removing duplicates?

It overwrites duplicate elements by moving unique elements forward, so the first part of the array contains only unique values.

What does the 'fast' pointer do in the two-pointer approach for removing duplicates?

A Sorts the array

B Marks the position to place the next unique element

C Deletes duplicate elements directly

D Scans through the array to find unique elements

The 'fast' pointer moves through the array to find unique elements while the 'slow' pointer tracks where to place them.

Why is the array required to be sorted for the two-pointer duplicate removal method?

A So duplicates are grouped together

B To use extra memory efficiently

C To allow binary search

D To reverse the array easily

Sorting groups duplicates together, making it easy to detect and skip them with two pointers.

What is the space complexity of the two-pointer method for removing duplicates?

A O(n)

B O(log n)

C O(1)

D O(n^2)

The method modifies the array in place and uses only a few pointers, so space complexity is constant.

After removing duplicates using two pointers, what does the returned length represent?

A Number of unique elements

B Total elements including duplicates

C Number of duplicates removed

D Array capacity

The returned length is the count of unique elements now at the start of the array.

If the input array is [1,1,2], what will be the array state after removing duplicates using two pointers?

A [2,2,2]

B [1,2,2]

C [1,1,2]

D [1,2,1]

The unique elements 1 and 2 are moved to the front: [1,2,...]. The rest of the array beyond the new length is not important.

Explain how the two-pointer technique removes duplicates from a sorted array in place.

Think about scanning and placing unique values next to each other.

Describe why the two-pointer method is efficient for removing duplicates from a sorted array compared to other methods.

Focus on time and space benefits.

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