Remove Duplicates from Sorted Array Two Pointer in DSA C# - 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. Since the array is sorted, duplicates are next to each other. The two-pointer method uses two positions to scan and update the array without extra space. This way, we keep only unique numbers at the start of the array.

Why it matters

Without removing duplicates, data can be confusing or incorrect when you want unique values, like in lists of names or IDs. Doing this efficiently saves memory and time, especially for large data. Without this method, you might waste space or do extra work copying data, slowing down programs.

Where it fits

You should know what arrays are and how to loop through them. Understanding sorting helps because duplicates are next to each other. After this, you can learn about more complex data structures like linked lists or hash sets for handling duplicates differently.

Mental Model

Core Idea

Use two pointers to track unique values and overwrite duplicates in one pass through the sorted array.

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.

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

Pointers:
  i -> position of last unique number kept
  j -> current scanning position

Start:
 i=0 (points to first 1), j=1 (second 1)

Process:
 j moves forward, when nums[j] != nums[i], i++ and nums[i] = nums[j]

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

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: A sorted array has numbers in order, so duplicates are next to each other.

Look at an array like [1, 1, 2, 3, 3, 4]. Because it's sorted, all duplicates (like the two 1s or two 3s) are side by side. This makes it easier to find and remove duplicates by checking neighbors.

Result

Duplicates appear consecutively, making them easy to spot by comparing neighbors.

Knowing that duplicates are grouped together lets us scan the array once without jumping around.

2

Foundation

What Does Removing Duplicates Mean?

Concept: Removing duplicates means keeping only one copy of each number in the array.

If the array is [1, 1, 2, 3, 3, 4], after removing duplicates it becomes [1, 2, 3, 4]. The extra spaces at the end can be ignored or overwritten. The goal is to do this without creating a new array.

Result

The array starts with unique numbers only, duplicates removed.

Removing duplicates in-place saves memory and is efficient for large data.

3

Intermediate

Two Pointer Technique Introduction

Concept: Use two pointers to track unique elements and overwrite duplicates in one pass.

One pointer (i) marks the position of the last unique number found. The other pointer (j) scans the array from the start. When nums[j] is different from nums[i], move i forward and copy nums[j] there.

Result

Unique numbers are moved to the front of the array as i advances.

Using two pointers avoids extra space and multiple passes, making the process efficient.

4

Intermediate

Implementing Two Pointer in C#

🤔Before reading on: Do you think the first pointer should start at index 0 or 1? Commit to your answer.

Concept: Start the first pointer at index 0 and the second pointer at index 1 to compare neighbors.

