Remove Duplicates from Sorted Array Two Pointer in DSA C++ - 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 pointer to scan through the array to find new unique elements.

beginner

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

Because duplicates are adjacent in a sorted array, 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 number of elements in the array, because each element is visited at most once.

intermediate

How does the two-pointer method modify the original array when removing duplicates?

It overwrites duplicate elements by placing unique elements at the front, so the first part of the array contains only unique values.

What does the fast pointer do in the two-pointer approach for removing duplicates?

A Scans through the array to find unique elements

B Marks the position of the last unique element

C Deletes duplicate elements directly

D Sorts the array before processing

The fast pointer moves through the array to find unique elements while the slow pointer tracks the position to place them.

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

A Because the method only works on sorted arrays by definition

B Because sorting removes duplicates automatically

C Because the pointers need to jump randomly

D Because duplicates are grouped together, making it easy to detect them

Duplicates appear next to each other in a sorted array, so the method can detect and skip duplicates efficiently.

What is the final output of the two-pointer method after removing duplicates?

A The array sorted again

B The length of the unique elements and the array modified in-place with unique elements at the front

C The original array unchanged

D A new array with unique elements only

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

What happens when the fast pointer finds a duplicate element?

A It swaps the duplicate with the slow pointer element

B It resets the slow pointer

C It skips it and moves forward without changing the slow pointer

D It deletes the element from the array

When a duplicate is found, the fast pointer moves forward, but the slow pointer stays to keep the last unique element position.

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

A O(1) - constant extra space

B O(n) - linear extra space

C O(log n) - logarithmic extra space

D O(n^2) - quadratic extra space

The method modifies the array in-place and uses only a few variables, so extra space used is constant.

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

Think about how you track unique elements and overwrite duplicates.

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

Focus on time, space, and array properties.

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