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

Concept Flow - Remove Duplicates from Sorted Array Two Pointer

Start with two pointers

↓

Pointer1 at index 0

↓

Pointer2 at index 1

↓

Compare values at Pointer1 and Pointer2

↓

Move Pointer2 forward

↓

Repeat until Pointer2 reaches end

↓

Return length = Pointer1 + 1

Use two pointers to scan the array. Pointer1 tracks unique elements, Pointer2 scans ahead. When new unique found, copy it forward.

Execution Sample

DSA Java

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

This code removes duplicates in-place from a sorted array 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 nums[i] and nums[j]	0	1	[1,1,2,2,3]	nums[1]=1 equals nums[0]=1, j++
2	Compare nums[i] and nums[j]	0	2	[1,1,2,2,3]	nums[2]=2 not equal nums[0]=1, i++, nums[1]=2
3	Array updated	1	2	[1,2,2,2,3]	Copied 2 to position 1
4	Compare nums[i] and nums[j]	1	3	[1,2,2,2,3]	nums[3]=2 equals nums[1]=2, j++
5	Compare nums[i] and nums[j]	1	4	[1,2,2,2,3]	nums[4]=3 not equal nums[1]=2, i++, nums[2]=3
6	Array updated	2	4	[1,2,3,2,3]	Copied 3 to position 2
7	End of array	2	5	[1,2,3,2,3]	j reached end, return length i+1=3

💡 Pointer j reached end of array, loop ends

Variable Tracker

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

Because pointer i marks the position of last unique element. We only move it forward to store a new unique value, as shown in steps 2 and 5 where i increments and array updates happen.

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 new unique values correctly. This is clear in steps 1 and 4 where comparisons happen.

What happens if the array has all duplicates?

Pointer i stays at 0, and pointer j moves through the array without copying new values. The returned length is 1, meaning only one unique element remains, as shown in step 1.

Visual Quiz - 3 Questions

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

A 0

B 2

C 1

D 3

💡 Hint

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

At which step does the array first get updated with a new unique value?

A Step 1

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the first 'Array updated' operation in the execution_table.

If the input array was [1,1,1,1], what would be the returned length?

A 1

B 4

C 0

D 2

💡 Hint

Refer to key_moments about all duplicates and the final length returned.

Concept Snapshot

Remove duplicates from sorted array using two pointers:
- Pointer i tracks last unique element index
- Pointer j scans array
- If nums[j] != nums[i], increment i and copy nums[j] to nums[i]
- Continue until j reaches end
- Return i + 1 as new length

Full Transcript

This concept uses two pointers to remove duplicates from a sorted array in place. Pointer i starts at 0 and marks the last unique element's position. Pointer j scans from index 1 forward. When nums[j] differs from nums[i], pointer i moves forward and nums[j] is copied to nums[i]. This way, unique elements are collected at the start of the array. The process continues until pointer j reaches the end. The new length of unique elements is i + 1. The execution table shows each step with pointer positions and array state changes. Key moments clarify why pointer i moves only on new unique values and why comparisons are made with nums[i]. The visual quiz tests understanding of pointer positions and array updates.

Practice

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

easy

A. To sort the array before removing duplicates

B. To count the total number of duplicates in the array

C. To create a new array with unique elements

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

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, keeping unique elements at the start.

3. Final Answer:

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

4. Quick Check:

   Two pointers help remove duplicates without extra space [OK]

Hint: Two pointers move to keep unique elements compact [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 the two pointers i and j for the problem in Java?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

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

D. int i = 1; int j = 1;

Solution

1. Step 1: Identify pointer roles

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

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 allows scanning from second element while i marks last unique.

3. Final Answer:

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

4. Quick Check:

   Start i at 0, j at 1 to scan array [OK]

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

Common Mistakes:

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

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

medium

A. 2

B. 3

C. 5

D. 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1; compare elements and overwrite duplicates: unique elements are 1, 2, 3.

2. Step 2: Count unique elements

   After processing, unique elements count is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Count unique elements after skipping duplicates [OK]

Common Mistakes:

• Counting duplicates instead of unique
• Assuming length stays same
• Miscounting when duplicates are consecutive

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

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

medium

A. Pointers initialized incorrectly

B. Incorrect comparison operator used

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

D. Does not increment j inside the loop

Solution

1. Step 1: Analyze return value

   The variable i tracks last unique index, so length is i + 1.

2. Step 2: Identify mistake in return

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

3. Final Answer:

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

4. Quick Check:

   Length = last index + 1 [OK]

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

Common Mistakes:

• Returning i instead of i + 1
• Forgetting to increment j
• Using wrong comparison operator

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, 1, 2, 3, 4, _, _, _, _, _]

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

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

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

Solution

1. Step 1: Apply two-pointer overwrite

   Start with i=0, j=1; overwrite duplicates by moving unique elements forward: unique elements are 0,1,2,3,4.

2. Step 2: Final array state

   First five positions hold unique elements [0,1,2,3,4], rest remain unchanged or ignored.

3. Final Answer:

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

4. Quick Check:

   Unique elements compacted at start [OK]

Hint: Unique elements fill front, duplicates ignored after [OK]

Common Mistakes:

• Assuming duplicates remain in place
• Misplacing unique elements
• Counting extra elements beyond unique count