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

Overview - Remove Duplicates from Sorted Array Two Pointer

What is it?

Removing duplicates from a sorted array means changing the array so that each number appears only once, without changing the order. The two-pointer technique uses two indexes to scan and update the array efficiently. One pointer reads through the array, and the other writes unique values. This method changes the array in place without extra space.

Why it matters

Without removing duplicates, data can be redundant and waste space or cause errors in programs. This technique helps keep data clean and efficient, especially when working with large sorted lists. Without it, programs might run slower or use more memory, making them less practical.

Where it fits

Before learning this, you should understand arrays and basic loops. After this, you can learn about more complex array problems, like merging sorted arrays or using two pointers for other tasks like finding pairs or triplets.

Mental Model

Core Idea

Use one pointer to read each element and another to write only unique elements, skipping duplicates as you go.

Think of it like...

Imagine you are sorting through a line of identical books on a shelf. You pick up each book (read pointer) and only place a new book on a separate shelf (write pointer) if it's different from the last one you placed.

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

Pointers:
Read -> moves through every element
Write -> moves only when a new unique element is found

Process:
[1, 1, 2, 2, 3, 4, 4]
 ^R  ^W

After first unique found:
[1, 2, 2, 2, 3, 4, 4]
    ^R  ^W

Final unique array:
[1, 2, 3, 4, _, _, _]

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why duplicates appear consecutively.

A sorted array is a list where numbers are arranged from smallest to largest. Because it is sorted, any duplicates will be next to each other. For example, in [1, 1, 2, 3, 3], the duplicates 1 and 3 appear side by side.

Result

You know that duplicates are always neighbors in a sorted array.

Understanding that duplicates are consecutive allows us to check only neighbors instead of the whole array.

2

Foundation

Basic Array Traversal

Concept: Learn how to move through an array using a loop.

