Introduction

Remove Duplicates from Sorted Array is one of the most common Array + Two Pointer interview questions.

It is frequently asked by:

• Google
• Amazon
• Microsoft
• Meta
• Apple
• Adobe
• Oracle
• Goldman Sachs

This problem evaluates your understanding of:

• Two Pointer Technique
• In-place array modification
• Sorted array optimization
• Time and Space complexity

Because the array is already sorted, duplicates appear together, allowing an efficient O(n) solution.

---

Problem Statement

Given a sorted integer array, remove duplicates in-place such that each unique element appears only once.

Return the number of unique elements (k).

Requirements

• Modify the original array.
• Use only constant extra space.
• Return the count of unique elements.

Example

Input

[1,1,2]

Output

2

Modified Array

[1,2,_]

---

Example 2

Input

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

Output

5

Modified Array

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

---

Brute Force Approach

Idea

Create another collection containing unique elements.

Then copy them back into the original array.

Illustration

Original Array

↓

HashSet

↓

Copy Back

Although easy to understand,

this violates the constant-space requirement.

---

Complexity

Complexity	Value
Time	O(n)
Space	O(n)

Not acceptable for this interview problem.

---

Optimal Approach — Two Pointers

Core Idea

Maintain two pointers.

• Read Pointer scans the array.
• Write Pointer stores the next unique element.

Whenever a new unique value is found,

copy it to the write position.

---

Algorithm

Sorted Array

↓

Read Pointer

↓

New Value?

↓

Copy

↓

Move Write Pointer

---

Dry Run

Input

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

Initial

write = 0

---

Read = 1

0 == 0

Ignore

---

Read = 2

1 != 0

↓

write++

↓

Copy 1

Array

0 1 1 1 1 2 2 3 3 4

---

Read = 5

2 != 1

↓

write++

↓

Copy 2

---

Continue

3

↓

4

Final Array

0 1 2 3 4

Return

5

---

Java Code

public class RemoveDuplicates {

    public 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;

    }

}

---

Complexity

Complexity	Value
Time	O(n)
Space	O(1)

This is the optimal solution.

---

Why Does This Work?

Since the array is sorted,

all duplicates appear together.

The algorithm only copies a value when it differs from the last unique value.

Illustration

Sorted Array

↓

Compare

↓

Different?

↓

Store

↓

Continue

Only one traversal is required.

---

Visual Explanation

Input

0 0 1 1 1 2 2 3 3 4

↓

Write Pointer

0

↓

Unique

↓

0 1

↓

Unique

↓

0 1 2

↓

Unique

↓

0 1 2 3

↓

Unique

↓

0 1 2 3 4

---

Edge Cases

Empty Array

[]

Output

0

---

Single Element

[5]

Output

1

---

All Duplicates

[2,2,2,2]

Output

1

---

No Duplicates

[1,2,3,4]

Output

4

---

Production Applications

This in-place deduplication technique is commonly used in:

• Customer master data cleanup
• ETL pipelines
• Financial transaction processing
• Inventory synchronization
• Data migration utilities
• Log compaction
• Event stream optimization
• Reporting systems

---

Common Interview Mistakes

❌ Using a HashSet.

❌ Creating another array.

❌ Forgetting that the array is already sorted.

❌ Returning the array instead of the count.

❌ Comparing with the previous read pointer instead of the last unique element.

---

Follow-Up Questions

What if the array is not sorted?

Sorting first would make the solution:

O(n log n)

Alternatively,

use a HashSet.

---

Can duplicates be allowed twice?

Yes.

This becomes LeetCode 80 – Remove Duplicates from Sorted Array II.

The logic changes slightly by allowing two occurrences before moving the write pointer.

---

Why is this considered an in-place algorithm?

Because it modifies the original array without allocating another collection.

Extra space remains:

O(1)

---

Interview Tips

Interviewers commonly ask:

• Why does sorting help?
• Why are Two Pointers used?
• Why return write + 1?
• Why not use a HashSet?
• What is the space complexity?
• Can this work on an unsorted array?
• How would you allow duplicates twice?
• Explain the dry run.

Always explain the pointer movement before writing code.

---

Summary

The Remove Duplicates from Sorted Array problem is a classic example of using the Two Pointer Technique to efficiently process sorted data. By maintaining separate read and write pointers, we can remove duplicates in-place with O(n) time and O(1) space while preserving the order of unique elements. This approach is widely applicable in enterprise systems that require efficient data cleansing and deduplication.

---

Key Takeaways

• Understand why sorting simplifies the problem.
• Use Two Pointers for in-place modification.
• Keep separate read and write pointers.
• Copy only unique elements.
• Return the count of unique values.
• Achieve O(n) time complexity.
• Use O(1) extra space.
• Avoid unnecessary data structures.
• Practice pointer movement through dry runs.
• Relate the solution to real-world data deduplication scenarios.

---