Remove Duplicates from Sorted Array Two Pointer in DSA Javascript - Deep Dive

Overview - Remove Duplicates from Sorted Array Two Pointer

What is it?

Removing duplicates from a sorted array means taking an array where numbers are in order and making sure each number appears only once. The two-pointer technique uses two markers to scan and update the array efficiently without extra space. This method changes the array in place and returns the new length without duplicates. It helps keep data clean and easy to use.

Why it matters

Without removing duplicates, data can be confusing and slow to process because repeated values add noise and waste space. This technique solves the problem quickly and uses no extra memory, which is important for big data or limited devices. It makes programs faster and more reliable when working with sorted lists.

Where it fits

Before learning this, you should understand arrays and basic loops. After this, you can learn more about two-pointer techniques, sliding windows, and other array manipulation methods.

Mental Model

Core Idea

Use two pointers to track unique elements and overwrite duplicates in a sorted array, keeping only one copy of each number.

Think of it like...

Imagine walking through a line of people sorted by height, and you want to keep only one person of each height. One hand points to the last unique person you kept, and the other hand scans ahead to find the next new height to keep.

Sorted Array: [1, 1, 2, 3, 3, 4]

Pointers:
  i (slow) -> tracks last unique element
  j (fast) -> scans ahead

Process:
Start: i=0, j=1

[1, 1, 2, 3, 3, 4]
 i ^  j ^

If nums[j] != nums[i], move i forward and copy nums[j] to nums[i]

Result after processing:
[1, 2, 3, 4, _, _]
 i points to last unique index

Return i+1 as new length

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why duplicates appear next to each other.

A sorted array is a list of numbers arranged from smallest to largest. Because it's sorted, any duplicates will be next to each other. For example, [1, 1, 2, 3, 3] has duplicates '1' and '3' right next to each other.

Result

Knowing duplicates are adjacent helps us remove them efficiently.

Understanding that duplicates are neighbors in a sorted array allows us to check only nearby elements instead of the whole array.

2

Foundation

Basic Array Traversal

Concept: Learn how to loop through an array and compare elements.

We use a loop to go through each element in the array. For example, for(let i = 0; i < nums.length; i++) { console.log(nums[i]); } prints each number. Comparing nums[i] and nums[i+1] helps find duplicates.

Result

You can identify duplicates by comparing neighbors.

Knowing how to traverse arrays and compare neighbors is the base for removing duplicates.

3

Intermediate

Two Pointer Technique Introduction

Concept: Use two pointers to track unique elements and scan ahead.

We use two pointers: 'i' to mark the position of the last unique element, and 'j' to scan through the array. When nums[j] is different from nums[i], we move i forward and copy nums[j] there. This way, unique elements are collected at the start.

Result

Duplicates are overwritten, and unique elements are compacted at the front.

Using two pointers avoids extra space and keeps the array updated in place.

4

Intermediate

Implementing Two Pointer in JavaScript

🤔Before reading on: do you think the slow pointer 'i' should start at 0 or 1? Commit to your answer.

Concept: Write code that uses two pointers to remove duplicates and returns the new length.