To look at every element in an array, we use a loop that starts at the first element and moves to the last. For example, for (int i = 0; i < array.length; i++) { // access array[i] } visits each element one by one.

Result

You can visit and check every element in an array.

Knowing how to traverse arrays is essential before modifying or checking elements.

3

Intermediate

Two Pointer Technique Introduction

Concept: Use two pointers to read and write in the array simultaneously.

We use two indexes: one (read) moves through every element, the other (write) marks where to place the next unique element. Initially, write starts at 0, read at 1. When read finds a new number, write moves forward and updates the array.

Result

You can separate unique elements at the start of the array while scanning it once.

Using two pointers reduces the need for extra space and multiple passes.

4

Intermediate

Implementing Duplicate Removal Logic

🤔Before reading on: do you think the write pointer moves only when a new unique element is found, or every time the read pointer moves? Commit to your answer.

Concept: Move the write pointer only when a new unique element is found by comparing current and previous elements.

Start write at 0. For each read from 1 to end, compare array[read] with array[write]. If different, increment write and copy array[read] to array[write]. This skips duplicates.

Result

The array's first part contains only unique elements, and duplicates are overwritten.

Knowing when to move the write pointer avoids unnecessary overwrites and keeps unique elements compact.

5

Intermediate

Returning the New Length

🤔Before reading on: do you think the new length is the write pointer's position or write pointer plus one? Commit to your answer.

Concept: The new length of the array without duplicates is write pointer index plus one.

Since write points to the last unique element's index, the count of unique elements is write + 1. This length tells how many elements to consider in the modified array.

Result

You get the correct size of the array after duplicates are removed.

Understanding the length helps use the array correctly after modification.

6

Advanced

In-Place Modification Without Extra Space

🤔Before reading on: do you think this method requires extra memory proportional to the array size? Commit to your answer.

Concept: The two-pointer method modifies the array in place, using only constant extra space.

Instead of creating a new array, the write pointer overwrites duplicates in the original array. This saves memory and is efficient for large data.

Result

Duplicates are removed without using extra arrays or lists.

Knowing in-place modification is key for memory-efficient algorithms.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think this method works correctly if the array is empty or has one element? Commit to your answer.

Concept: The method handles empty arrays and single-element arrays gracefully and runs in linear time.

If the array is empty, return 0 immediately. If one element, return 1. The algorithm only scans once, so time complexity is O(n).

Result

The method is robust and efficient for all valid inputs.

Understanding edge cases and performance ensures reliable and fast code in real applications.

Under the Hood

The two-pointer technique uses one pointer to scan each element (read pointer) and another pointer to track the position to write unique elements (write pointer). When the read pointer finds a new unique element different from the last written, the write pointer moves forward and updates the array. This avoids extra memory allocation by overwriting duplicates in place.

Why designed this way?

This method was designed to optimize space and time. Earlier approaches used extra arrays or nested loops, which increased memory use or slowed down the process. The two-pointer approach leverages the sorted property to detect duplicates in one pass, making it efficient and simple.

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

Initial:
Read -> index 1
Write -> index 0

Step 1:
Compare array[1] and array[0]: both 1, duplicate, no write move

Step 2:
Read -> index 2, array[2] = 2 != array[0] = 1
Write -> index 1, array[1] = 2

Step 3:
Read -> index 3, array[3] = 3 != array[1] = 2
Write -> index 2, array[2] = 3

Step 4:
Read -> index 4, array[4] = 3 == array[2] = 3, duplicate

Step 5:
Read -> index 5, array[5] = 4 != array[2] = 3
Write -> index 3, array[3] = 4

Final array:
[1, 2, 3, 4, _, _]

Myth Busters - 4 Common Misconceptions

Quick: Does this method require sorting the array first? Commit to yes or no.

Common Belief: You can remove duplicates from any array using this two-pointer method without sorting.

Reality: This method only works correctly if the array is already sorted, because it relies on duplicates being adjacent.

Why it matters: Using this method on unsorted arrays can miss duplicates, leading to incorrect results and bugs.

Quick: Is the new length always equal to the original array length? Commit to yes or no.

Common Belief: The length of the array does not change after removing duplicates; only the content changes.

Reality: The length decreases because duplicates are removed; the method returns the new length to indicate this.

Why it matters: Ignoring the new length can cause processing of invalid or duplicate data beyond the unique elements.

Quick: Does the write pointer move every time the read pointer moves? Commit to yes or no.

Common Belief: The write pointer moves forward with every read pointer step.

Reality: The write pointer only moves when a new unique element is found, not every step.

Why it matters: Moving the write pointer incorrectly can overwrite unique elements or leave duplicates in place.

Quick: Can this method handle empty arrays without errors? Commit to yes or no.

Common Belief: The method will fail or throw an error if the array is empty.

Reality: The method handles empty arrays by returning zero immediately, avoiding errors.

Why it matters: Not handling empty arrays causes crashes or unexpected behavior in programs.

Expert Zone

1

The write pointer's position always points to the last unique element, which helps in calculating the new length precisely.

2

This method can be adapted for removing duplicates from sorted linked lists by adjusting pointers, showing its versatility.

3

In concurrent or multi-threaded environments, in-place modification requires careful synchronization to avoid race conditions.

When NOT to use

Do not use this method if the array is unsorted; instead, use a hash set or sorting first. Also, if you need to preserve the original array, use extra space to create a new array with unique elements.

Production Patterns

This technique is widely used in database query optimization, data cleaning pipelines, and real-time systems where memory and speed are critical. It is also a common interview question to test understanding of array manipulation and pointer techniques.

Connections

Sliding Window Technique

Both use multiple pointers to scan arrays efficiently.

Understanding two pointers here helps grasp sliding window methods used for subarray problems.

Linked List Deduplication

The logic of skipping duplicates applies similarly to linked lists with pointers.

Knowing array two-pointer deduplication makes linked list deduplication easier to understand.

Data Compression

Removing duplicates is a form of data reduction, similar to compression techniques.

Recognizing duplicate removal as data reduction connects algorithmic thinking to storage optimization.

Common Pitfalls

#1 Not checking if the array is empty before processing.

Wrong approach:

int removeDuplicates(int[] nums) {
int write = 0;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write]) {
write++;
nums[write] = nums[read];
}
}
return write + 1;
}

