Remove Duplicates from Sorted Array Two Pointer in DSA Go - Execution Trace

Concept Flow - Remove Duplicates from Sorted Array Two Pointer

Start with two pointers

↓

Pointer i at index 0

↓

Pointer j scans from index 1 to end

↓

Compare arr[j

↓

j

↓

End when j reaches array end

↓

Return length i+1 as new size

Two pointers scan the sorted array; one tracks unique elements, the other scans ahead to find new unique values to copy forward.

Execution Sample

DSA Go

arr := []int{1,1,2,2,3}
i := 0
for j := 1; j < len(arr); j++ {
  if arr[j] != arr[i] {
    i++
    arr[i] = arr[j]
  }
}
newLength := i + 1

This code removes duplicates in-place from a sorted array using two pointers and returns the new length.

Execution Table

Step	Operation	Pointer i	Pointer j	Array State	Action
0	Initialize pointers	0	1	[1,1,2,2,3]	Start with i=0, j=1
1	Compare arr[j] and arr[i]	0	1	[1,1,2,2,3]	arr[1]=1 equals arr[0]=1, skip
2	Increment j	0	2	[1,1,2,2,3]	Move j to 2
3	Compare arr[j] and arr[i]	0	2	[1,1,2,2,3]	arr[2]=2 not equal arr[0]=1, increment i and copy
4	Copy arr[j] to arr[i]	1	2	[1,2,2,2,3]	arr[1] = 2
5	Increment j	1	3	[1,2,2,2,3]	Move j to 3
6	Compare arr[j] and arr[i]	1	3	[1,2,2,2,3]	arr[3]=2 equals arr[1]=2, skip
7	Increment j	1	4	[1,2,2,2,3]	Move j to 4
8	Compare arr[j] and arr[i]	1	4	[1,2,2,2,3]	arr[4]=3 not equal arr[1]=2, increment i and copy
9	Copy arr[j] to arr[i]	2	4	[1,2,3,2,3]	arr[2] = 3
10	Increment j	2	5	[1,2,3,2,3]	j reached array end
11	Return new length	2	5	[1,2,3,2,3]	New length = i+1 = 3

💡 j reaches array length 5, loop ends, new length is i+1 = 3

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
i	0	0	1	1	2	2
j	1	2	3	4	5	5
arr	[1,1,2,2,3]	[1,1,2,2,3]	[1,2,2,2,3]	[1,2,2,2,3]	[1,2,3,2,3]	[1,2,3,2,3]

Key Moments - 3 Insights

Why do we increment pointer i only when we find a new unique element?

Pointer i marks the position of the last unique element. We only move it forward to store a new unique value, as shown in steps 3 and 8 in the execution_table.

Why do we compare arr[j] with arr[i] and not with arr[j-1]?

Pointer i always points to the last unique element, so comparing arr[j] with arr[i] ensures we detect duplicates correctly. This is clear in steps 3 and 8 where arr[j] != arr[i] triggers copying.

What happens to the elements after the new length?

Elements after the new length remain in the array but are ignored. The algorithm only guarantees unique elements up to index i, as seen in the final array state in step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the array state?

A [1,1,2,2,3]

B [1,2,2,2,3]

C [1,2,3,2,3]

D [1,1,3,2,3]

💡 Hint

Check the 'Array State' column at step 4 in the execution_table.

At which step does pointer i first increment?

A Step 1

B Step 6

C Step 3

D Step 8

💡 Hint

Look at the 'Pointer i' column changes in the execution_table.

If the array was [1,1,1,1], what would be the new length after execution?

A 1

B 2

C 3

D 4

💡 Hint

Refer to the variable_tracker and execution_table logic where duplicates are skipped.

Concept Snapshot

Remove duplicates from a sorted array using two pointers:
- i tracks last unique element index
- j scans through array
- If arr[j] != arr[i], increment i and copy arr[j]
- Return i+1 as new length
- In-place, O(n) time, O(1) space

Full Transcript

This concept uses two pointers to remove duplicates from a sorted array in-place. Pointer i starts at index 0 and marks the last unique element found. Pointer j scans from index 1 to the end. When arr[j] is different from arr[i], we increment i and copy arr[j] to arr[i]. This way, all unique elements are moved to the front of the array. The process continues until j reaches the end. The new length of the array without duplicates is i+1. Elements beyond this length are ignored. This method is efficient and uses constant extra space.

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