Remove Duplicates from Sorted Array Two Pointer in DSA Javascript - 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 explore the array. When a new unique element is found, move it next to the last unique element.

beginner

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

Because duplicates are adjacent in a sorted array, the method can compare neighbors easily and skip duplicates without extra space.

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.

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 happens if the input array is empty in the two-pointer duplicate removal method?

The method returns 0 immediately since there are no elements to process.

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

A Sorts the array

B Marks the last unique element's position

C Scans through the array to find unique elements

D Deletes duplicate elements directly

The 'fast' pointer moves through the array to find unique elements to place next to the 'slow' pointer.

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

A The original array unchanged

B A new array with unique elements

C The count of duplicates removed

D The length of the array with unique elements at the start

The method returns the length of unique elements, with those elements placed at the start of the original array.

Why is extra space not needed in the two-pointer approach for removing duplicates?

A Because the array is sorted and duplicates are adjacent

B Because the array is copied internally

C Because duplicates are removed by creating a new array

D Because the method uses recursion

Duplicates being adjacent in a sorted array allows in-place modification without extra space.

If the input array is [1,1,2], what will be the length returned after removing duplicates?

A 2

B 3

C 1

D 0

The unique elements are [1,2], so the length returned is 2.

What should be done when the 'fast' pointer finds a new unique element?

A Skip the element

B Move the 'slow' pointer forward and copy the element there

C Delete the element

D Reset both pointers

The 'slow' pointer moves forward and the new unique element is placed at its position.

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

Think about how to keep unique elements at the front.

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

Focus on time and space efficiency.

Practice

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

easy

A. To reverse the array while removing duplicates

B. To sort the array again after duplicates are removed

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

D. To efficiently overwrite duplicates and keep unique elements at the start

Solution

1. Step 1: Understand the two-pointer technique

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

2. Step 2: Purpose of the technique

   It overwrites duplicates by placing unique elements at the front, avoiding extra space.

3. Final Answer:

   To efficiently overwrite duplicates and keep unique elements at the start -> Option D

4. Quick Check:

   Two-pointer = overwrite duplicates [OK]

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

Common Mistakes:

• Thinking it sorts the array again
• Confusing counting duplicates with removing them
• Assuming it reverses the array

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

easy

A. let i = 1, j = 0;

B. let i = 0, j = 1;

C. let i = 0, j = 0;

D. let i = 1, j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i tracks last unique element index, j scans from next element.

2. Step 2: Correct initialization

   i starts at 0 (first element), j starts at 1 (second element) to compare.

3. Final Answer:

   let i = 0, j = 1; -> Option B

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 both pointers at 1

3. What will be the output array after removing duplicates using the two-pointer method on nums = [1, 1, 2, 2, 3]?

medium

A. [1, 2, 3]

B. [1, 1, 2, 3]

C. [1, 2, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Traverse and compare elements

   Start with i=0, j=1. Compare nums[j] with nums[i]. If different, increment i and copy nums[j].

2. Step 2: Update array with unique elements

   After processing, unique elements at start are [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Unique sorted elements = [1, 2, 3] [OK]

Hint: Unique elements stay at front in sorted order [OK]

Common Mistakes:

• Leaving duplicates in the output
• Mixing order of elements
• Not updating the array in place

4. Consider this code snippet for removing duplicates from a sorted array nums. What is the bug?

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

medium

A. Pointer i should be incremented, not assigned j

B. The loop should start from j = 0

C. The comparison should be nums[j] === nums[i]

D. Return statement should be i instead of i + 1

Solution

1. Step 1: Analyze pointer update

   i should move forward by incrementing to next unique position, not jump to j.

2. Step 2: Correct pointer increment

   Use i++ to move i forward, then assign nums[i] = nums[j].

3. Final Answer:

   Pointer i should be incremented, not assigned j -> Option A

4. Quick Check:

   i++ to move pointer forward [OK]

Hint: Increment i to place unique elements, don't assign j to i [OK]

Common Mistakes:

• Assigning i = j instead of i++
• Starting loop at wrong index
• Wrong comparison operator

5. Given a sorted array nums = [0,0,1,1,1,2,2,3,3,4], what will be the length of the array after removing duplicates using the two-pointer method, and what will the first part of the array look like?

hard

A. Length: 4, Array start: [0, 1, 2, 3]

B. Length: 6, Array start: [0, 1, 1, 2, 3, 4]

C. Length: 5, Array start: [0, 1, 2, 3, 4]

D. Length: 5, Array start: [0, 0, 1, 2, 3]

Solution

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

   Traverse array, move unique elements forward: 0,1,2,3,4.

2. Step 2: Count unique elements and array start

   There are 5 unique elements, so length is 5, and array start is [0,1,2,3,4].

3. Final Answer:

   Length: 5, Array start: [0, 1, 2, 3, 4] -> Option C

4. Quick Check:

   Unique count = 5, array front = [0,1,2,3,4] [OK]

Hint: Count unique elements, array front holds them [OK]

Common Mistakes:

• Counting duplicates as unique
• Not updating array in place
• Miscounting length after removal