Correct approach:

int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int write = 0;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write]) {
write++;
nums[write] = nums[read];
}
}
return write + 1;
}

Root cause:

Assuming the array always has elements leads to errors when it is empty.

#2 Moving the write pointer every time the read pointer moves.

Wrong approach:

int removeDuplicates(int[] nums) {
int write = 0;
for (int read = 1; read < nums.length; read++) {
write++;
nums[write] = nums[read];
}
return write + 1;
}

Correct approach:

int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int write = 0;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write]) {
write++;
nums[write] = nums[read];
}
}
return write + 1;
}

Root cause:

Misunderstanding that write pointer should only move on unique elements.

#3 Using this method on unsorted arrays.

Wrong approach:

int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int write = 0;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write]) {
write++;
nums[write] = nums[read];
}
}
return write + 1;
}
// Called with unsorted array like [3,1,2,3]

Correct approach:

// Sort first
Arrays.sort(nums);
// Then apply removeDuplicates method

Root cause:

Not recognizing the requirement that the array must be sorted for this method.

Key Takeaways

Removing duplicates from a sorted array can be done efficiently using two pointers: one to read and one to write unique elements.

The array must be sorted so duplicates appear consecutively, allowing simple neighbor comparison.

The write pointer only moves when a new unique element is found, ensuring in-place modification without extra space.

Always handle edge cases like empty or single-element arrays to avoid errors.

This technique is a foundation for many array problems and is widely used in real-world applications for efficient data processing.

Practice

1. What is the main purpose of using two pointers in the Remove Duplicates from Sorted Array problem?

easy

A. To sort the array before removing duplicates

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

C. To create a new array with unique elements

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

Solution

1. Step 1: Understand the two-pointer approach

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

2. Step 2: Purpose of pointers in-place

   This method avoids extra space by overwriting duplicates, keeping unique elements at the start.

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 move to keep unique elements compact [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 the two pointers i and j for the problem in Java?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

C. int i = 0; int j = 0;

D. int i = 1; int j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i starts at 0 to track unique elements, j starts at 1 to scan ahead.

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 allows scanning from second element while i marks last unique.

3. Final Answer:

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

4. Quick Check:

   Start i at 0, j at 1 to scan array [OK]

Hint: Start i at 0 and 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 length after removing duplicates using two pointers on the sorted array [1, 1, 2, 2, 3]?

medium

A. 2

B. 3

C. 5

D. 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1; compare elements and overwrite duplicates: unique elements are 1, 2, 3.

2. Step 2: Count unique elements

   After processing, unique elements count is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Count unique elements after skipping duplicates [OK]

Common Mistakes:

• Counting duplicates instead of unique
• Assuming length stays same
• Miscounting when duplicates are consecutive

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

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

medium

A. Pointers initialized incorrectly

B. Incorrect comparison operator used

C. Returns i instead of i + 1 as new length

D. Does not increment j inside the loop

Solution

1. Step 1: Analyze return value

   The variable i tracks last unique index, so length is i + 1.

2. Step 2: Identify mistake in return

   Returning i misses counting the first element, causing length off by one.

3. Final Answer:

   Returns i instead of i + 1 as new length -> Option C

4. Quick Check:

   Length = last index + 1 [OK]

Hint: Return i + 1 for length, not i [OK]

Common Mistakes:

• Returning i instead of i + 1
• Forgetting to increment j
• Using wrong comparison operator

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?

hard

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

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

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

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

Solution

1. Step 1: Apply two-pointer overwrite

   Start with i=0, j=1; overwrite duplicates by moving unique elements forward: unique elements are 0,1,2,3,4.

2. Step 2: Final array state

   First five positions hold unique elements [0,1,2,3,4], rest remain unchanged or ignored.

3. Final Answer:

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

4. Quick Check:

   Unique elements compacted at start [OK]

Hint: Unique elements fill front, duplicates ignored after [OK]

Common Mistakes:

• Assuming duplicates remain in place
• Misplacing unique elements
• Counting extra elements beyond unique count