Remove Duplicates from Sorted Array Two Pointer in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the two-pointer technique in removing duplicates from a sorted array?

Use one pointer to track the position of the last unique element and another to scan through the array, copying unique elements forward.

beginner

Why does the two-pointer method work efficiently on a sorted array?

Because duplicates are adjacent, so scanning once with two pointers can identify and skip duplicates without extra space.

intermediate

In the two-pointer approach, what does the 'slow' pointer represent?

The index where the next unique element should be placed, effectively marking the end of the unique elements found so far.

beginner

What is the time complexity of removing duplicates from a sorted array using the two-pointer technique?

O(n), where n is the length of the array, because each element is visited once.

beginner

What is the space complexity of the two-pointer method for removing duplicates in-place?

O(1), since it modifies the array in place without using extra space.

What does the fast pointer do in the two-pointer approach to remove duplicates?

A Marks the position of the last unique element

B Scans through the array to find unique elements

C Deletes duplicates directly

D Sorts the array

The fast pointer moves through the array to find unique elements to copy forward.

Why is the array required to be sorted for this two-pointer method to work correctly?

A Because unsorted arrays have no duplicates

B Because sorting removes duplicates automatically

C Because duplicates are grouped together

D Because the method sorts the array internally

Duplicates must be adjacent to be detected by comparing current and previous elements.

What is the final output of the two-pointer method for removing duplicates from a sorted array?

A Length of the array after removing duplicates

B New array with duplicates removed

C Number of duplicates found

D Sorted array with duplicates

The method returns the length of the unique elements segment in the original array.

What happens when the fast pointer finds a new unique element?

A It is copied to the position after the last unique element

B It is ignored

C The array is resized

D The slow pointer moves backwards

The unique element is copied forward to keep all unique elements contiguous.

What is the space complexity of the two-pointer approach for removing duplicates?

A O(n^2)

B O(log n)

C O(n)

D O(1)

The method modifies the array in place without extra space.

Explain how the two-pointer technique removes duplicates from a sorted array step-by-step.

Think about how you move through the array and keep track of unique values.

Describe why the two-pointer method is efficient for removing duplicates in a sorted array compared to other methods.

Consider time and space usage and the sorted property.

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