Code example: int RemoveDuplicates(int[] nums) { if (nums.Length == 0) return 0; int i = 0; for (int j = 1; j < nums.Length; j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; } This code moves unique numbers to the front and returns the count of unique numbers.

Result

For input [1,1,2,3,3,4], output length is 4 and array starts as [1,2,3,4,...].

Starting i at 0 ensures the first element is always counted as unique, simplifying logic.

5

Intermediate

Dry Run Example with Two Pointers

🤔Before reading on: What will be the value of i and array after processing [1,1,2,3,3,4]? Predict the final array start.

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

Initial array: [1,1,2,3,3,4] - i=0, j=1: nums[1]=1 equals nums[0]=1, skip - j=2: nums[2]=2 != nums[0]=1, i=1, nums[1]=2 - j=3: nums[3]=3 != nums[1]=2, i=2, nums[2]=3 - j=4: nums[4]=3 equals nums[2]=3, skip - j=5: nums[5]=4 != nums[2]=3, i=3, nums[3]=4 Final array start: [1,2,3,4] Return value: i+1 = 4

Result

Unique count is 4, array starts with [1,2,3,4]

Walking through the process clarifies how duplicates are skipped and unique values collected.

6

Advanced

Handling Edge Cases and Empty Arrays

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

Concept: Consider arrays with zero or one element to avoid errors.

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 checks for empty arrays first to handle this safely.

Result

Empty array returns 0, single-element array returns 1 without errors.

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

7

Expert

Why Two Pointer Beats Other Methods

🤔Before reading on: Do you think using extra space is better or worse than two pointers here? Commit your answer.

Concept: Two pointer method uses O(1) extra space and O(n) time, better than copying or using sets.

Other methods like using a hash set require extra memory and may not keep order. Copying to a new array doubles memory use. Two pointers modify the array in place, scanning once, making it optimal for sorted arrays.

Result

Efficient in time and space, suitable for large data and memory-limited environments.

Understanding the efficiency trade-offs helps choose the best method for production code.

Under the Hood

The two-pointer method works by maintaining one pointer at the last unique element's position and another scanning ahead. When a new unique element is found, it is copied forward to the position after the last unique element. This overwrites duplicates in place without extra memory allocation. The array's sorted property guarantees duplicates are consecutive, so a single pass suffices.

Why designed this way?

This approach was designed to optimize space and time. Before, removing duplicates often required extra arrays or data structures, increasing memory use. Sorting arrays is common, so leveraging their order to remove duplicates in place was a natural, efficient solution. Alternatives like hash sets lose order or use extra space, so two pointers balance simplicity and performance.

Start:
 nums: [1, 1, 2, 3, 3, 4]
 i -> index of last unique
 j -> scanning index

Process:
 i=0, j=1
 Compare nums[j] and nums[i]
 If different:
  i++
  nums[i] = nums[j]

Flow:
 [1,1,2,3,3,4]
  i=0, j=1 (equal, skip)
  j=2 (2 != 1)
   i=1, nums[1]=2
  j=3 (3 != 2)
   i=2, nums[2]=3
  j=4 (3 == 3, skip)
  j=5 (4 != 3)
   i=3, nums[3]=4

Result:
 [1,2,3,4,3,4]
 Unique count = i+1 = 4

Myth Busters - 3 Common Misconceptions

Quick: Does this method work correctly if the array is not sorted? Commit yes or no.

Common Belief: This two-pointer method works on any array to remove duplicates.

Reality: It only works correctly if the array is sorted because duplicates must be consecutive to detect them by comparing neighbors.

Why it matters: Using this method on unsorted arrays can miss duplicates, leaving repeated values and incorrect results.

Quick: Does the method create a new array to store unique elements? Commit yes or no.

Common Belief: Removing duplicates requires creating a new array to hold unique values.

Reality: The two-pointer method modifies the original array in place without extra arrays, saving memory.

Why it matters: Believing extra arrays are needed can lead to inefficient code and higher memory use.

Quick: After removing duplicates, is the array length automatically reduced? Commit yes or no.

Common Belief: The array size shrinks automatically after duplicates are removed.

Reality: The array size stays the same; only the first part contains unique values. The rest remains but is ignored based on the returned count.

Why it matters: Expecting the array to shrink can cause bugs if code reads beyond the unique count.

Expert Zone

1

The returned length indicates how many unique elements are valid; the rest of the array beyond that length is undefined and should not be used.

2

This method assumes the array is mutable; immutable arrays or lists require different approaches or copying.

3

In languages with pointers or references, care must be taken to avoid aliasing issues when overwriting elements.

When NOT to use

Do not use this method if the array is unsorted or if you need to preserve the original array unchanged. Instead, use hash sets or sorting plus copying. Also avoid if the data structure is not an array but a linked list or tree, which require different techniques.

Production Patterns

This method is commonly used in coding interviews and systems where memory is limited. In databases or data pipelines, similar logic is applied to sorted streams to remove duplicates efficiently without extra storage.

Connections

Sliding Window

Both use multiple pointers to scan arrays efficiently.

Understanding two pointers here helps grasp sliding window techniques that also move pointers to solve problems in linear time.

Run-Length Encoding

Removing duplicates relates to compressing repeated values into counts.

Knowing how duplicates cluster in sorted arrays aids understanding how run-length encoding compresses data by counting repeats.

Data Deduplication in Storage Systems

Both remove repeated data to save space.

The concept of removing duplicates in arrays parallels how storage systems identify and eliminate repeated data blocks to optimize space.

Common Pitfalls

#1 Starting the first pointer at 1 instead of 0 causes missing the first element as unique.

Wrong approach:

int i = 1;
for (int j = 1; j < nums.Length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}

Correct approach:

int i = 0;
for (int j = 1; j < nums.Length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}

Root cause:

Misunderstanding that the first element is always unique and must be included from the start.

#2 Not checking for empty array causes runtime error.

Wrong approach:

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

Correct approach:

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

Root cause:

Ignoring edge cases like empty input leads to accessing invalid indexes.

#3 Using this method on unsorted arrays leads to incorrect results.

Wrong approach:

int RemoveDuplicates(int[] nums) {
if (nums.Length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.Length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
// Called with [3,1,2,3,1]

Correct approach:

// Sort the array first
Array.Sort(nums);
// Then call RemoveDuplicates as above

Root cause:

Assuming the array is sorted when it is not, breaking the logic of consecutive duplicates.

Key Takeaways

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

One pointer tracks the last unique element, while the other scans ahead to find new unique values.

The method requires the array to be sorted so duplicates are consecutive and easy to detect.

Edge cases like empty arrays must be handled to avoid errors.

This technique is widely used in interviews and production for its simplicity and efficiency.

Practice

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

easy

A. To create a new array with unique elements

B. To sort the array before removing duplicates

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

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

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 directly in the original array.

3. Final Answer:

   To efficiently track unique elements and overwrite duplicates in-place -> Option C

4. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers track and overwrite duplicates without extra space [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 C# syntax to initialize the two pointers i and j for the problem?

easy

A. int i = 1; int j = 1;

B. int i = 1, j = 0;

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

D. int i = 0, j = 1;

Solution

1. Step 1: Identify pointer roles

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

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 matches the logic of comparing current and next elements.

3. Final Answer:

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

4. Quick Check:

   Start i at 0 and j at 1 [OK]

Hint: Start i at 0 and j at 1 to compare adjacent elements [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 and new length after running the two-pointer method on the sorted array [1, 1, 2, 3, 3]?

medium

A. [1, 2, 3, 3], length = 4

B. [1, 2, 3], length = 3

C. [1, 1, 2, 3, 3], length = 5

D. [1, 2, 2, 3], length = 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1. Compare elements: skip duplicates, overwrite unique elements at i+1.

2. Step 2: Final array and length

   Unique elements are 1, 2, 3 placed at start. Length is 3.

3. Final Answer:

   [1, 2, 3], length = 3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Overwrite duplicates, count unique elements for length [OK]

Common Mistakes:

• Not updating length after removal
• Leaving duplicates in output
• Misplacing unique elements

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

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

medium

A. The function should return i + 1 instead of i

B. Pointers i and j should both start at 1

C. The while loop condition should be j <= nums.Length

D. The array should be sorted inside the function

Solution

1. Step 1: Understand pointer meaning

   Pointer i tracks last unique element index, so length is i + 1.

2. Step 2: Check return value

   Returning i alone misses counting the first element, so return i + 1.

3. Final Answer:

   The function should return i + 1 instead of i -> Option A

4. Quick Check:

   Return length as i + 1 [OK]

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

Common Mistakes:

• Returning i instead of i + 1
• Incorrect loop boundary causing out-of-range
• Sorting array inside function unnecessarily

5. Given a sorted array nums = [0,0,1,1,1,2,2,3,3,4], what will be the array state and returned length after applying the two-pointer duplicate removal method?

hard

A. [0, 1, 2, 3, 4], length = 5

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

C. [0, 1, 1, 2, 3, 4], length = 6

D. [0, 1, 2, 3, 3, 4], length = 6

Solution

1. Step 1: Apply two-pointer method step-by-step

   Start with i=0, j=1. Move j forward, overwrite duplicates by placing unique elements at i+1.

2. Step 2: Final array and length

   Unique elements are 0,1,2,3,4 placed at start. Length is 5.

3. Final Answer:

   [0, 1, 2, 3, 4], length = 5 -> Option A

4. Quick Check:

   Unique count = 5 [OK]

Hint: Overwrite duplicates, count unique elements for final length [OK]

Common Mistakes:

• Leaving duplicates in the array
• Returning wrong length
• Misplacing unique elements during overwrite