function removeDuplicates(nums) { if (nums.length === 0) return 0; let i = 0; for (let j = 1; j < nums.length; j++) { if (nums[j] !== nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; } // Example: // Input: [1,1,2,3,3] // Output length: 3 // Modified array start: [1,2,3,...]

Result

The function returns 3 and modifies the array to [1,2,3,3,3], but only first 3 elements matter.

Knowing where to start the slow pointer is key to correctly overwriting duplicates.

5

Intermediate

Dry Run with Example Array

🤔Before reading on: predict the array state after processing [0,0,1,1,2]. Commit to your answer.

Concept: Step through the algorithm with a sample array to see how pointers move and array changes.

Array: [0,0,1,1,2] Start: i=0, j=1 - nums[j]=0 equals nums[i]=0, skip - j=2, nums[j]=1 != nums[i]=0, i=1, nums[i]=1 - j=3, nums[j]=1 equals nums[i]=1, skip - j=4, nums[j]=2 != nums[i]=1, i=2, nums[i]=2 Result length = i+1 = 3 Modified array start: [0,1,2,1,2]

Result

New length is 3, unique elements are [0,1,2] at the start.

Dry running clarifies how duplicates are skipped and unique values are collected.

6

Advanced

Handling Edge Cases and Empty Arrays

🤔Before reading on: what should the function return for an empty array? Commit to your answer.

Concept: Consider what happens if the array is empty or has one element.

If the array is empty, return 0 because there are no elements. If it has one element, return 1 because it's unique by default. The code handles this by checking length at the start.

Result

Function returns 0 for [] and 1 for [5].

Handling edge cases prevents errors and ensures the function works for all inputs.

7

Expert

Why In-Place Modification Matters

🤔Before reading on: do you think creating a new array is better or worse than modifying in place? Commit to your answer.

Concept: Understand the memory and performance benefits of modifying the array without extra space.

Creating a new array uses extra memory and time to copy elements. Modifying in place saves memory and is faster, especially for large arrays. This is important in systems with limited resources or real-time constraints.

Result

In-place modification reduces memory usage and improves speed.

Knowing the tradeoff between space and time helps write efficient code for real-world applications.

Under the Hood

The two-pointer method works by maintaining a slow pointer 'i' that marks the position of the last unique element found. The fast pointer 'j' scans through the array. When nums[j] differs from nums[i], it means a new unique element is found, so 'i' is incremented and nums[j] is copied to nums[i]. This overwrites duplicates and compacts unique elements at the front. The rest of the array beyond 'i' remains unchanged but is ignored.

Why designed this way?

This approach was designed to optimize space by avoiding extra arrays and to leverage the sorted property so duplicates are adjacent. Alternatives like using sets or extra arrays use more memory and time. The in-place two-pointer method balances simplicity, speed, and memory efficiency.

Array: [1,1,2,3,3,4]

Start:
 i=0 (points to 1)
 j=1 (points to 1)

Loop:
 j moves forward
 If nums[j] != nums[i], i++ and nums[i]=nums[j]

Result:
 [1,2,3,4,3,4]
 i=3 (last unique index)

Return i+1 = 4

Myth Busters - 3 Common Misconceptions

Quick: Does the two-pointer method require extra memory to store unique elements? Commit yes or no.

Common Belief: You need extra space like a new array or set to remove duplicates.

Reality: The two-pointer method removes duplicates in place without extra memory beyond variables for pointers.

Why it matters: Using extra memory can be costly for large data and slow down programs unnecessarily.

Quick: Does this method work correctly on unsorted arrays? Commit yes or no.

Common Belief: The two-pointer method works on any array, sorted or not.

Reality: It only works correctly on sorted arrays because duplicates must be adjacent to detect them by comparing neighbors.

Why it matters: Using it on unsorted arrays leads to incorrect results and missed duplicates.

Quick: After removing duplicates, is the entire array guaranteed to be sorted? Commit yes or no.

Common Belief: The array remains fully sorted after removing duplicates.

Reality: Only the first part up to the returned length is guaranteed sorted and unique; the rest of the array beyond that length is unchanged and may contain old values.

Why it matters: Assuming the whole array is clean can cause bugs if you use elements beyond the new length.

Expert Zone

1

The slow pointer 'i' always points to the last unique element, not just any unique element, which is crucial for correct overwriting.

2

The method relies heavily on the array being sorted; if sorting is expensive, it may be better to use a hash set for unsorted data.

3

The leftover elements beyond the new length are not cleared or removed; they remain in memory but should be ignored.

When NOT to use

Do not use this method if the array is unsorted or if you need to preserve the original array order without modification. Alternatives include using hash sets for unsorted arrays or creating a new array to keep the original intact.

Production Patterns

This method is widely used in coding interviews and systems where memory is limited, such as embedded devices. It is also a building block for more complex algorithms that require unique sorted data, like merge operations or binary search optimizations.

Connections

Sliding Window Technique

Both use multiple pointers to scan and process arrays efficiently.

Understanding two pointers here helps grasp sliding windows, which also use pointers to track ranges and conditions.

Database Indexing

Removing duplicates is similar to how database indexes maintain unique keys for fast lookup.

Knowing how duplicates are removed in arrays helps understand how databases optimize queries by avoiding repeated keys.

Signal Processing - Noise Filtering

Removing duplicates is like filtering repeated noise signals to keep only unique signals.

This cross-domain link shows how cleaning data by removing repeats is a universal concept in many fields.

Common Pitfalls

#1 Starting the slow pointer at 1 instead of 0 causes skipping the first element.

Wrong approach:

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

Correct approach:

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

Root cause:

Misunderstanding that the slow pointer should start at the first element's index to track unique elements correctly.

#2 Using this method on an unsorted array leads to incorrect results.

Wrong approach:

function removeDuplicates(nums) {
let i = 0;
for (let j = 1; j < nums.length; j++) {
if (nums[j] !== nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
// Input: [3,1,2,3,1]
// Output incorrect

Correct approach:

// Sort first then remove duplicates
nums.sort((a,b) => a-b);
// Then apply removeDuplicates as above

Root cause:

Assuming the array is sorted when it is not, which breaks the logic of adjacent duplicates.

#3 Using the returned length but accessing elements beyond it causes bugs.

Wrong approach:

const length = removeDuplicates(nums);
for(let i = 0; i < nums.length; i++) {
console.log(nums[i]);
}

Correct approach:

const length = removeDuplicates(nums);
for(let i = 0; i < length; i++) {
console.log(nums[i]);
}

Root cause:

Not using the new length returned by the function to limit access to unique elements.

Key Takeaways

Removing duplicates from a sorted array can be done efficiently using two pointers without extra memory.

The slow pointer tracks the last unique element, while the fast pointer scans ahead for new unique values.

This method only works correctly on sorted arrays because duplicates are adjacent.

Always use the returned new length to access the unique elements and ignore the rest of the array.

Handling edge cases like empty arrays and single-element arrays ensures robust code.

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