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

Concept Flow - Remove Duplicates from Sorted Array Two Pointer

Start with two pointers

↓

Pointer1 at index 0

↓

Compare values at Pointer1 and Pointer2

↓

Repeat until Pointer2 reaches end

↓

Return length = Pointer1 + 1

Use two pointers to scan the array. One pointer tracks unique elements, the other scans ahead to find new unique values to copy.

Execution Sample

DSA C#

int RemoveDuplicates(int[] nums) {
  int i = 0;
  for (int j = 1; j < nums.Length; j++) {
    if (nums[j] != nums[i]) {
      i++;
      nums[i] = nums[j];
    }
  }
  return i + 1;
}

This code removes duplicates from a sorted array in place and returns the new length of unique elements.

Execution Table

Step	Operation	Pointer i	Pointer j	Array State	Action
Start	Initialize pointers	0	1	[0,0,1,1,2,2,3,3,4,4]	Set i=0, j=1
1	Compare nums[i] and nums[j]	0	1	[0,0,1,1,2,2,3,3,4,4]	nums[1]=0 equals nums[0]=0, move j
2	Move j forward	0	2	[0,0,1,1,2,2,3,3,4,4]	j=2
3	Compare nums[i] and nums[j]	0	2	[0,0,1,1,2,2,3,3,4,4]	nums[2]=1 != nums[0]=0, increment i and copy
4	Increment i and copy	1	2	[0,1,1,1,2,2,3,3,4,4]	nums[1]=1 copied from nums[2]
5	Move j forward	1	3	[0,1,1,1,2,2,3,3,4,4]	j=3
6	Compare nums[i] and nums[j]	1	3	[0,1,1,1,2,2,3,3,4,4]	nums[3]=1 equals nums[1]=1, move j
7	Move j forward	1	4	[0,1,1,1,2,2,3,3,4,4]	j=4
8	Compare nums[i] and nums[j]	1	4	[0,1,1,1,2,2,3,3,4,4]	nums[4]=2 != nums[1]=1, increment i and copy
9	Increment i and copy	2	4	[0,1,2,1,2,2,3,3,4,4]	nums[2]=2 copied from nums[4]
10	Move j forward	2	5	[0,1,2,1,2,2,3,3,4,4]	j=5
11	Compare nums[i] and nums[j]	2	5	[0,1,2,1,2,2,3,3,4,4]	nums[5]=2 equals nums[2]=2, move j
12	Move j forward	2	6	[0,1,2,1,2,2,3,3,4,4]	j=6
13	Compare nums[i] and nums[j]	2	6	[0,1,2,1,2,2,3,3,4,4]	nums[6]=3 != nums[2]=2, increment i and copy
14	Increment i and copy	3	6	[0,1,2,3,2,2,3,3,4,4]	nums[3]=3 copied from nums[6]
15	Move j forward	3	7	[0,1,2,3,2,2,3,3,4,4]	j=7
16	Compare nums[i] and nums[j]	3	7	[0,1,2,3,2,2,3,3,4,4]	nums[7]=3 equals nums[3]=3, move j
17	Move j forward	3	8	[0,1,2,3,2,2,3,3,4,4]	j=8
18	Compare nums[i] and nums[j]	3	8	[0,1,2,3,2,2,3,3,4,4]	nums[8]=4 != nums[3]=3, increment i and copy
19	Increment i and copy	4	8	[0,1,2,3,4,2,3,3,4,4]	nums[4]=4 copied from nums[8]
20	Move j forward	4	9	[0,1,2,3,4,2,3,3,4,4]	j=9
21	Compare nums[i] and nums[j]	4	9	[0,1,2,3,4,2,3,3,4,4]	nums[9]=4 equals nums[4]=4, move j
22	Move j forward	4	10	[0,1,2,3,4,2,3,3,4,4]	j=10 (end)
End	Return length	4	10	[0,1,2,3,4,2,3,3,4,4]	Length = i+1 = 5

💡 j reaches array length, loop ends, return i+1 as new length

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
i	0	0	1	1	2	2	3	3	4	4	4
j	1	2	3	4	5	6	7	8	9	10	10
Array	[0,0,1,1,2,2,3,3,4,4]	[0,0,1,1,2,2,3,3,4,4]	[0,1,1,1,2,2,3,3,4,4]	[0,1,1,1,2,2,3,3,4,4]	[0,1,2,1,2,2,3,3,4,4]	[0,1,2,1,2,2,3,3,4,4]	[0,1,2,3,2,2,3,3,4,4]	[0,1,2,3,2,2,3,3,4,4]	[0,1,2,3,4,2,3,3,4,4]	[0,1,2,3,4,2,3,3,4,4]	[0,1,2,3,4,2,3,3,4,4]

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 when we find a new unique value to overwrite the next position. This is shown in steps 3-4 and 8-9 where i increments and the array is updated.

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

