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

Recall & Review

beginner

What is the main idea behind the two-pointer approach to remove duplicates from a sorted array?

Use one pointer to track the position of unique elements and another to scan through the array. When a new unique element is found, place it at the unique pointer's position and move the pointer forward.

beginner

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

Because duplicates are adjacent in a sorted array, the method can easily detect duplicates by comparing current and previous elements, avoiding extra space and multiple passes.

beginner

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

The 'slow' pointer marks the position where the next unique element should be placed, effectively tracking the length of the array without duplicates.

beginner

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

O(n), where n is the number of elements in the array, because each element is visited at most once.

intermediate

What happens to the elements after the 'slow' pointer in the array after duplicates are removed?

They remain in the array but are not considered part of the unique elements. The array length is effectively the position of the 'slow' pointer.

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

A Sorts the array

B Marks the position of unique elements

C Scans through the array to find unique elements

D Deletes duplicates directly

The 'fast' pointer moves through the array to find unique elements by comparing with the previous element.

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

A Because duplicates are grouped together

B Because sorting removes duplicates automatically

C Because the method uses hashing

D Because the array size must be fixed

Duplicates appear next to each other in a sorted array, making it easy to detect and skip them.

What is the final output of the two-pointer duplicate removal method?

A Length of unique elements and modified array with unique elements at the front

B Sorted array with duplicates

C Array with duplicates removed and empty spaces removed

D Array reversed

The method returns the count of unique elements and the array modified so that unique elements are at the start.

If the input array is [1,1,2], what will be the array after removing duplicates using two pointers?

A [1,2,2]

B [1,1,2]

C [2,1,_]

D [1,2,_]

The unique elements 1 and 2 are placed at the start; the third position is ignored.

What is the space complexity of the two-pointer approach for removing duplicates from a sorted array?

A O(n)

B O(1)

C O(log n)

D O(n^2)

The method uses constant extra space by modifying the array in place.

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

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

Describe the state of the array and pointers after processing the input [0,0,1,1,1,2,2,3,3,4] with the two-pointer method.

Visualize the array as you move pointers and place unique elements.

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 count the total number of duplicates in the array

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

Solution

1. Step 1: Understand the two pointer roles

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

2. Step 2: Explain in-place overwrite

   When a new unique element is found, it is placed at the first pointer's position, avoiding extra space.

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 help 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 syntax to initialize two pointers i and j for the two-pointer approach in Python?

easy

A. i = 1; j = 0

B. i = j = 0

C. i, j = 0, 1

D. i = 0; j = 0

Solution

1. Step 1: Identify pointer roles

   Pointer i starts at 0 (position for unique elements), j starts at 1 (scanning pointer).

2. Step 2: Match initialization

   Correct initialization is i, j = 0, 1 to start comparing adjacent elements.

3. Final Answer:

   i, j = 0, 1 -> Option C

4. Quick Check:

   Start pointers at 0 and 1 for two-pointer scan [OK]

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

Common Mistakes:

• Initializing both pointers at 0
• Swapping pointer start positions
• Using incorrect syntax for multiple assignments

3. What will be the output of the following code snippet?

nums = [1, 1, 2, 2, 3]
i = 0
for j in range(1, len(nums)):
    if nums[j] != nums[i]:
        i += 1
        nums[i] = nums[j]
print(nums[:i+1])

medium

A. [1, 1, 2, 3]

B. [1, 2, 3]

C. [1, 2, 2, 3]

D. [1, 1, 2, 2, 3]

Solution

1. Step 1: Trace the loop and pointer updates

   Initially, i=0, j scans from 1 to 4. When nums[j] != nums[i], i increments and nums[i] is updated.

2. Step 2: Track array changes

   After processing, nums becomes [1, 2, 3, 2, 3], but only first i+1=3 elements are unique.

3. Final Answer:

   [1, 2, 3] -> Option B

4. Quick Check:

   Unique elements extracted as [1, 2, 3] [OK]

Hint: Print slice up to i+1 for unique elements [OK]

Common Mistakes:

• Printing full array instead of slice
• Not updating i correctly
• Confusing pointer roles

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

nums = [1, 1, 2, 3, 3]
i = 0
for j in range(1, len(nums)):
    if nums[i] == nums[j]:
        i += 1
        nums[i] = nums[j]
print(nums[:i+1])

medium

A. The condition should check if nums[j] != nums[i]

B. The pointer i should start at 1 instead of 0

C. The loop should start from j = 0

D. The print statement should print the entire array

Solution

1. Step 1: Analyze the if condition

   The code increments i and updates nums[i] only when nums[i] == nums[j], which is incorrect for removing duplicates.

2. Step 2: Correct the condition

   It should increment i and update nums[i] when nums[j] != nums[i] to keep unique elements.

3. Final Answer:

   The condition should check if nums[j] != nums[i] -> Option A

4. Quick Check:

   Use != to detect new unique elements [OK]

Hint: Use != to find unique elements, not == [OK]

Common Mistakes:

• Using == instead of !=
• Starting pointers incorrectly
• Printing wrong slice of array

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 in-place?

hard

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

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

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

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

Solution

1. Step 1: Apply two-pointer logic on nums

   Start with i=0, j scans from 1 to end. Each time nums[j] != nums[i], increment i and set nums[i] = nums[j].

2. Step 2: Track unique elements placement

   Unique elements placed at start: 0,1,2,3,4. The array's first 5 elements become [0,1,2,3,4].

3. Final Answer:

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

4. Quick Check:

   Unique sorted elements remain at front [OK]

Hint: Unique elements stay at front after two-pointer overwrite [OK]

Common Mistakes:

• Assuming duplicates remain in front
• Not updating i correctly
• Confusing array slicing after operation