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 elements at Pointer1 and Pointer2

↓

Repeat until Pointer2 reaches end

↓

Return length = Pointer1 + 1

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

Execution Sample

DSA C

int removeDuplicates(int* nums, int numsSize) {
    int i = 0;
    for (int j = 1; j < numsSize; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return 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 (unique index)	Pointer j (scan index)	Array State	Action
0	Initialize pointers	0	1	[1,1,2,2,3]	Start with i=0, j=1
1	Compare nums[j] and nums[i]	0	1	[1,1,2,2,3]	nums[1]=1 == nums[0]=1, duplicate found, move j
2	Increment j	0	2	[1,1,2,2,3]	j moves to 2
3	Compare nums[j] and nums[i]	0	2	[1,1,2,2,3]	nums[2]=2 != nums[0]=1, unique found
4	Increment i and copy nums[j]	1	2	[1,2,2,2,3]	i=1, nums[1]=2
5	Increment j	1	3	[1,2,2,2,3]	j moves to 3
6	Compare nums[j] and nums[i]	1	3	[1,2,2,2,3]	nums[3]=2 == nums[1]=2, duplicate found, move j
7	Increment j	1	4	[1,2,2,2,3]	j moves to 4
8	Compare nums[j] and nums[i]	1	4	[1,2,2,2,3]	nums[4]=3 != nums[1]=2, unique found
9	Increment i and copy nums[j]	2	4	[1,2,3,2,3]	i=2, nums[2]=3
10	Increment j	2	5	[1,2,3,2,3]	j moves beyond array length, stop
11	Return new length	2	5	[1,2,3,2,3]	Length = i + 1 = 3

💡 j reaches 5 which is numsSize, loop ends

Variable Tracker

Variable	Start	After Step 4	After Step 9	Final
i	0	1	2	2
j	1	2	4	5
nums	[1,1,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?

Because i tracks the position of the last unique element. We only move it forward to store the next unique value, as shown in steps 4 and 9.

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, as seen in steps 3 and 8.

What happens to the elements after the new length?

They remain unchanged but are ignored. The function returns the new length (i+1), so only the first part of the array up to that length is valid, as in step 11.

Visual Quiz - 3 Questions

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

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Pointer i (unique index)' column at step 4 in the execution table.

At which step does the pointer j move beyond the array length?

A Step 9

B Step 10

C Step 11

D Step 8

💡 Hint

Look at the 'Pointer j (scan index)' column and the 'Action' description in the execution table.

If the array was [1,1,1,1,1], what would be the final value of i?

A 0

B 1

C 4

D 5

💡 Hint

Since all elements are duplicates, i stays at 0 as no new unique elements are found.

Concept Snapshot

Remove duplicates from a sorted array using two pointers:
- i tracks last unique element index
- j scans through array
- When nums[j] != nums[i], increment i and copy nums[j]
- Return i + 1 as new length
- Modifies array in-place without extra space

Full Transcript

This concept uses two pointers to remove duplicates from a sorted array in-place. Pointer i marks the position of the last unique element found. Pointer j scans the array from the second element onward. When nums[j] is different from nums[i], it means a new unique element is found. We increment i and copy nums[j] to nums[i]. This process continues until j reaches the end of the array. The function returns i + 1, which is the count of unique elements. The array is modified so that the first i+1 elements are unique, and duplicates beyond that are 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.

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 A

4. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers track unique and current elements [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 syntax to initialize two pointers i and j for the two-pointer approach in C?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

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

D. int i, j = 0;

Solution

1. Step 1: Understand pointer roles

   Pointer i starts at 0 (first unique), j starts at 1 (scanning next elements).

2. Step 2: Correct initialization syntax

   Both pointers must be initialized properly; int i = 0, j = 1; is correct in C.

3. Final Answer:

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

4. Quick Check:

   Initialize i=0 and j=1 for two-pointer [OK]

Hint: Start i at 0 and j at 1 for scanning [OK]

Common Mistakes:

• Swapping initial values of i and j
• Initializing both pointers to 0
• Incorrect declaration syntax

3. What will be the output length after removing duplicates using the two-pointer method on the sorted array [1, 1, 2, 3, 3, 4]?

medium

A. 6

B. 5

C. 3

D. 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1. Compare elements: duplicates skipped, unique elements moved forward.

2. Step 2: Count unique elements

   Unique elements are 1, 2, 3, 4. So length is 4 after removal.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Unique elements count = 4 [OK]

Hint: Count unique elements after skipping duplicates [OK]

Common Mistakes:

• Counting duplicates as unique
• Assuming length stays same
• Miscounting unique elements

4. Identify the bug in this C code snippet for removing duplicates from a sorted array:

int removeDuplicates(int* nums, int numsSize) {
    int i = 0, j = 1;
    while (j < numsSize) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. Does not check for array size zero

B. Pointers i and j are initialized incorrectly

C. Returns i instead of i+1 as new length

D. Uses while loop instead of for loop

Solution

1. Step 1: Analyze return value

   Variable i tracks last unique index, so length is i+1, not i.

2. Step 2: Identify correct return

   Returning i misses counting the first element, causing off-by-one error.

3. Final Answer:

   Returns i instead of i+1 as new length -> Option C

4. Quick Check:

   Return length = i+1, not i [OK]

Hint: Return last index + 1 for length [OK]

Common Mistakes:

• Off-by-one error in return value
• Ignoring empty array edge case
• Confusing pointer initialization

5. Given a sorted array nums = [0,0,1,1,1,2,2,3,3,4], what will be the array state after applying the two-pointer method to remove duplicates?

hard

A. [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

B. [0, 1, 2, 3, 4, _, _, _, _, _]

C. [0, 1, 1, 2, 3, 4, _, _, _, _]

D. [0, 1, 2, 3, 4, 5, _, _, _, _]

Solution

1. Step 1: Apply two-pointer overwrite

   Unique elements 0,1,2,3,4 are moved to front positions in array.

2. Step 2: Final array state

   Positions after unique elements remain unchanged or ignored (represented as underscores).

3. Final Answer:

   [0, 1, 2, 3, 4, _, _, _, _, _] -> Option B

4. Quick Check:

   Array front holds unique elements [OK]

Hint: Unique elements overwrite front, rest ignored [OK]

Common Mistakes:

• Assuming duplicates remain in place
• Misplacing unique elements
• Confusing array length with content