Pointer i always points to the last unique element, so comparing nums[j] with nums[i] ensures we detect duplicates correctly. This is clear in the execution table rows where comparisons happen between nums[j] and nums[i].

What happens when nums[j] equals nums[i]?

When nums[j] equals nums[i], it means the element is a duplicate, so we only move pointer j forward to check the next element without changing i or the array. See steps 1-2 and 6-7 for this behavior.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of pointer i after step 9?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'Pointer i' column at step 9 in the execution_table.

At which step does the array first change from [0,0,1,1,2,2,3,3,4,4] to [0,1,1,1,2,2,3,3,4,4]?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Array State' column and find when the second element changes.

If the input array had no duplicates, how would the pointer i change compared to this execution?

A i would increment only once

B i would stay at 0

C i would increment at every step until the end

D i would decrement

💡 Hint

Refer to the variable_tracker for i's increments and think about unique elements.

Concept Snapshot

Remove Duplicates from Sorted Array using Two Pointers:
- Use i to track last unique index, j to scan array
- If nums[j] != nums[i], increment i and copy nums[j]
- Continue until j reaches end
- Return i + 1 as new length
- Modifies array in place, no extra space needed

Full Transcript

This concept uses two pointers to remove duplicates from a sorted array. Pointer i tracks the position of the last unique element found. Pointer j scans through the array. When nums[j] differs from nums[i], i is incremented and nums[j] is copied to nums[i]. This process continues until j reaches the end of the array. The new length of unique elements is i + 1. The array is modified in place without extra space. The execution table shows each step, pointer positions, array state, and actions. Key moments clarify why i moves only on new unique elements and why comparisons are made between nums[j] and nums[i]. The visual quiz tests understanding of pointer positions and array changes during execution.

Practice

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

easy

A. To create a new array with unique elements

B. To sort the array before removing duplicates

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

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.

2. Step 2: Purpose of pointers in-place

   This method avoids extra space by overwriting duplicates directly in the original array.

3. Final Answer:

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

4. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers track and overwrite duplicates without extra space [OK]

Common Mistakes:

• Thinking two pointers sort the array
• Assuming a new array is created
• Confusing counting duplicates with removing them

2. Which of the following is the correct C# syntax to initialize the two pointers i and j for the problem?

easy

A. int i = 1; int j = 1;

B. int i = 1, j = 0;

C. int i = 0; int j = 0;

D. int i = 0, j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i starts at index 0 to track unique elements, j starts at 1 to scan ahead.

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 matches the logic of comparing current and next elements.

3. Final Answer:

   int i = 0, j = 1; -> Option D

4. Quick Check:

   Start i at 0 and j at 1 [OK]

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

Common Mistakes:

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

3. What will be the output array and new length after running the two-pointer method on the sorted array [1, 1, 2, 3, 3]?

medium

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

B. [1, 2, 3], length = 3

C. [1, 1, 2, 3, 3], length = 5

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

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1. Compare elements: skip duplicates, overwrite unique elements at i+1.

2. Step 2: Final array and length

   Unique elements are 1, 2, 3 placed at start. Length is 3.

3. Final Answer:

   [1, 2, 3], length = 3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Overwrite duplicates, count unique elements for length [OK]

Common Mistakes:

• Not updating length after removal
• Leaving duplicates in output
• Misplacing unique elements

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

int RemoveDuplicates(int[] nums) {
    int i = 0, j = 1;
    while (j < nums.Length) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. The function should return i + 1 instead of i

B. Pointers i and j should both start at 1

C. The while loop condition should be j <= nums.Length

D. The array should be sorted inside the function

Solution

1. Step 1: Understand pointer meaning

   Pointer i tracks last unique element index, so length is i + 1.

2. Step 2: Check return value

   Returning i alone misses counting the first element, so return i + 1.

3. Final Answer:

   The function should return i + 1 instead of i -> Option A

4. Quick Check:

   Return length as i + 1 [OK]

Hint: Return i + 1 as length, not just i [OK]

Common Mistakes:

• Returning i instead of i + 1
• Incorrect loop boundary causing out-of-range
• Sorting array inside function unnecessarily

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

hard

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

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

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

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

Solution

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

   Start with i=0, j=1. Move j forward, overwrite duplicates by placing unique elements at i+1.

2. Step 2: Final array and length

   Unique elements are 0,1,2,3,4 placed at start. Length is 5.

3. Final Answer:

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

4. Quick Check:

   Unique count = 5 [OK]

Hint: Overwrite duplicates, count unique elements for final length [OK]

Common Mistakes:

• Leaving duplicates in the array
• Returning wrong length
• Misplacing unique elements during overwrite