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

→Pointer2 at index 1

↓

Compare arr[Pointer1

↓

Move Pointer2 forward

↓

Repeat until Pointer2 reaches end

↓

Return length = Pointer1 + 1

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

Execution Sample

DSA C++

int removeDuplicates(vector<int>& nums) {
  if (nums.empty()) return 0;
  int i = 0;
  for (int j = 1; j < nums.size(); 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	Pointer j	Array State	Action
1	Initialize pointers	0	1	[1, 1, 2, 2, 3]	Start with i=0, j=1
2	Compare nums[i] and nums[j]	0	1	[1, 1, 2, 2, 3]	nums[0]=1 == nums[1]=1, duplicate found, move j
3	Move j forward	0	2	[1, 1, 2, 2, 3]	j=2
4	Compare nums[i] and nums[j]	0	2	[1, 1, 2, 2, 3]	nums[0]=1 != nums[2]=2, unique found
5	Increment i and copy nums[j]	1	2	[1, 2, 2, 2, 3]	i=1, nums[1]=2
6	Move j forward	1	3	[1, 2, 2, 2, 3]	j=3
7	Compare nums[i] and nums[j]	1	3	[1, 2, 2, 2, 3]	nums[1]=2 == nums[3]=2, duplicate found, move j
8	Move j forward	1	4	[1, 2, 2, 2, 3]	j=4
9	Compare nums[i] and nums[j]	1	4	[1, 2, 2, 2, 3]	nums[1]=2 != nums[4]=3, unique found
10	Increment i and copy nums[j]	2	4	[1, 2, 3, 2, 3]	i=2, nums[2]=3
11	Move j forward	2	5	[1, 2, 3, 2, 3]	j=5 (end of array)
12	End loop	2	5	[1, 2, 3, 2, 3]	Return length = i+1 = 3

💡 j reaches array length 5, loop ends, unique elements count is i+1 = 3

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 7	After Step 9	After Step 10	Final
i	0	0	0	1	1	1	2	2
j	1	1	2	2	3	4	4	5
nums	[1,1,2,2,3]	[1,1,2,2,3]	[1,1,2,2,3]	[1,2,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 5 and 10 where i increments and nums[i] is updated.

Why do we compare nums[i] and nums[j] instead of nums[j] and nums[j-1]?

Comparing nums[i] and nums[j] ensures we compare the last unique element with the current scanning element. This is clear in steps 4 and 9 where the comparison decides if a new unique element is found.

What happens if the array is empty or has one element?

If empty, the loop never runs and length 0 is returned. If one element, i=0 and loop doesn't run, returning length 1. This is implied by the initialization in step 1.

Visual Quiz - 3 Questions

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

A 2

B 0

C 1

D 3

💡 Hint

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

At which step does the condition nums[i] != nums[j] first become true?

A Step 4

B Step 7

C Step 2

D Step 9

💡 Hint

Look at the 'Operation' and 'Action' columns in the execution_table for the first unique element detection.

If the input array was [1,1,1,1,1], how would the pointer i change?

A i would increment each step

B i would remain 0 throughout

C i would increment only once

D i would decrement

💡 Hint

Refer to variable_tracker and note that i only increments when a new unique element is found.

Concept Snapshot

Remove duplicates from a sorted array using two pointers:
- i tracks last unique element index
- j scans ahead for new unique elements
- When nums[j] != nums[i], increment i and copy nums[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 marks the position of the last unique element found. Pointer j scans through the array comparing its value with nums[i]. When a new unique value is found at nums[j], i increments and nums[j] is copied to nums[i]. This process continues until j reaches the end of the array. The final length of unique elements is i+1. The execution table shows each step, pointer positions, array state, and actions taken. Variable tracker records how pointers and array change over time. Key moments clarify why pointer i moves only on unique finds and why comparisons are done between nums[i] and nums[j]. The visual quiz tests understanding of pointer movements and conditions. This method is efficient and uses constant extra space.

Practice

1. What is the main purpose of the two-pointer technique in removing duplicates from a sorted array?

easy

A. To track unique elements and overwrite duplicates in-place

B. To sort the array again after removing duplicates

C. To create a new array with duplicates removed

D. To count the total number of duplicates only

Solution

1. Step 1: Understand the two-pointer roles

   One pointer tracks the position to place unique elements, the other scans the array.

2. Step 2: Overwrite duplicates in-place

   When a new unique element is found, it is placed at the tracked position, replacing duplicates.

3. Final Answer:

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

4. Quick Check:

   Two-pointer technique = overwrite duplicates [OK]

Hint: Two pointers: one scans, one writes unique values [OK]

Common Mistakes:

• Thinking it creates a new array instead of modifying in-place
• Assuming it sorts the array again
• Confusing counting duplicates with removing them

2. Which of the following is the correct syntax to initialize the two pointers for removing duplicates from a sorted array nums in C++?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

C. int i = 0, j = 0;

D. int i = 1, j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i tracks the last unique element index, starting at 0; j scans from 1.

2. Step 2: Initialize pointers accordingly

   Set i = 0 and j = 1 to start comparing from the second element.

3. Final Answer:

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

4. Quick Check:

   i=0, j=1 start positions [OK]

Hint: Start i at 0, j at 1 to compare neighbors [OK]

Common Mistakes:

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

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

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify unique elements in order

   Unique elements are 1, 2, 3, 4.

2. Step 2: Count unique elements

   There are 4 unique elements, so the length after removal is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Unique count = 4 [OK]

Hint: Count unique numbers in sorted array [OK]

Common Mistakes:

• Counting duplicates as unique
• Confusing length with original array size
• Off-by-one errors in counting

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

int removeDuplicates(vector<int>& nums) {
    int i = 0, j = 1;
    while (j < nums.size()) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. The loop should use for instead of while

B. Pointers i and j should start at 1 and 0 respectively

C. The condition should be nums[i] == nums[j] instead of !=

D. Return value should be i + 1, not i

Solution

1. Step 1: Understand pointer i meaning

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

2. Step 2: Check return statement

   Returning i alone gives index, not count; must return i + 1 for length.

3. Final Answer:

   Return value should be i + 1, not i -> Option D

4. Quick Check:

   Length = last index + 1 [OK]

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

Common Mistakes:

• Returning i instead of i + 1
• Swapping pointer initializations
• Using wrong comparison operator

5. Given a sorted array nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}, what will be the state of the array after applying the two-pointer method to remove duplicates, and what is the new length?

hard

A. Array: {0, 1, 1, 2, 3, 4, _, _, _, _}, Length: 4

B. Array: {0, 0, 1, 1, 2, 2, 3, 3, 4, 4}, Length: 6

C. Array: {0, 1, 2, 3, 4, _, _, _, _, _}, Length: 5

D. Array: {0, 1, 2, 3, 4, 5, _, _, _, _}, Length: 6

Solution

1. Step 1: Identify unique elements in order

   Unique elements are 0, 1, 2, 3, 4.

2. Step 2: Overwrite duplicates in-place

   Using two pointers, these unique elements overwrite the start of the array.

3. Step 3: Determine new length

   There are 5 unique elements, so length is 5.

4. Final Answer:

   Array: {0, 1, 2, 3, 4, _, _, _, _, _}, Length: 5 -> Option C

5. Quick Check:

   Unique elements = 5, array start updated [OK]

Hint: Unique elements overwrite start, length = count unique [OK]

Common Mistakes:

• Not overwriting duplicates correctly
• Miscounting unique elements
• Assuming array length stays same