Remove Duplicates from Sorted Array Two Pointer in DSA Typescript

Mental Model

Use two pointers to overwrite duplicates in a sorted array, keeping only unique elements at the front.

Analogy: Imagine sorting your books on a shelf and removing extra copies by sliding unique books forward to fill gaps left by duplicates.

Array: [1, 1, 2, 2, 3, 4, 4]
Pointers: i ↑ j ↑
Initially both at start, i marks last unique, j scans ahead.

Dry Run Walkthrough

Input: array: [1, 1, 2, 2, 3]

Goal: Remove duplicates so array starts with unique elements only, return new length

Step 1: Start with i=0 (first unique), j=1 scanning next element

[1 (i=0), 1 (j=1), 2, 2, 3]

Why: We compare j to i to find new unique elements

Step 2: Compare array[j]=1 with array[i]=1, same so skip j forward

[1 (i=0), 1, 2 (j=2), 2, 3]

Why: Duplicate found, do not move i, just advance j

Step 3: array[j]=2 differs from array[i]=1, increment i and copy 2 to i

[1, 2 (i=1), 2 (j=2), 2, 3]

Why: Found new unique, move i forward and update value

Step 4: j moves to 3, array[j]=2 equals array[i]=2, skip j

[1, 2 (i=1), 2, 2 (j=3), 3]

Why: Duplicate again, only advance j

Step 5: array[j]=3 differs from array[i]=2, increment i and copy 3 to i

[1, 2, 3 (i=2), 2, 3 (j=4)]

Why: New unique found, move i and update

Result:

[1, 2, 3] with length 3

Annotated Code

DSA Typescript

class Solution {
  removeDuplicates(nums: number[]): number {
    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
  }
}

// Driver code
const sol = new Solution()
const nums = [1, 1, 2, 2, 3]
const length = sol.removeDuplicates(nums)
let output = ''
for (let k = 0; k < length; k++) {
  output += nums[k] + (k < length - 1 ? ' -> ' : ' -> null')
}
console.log(output)

if (nums.length === 0) return 0

handle empty array edge case

for (let j = 1; j < nums.length; j++) {

scan array from second element to end

if (nums[j] !== nums[i]) {

check if current element differs from last unique

i++

move unique pointer forward to next position

nums[i] = nums[j]

overwrite position i with new unique element

return i + 1

return count of unique elements

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because we scan the array once with two pointers

Space: O(1) because we modify the array in place without extra space

vs Alternative: Naive approach uses extra space to store unique elements, increasing space to O(n)

Edge Cases

empty array

returns 0 immediately, no processing needed

DSA Typescript

if (nums.length === 0) return 0

array with all duplicates

returns length 1 with first element only

DSA Typescript

if (nums[j] !== nums[i]) {

array with no duplicates

returns original length, array unchanged

DSA Typescript

if (nums[j] !== nums[i]) {

When to Use This Pattern

When you see a sorted array and need to remove duplicates in place, use two pointers to overwrite duplicates efficiently.

Common Mistakes

Mistake: Incrementing the unique pointer i even when a duplicate is found
Fix: Only increment i when a new unique element is found (nums[j] !== nums[i])

Summary

Removes duplicates from a sorted array in place and returns the new length of unique elements.

Use when you want to keep only unique elements in a sorted array without extra space.

The key insight is to use two pointers: one to track unique elements and one to scan ahead.

Practice

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

easy

A. To sort the array before removing duplicates

B. To efficiently overwrite duplicates and keep unique elements in place

C. To create a new array with unique elements

D. To count the number of duplicates without modifying the array

Solution

1. Step 1: Understand the two-pointer technique

   The two-pointer method uses one pointer to track the position of unique elements and another to scan through the array.

2. Step 2: Purpose of the technique in this context

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

3. Final Answer:

   To efficiently overwrite duplicates and keep unique elements in place -> Option B

4. Quick Check:

   Two-pointer removes duplicates in-place = B [OK]

Hint: Two pointers help overwrite duplicates without extra space [OK]

Common Mistakes:

• Thinking it sorts the array
• Assuming it creates a new array
• Confusing counting duplicates with removing

2. Which of the following TypeScript code snippets correctly initializes the two pointers for removing duplicates from a sorted array nums?

easy

A. let i = 0, j = 1;

B. let i = 1, j = 0;

C. let i = 0, j = 0;

D. let i = 1, j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i tracks the last unique element index, starting at 0. Pointer j scans ahead, starting at 1.

2. Step 2: Match initialization with roles

   Initializing i = 0 and j = 1 correctly sets the pointers for comparison.

3. Final Answer:

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

4. Quick Check:

   Start i=0, j=1 for two-pointer [OK]

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

Common Mistakes:

• Starting both pointers at 0
• Swapping pointer initial values
• Starting both pointers at 1

3. What will be the output array after running the two-pointer duplicate removal 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: Trace the two-pointer process

   Start with i=0 (value 1), j=1 (value 1). Since nums[j] == nums[i], skip j. Move j to 2 (value 2), nums[j] != nums[i], increment i to 1 and set nums[i]=2. Repeat for j=3 (2) and j=4 (3), updating nums accordingly.

2. Step 2: Final array state

   After processing, first three elements are [1, 2, 3]. The rest are ignored as duplicates.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

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

Hint: Keep unique elements at front, ignore duplicates [OK]

Common Mistakes:

• Not updating i pointer correctly
• Leaving duplicates in place
• Confusing order of elements

4. Identify the bug in this TypeScript code snippet for removing duplicates from a sorted array nums:

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. Using strict inequality instead of loose inequality

B. Missing check for empty array

C. Incorrectly updating pointer i to j instead of i + 1

D. Returning i instead of i + 1

Solution

1. Step 1: Analyze pointer update logic

   Pointer i should move forward by one to place unique elements, but here it is set to j, which can skip positions.

2. Step 2: Correct pointer update

   Instead of i = j;, it should be i++; to maintain continuous unique elements at the front.

3. Final Answer:

   Incorrectly updating pointer i to j instead of i + 1 -> Option C

4. Quick Check:

   i must increment by 1, not jump to j [OK]

Hint: Increment i by 1, don't assign it to j [OK]

Common Mistakes:

• Assigning i = j causes gaps
• Ignoring empty array edge case
• Returning wrong length

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 = 10, Array unchanged

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

C. Length = 4, Array = [0, 1, 2, 3]

D. Length = 5, Array = [0, 1, 2, 3, 4]

Solution

1. Step 1: Apply two-pointer method to the array

   Start with i=0 at 0. Move j through array, placing unique elements at i+1 positions: 1, 2, 3, 4.

2. Step 2: Count unique elements and array state

   Unique elements are 0,1,2,3,4 making length 5. The first five elements become [0,1,2,3,4].

3. Final Answer:

   Length = 5, Array = [0, 1, 2, 3, 4] -> Option D

4. Quick Check:

   Unique count 5, array front shows unique values [OK]

Hint: Count unique values, overwrite front, length = unique count [OK]

Common Mistakes:

• Counting duplicates as unique
• Not updating array elements correctly
• Assuming array length stays same