Introduction

The Remove Duplicates from Sorted Array problem involves removing duplicate elements from a sorted array such that each unique element appears only once.

Given a sorted array arr[] of size n, the task is to remove duplicates in-place and return the number of unique elements.

This is a popular array problem that helps in understanding Two Pointer Technique, in-place array modification, and efficient traversal.

Example

Input: arr[] = [1, 1, 2, 2, 3, 4, 4]Output: [1, 2, 3, 4]
Unique Count = 4
Explanation:
Duplicate elements are removed.
Only unique elements remain in the array.

Input: arr[] = [5, 5, 5, 5]
Output: [5]
Unique Count = 1
Explanation:
All elements are duplicates except the first occurrence.

Constraints

     1 <= n <= 10^5 -10^9 <= arr[i] <= 10^9
Array is sorted in non-decreasing order

Approach 1 : Brute Force (Using Extra Array)

Explanation

The simplest way to solve this problem is:

  1. Create another array
  2. Traverse the original array
  3. Store only unique elements

Since the array is sorted, duplicates appear consecutively, making them easy to detect.

This approach is easy to understand but uses extra space.

Steps

  1. Create a new array.
  2. Insert the first element.
  3. Traverse the remaining array.
  4. If current element is different from previous element:
    • add it to result array
  5. Return the unique elements.

Dry Run

Input Array: [1, 1, 2, 2, 3, 4, 4]Insert first element:
Result = [1]
Traverse next 1:
Duplicate element
Skip it
Traverse 2:
Unique element
Insert 2
Result = [1, 2]
Traverse next 2:
Duplicate element
Skip it
Traverse 3:
Insert 3
Result = [1, 2, 3]
Traverse 4:
Insert 4
Result = [1, 2, 3, 4]
Final Result:
[1, 2, 3, 4]

Brute Force Code 

Complexity Analysis

Time Complexity: O(n)Explanation:
The array is traversed once.

Space Complexity: O(n)
Explanation:
An extra array is used to store unique elements.

Approach 2 : Optimized Solution (Two Pointer Technique)

Explanation

Instead of using another array, we can remove duplicates in-place using the Two Pointer Technique.

The idea is:

  1. One pointer tracks position for unique elements
  2. Another pointer traverses the array
  3. Whenever a new unique element is found:
    • place it at the correct position

This avoids extra space usage.

Steps

  1. Initialize pointer j=1.
  2. Traverse the array from index 1.
  3. Compare current element with previous unique element.
  4. If current element is unique:
    • place it at index j.
    • increment j
  5. First j elements become unique elements.

Dry Run

Input Array: [1, 1, 2, 2, 3, 4, 4]Initially:
j = 1
Traverse second 1:
Duplicate element
Skip it
Traverse 2:
Unique element found
Place 2 at index 1
Array becomes:
[1, 2, 2, 2, 3, 4, 4]
Increment j = 2
Traverse next 2:
Duplicate element
Skip it
Traverse 3:
Place 3 at index 2
Array becomes:
[1, 2, 3, 2, 3, 4, 4]
Increment j = 3
Traverse 4:
Place 4 at index 3
Final Unique Elements:
[1, 2, 3, 4]

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Every element is visited exactly once.


Space Complexity: O(n)
Explanation:
Only pointer variables are required.

Edge Cases

  1. Array contains all duplicates
  2. Array contains no duplicates
  3. Array contains only one element
  4. Array contains negative numbers

Why This Problem is Important

This problem helps in understanding:

  1. Two Pointer Technique
  2. In-place array modification
  3. Efficient traversal
  4. Duplicate handling
  5. Space optimization

It is one of the most important beginner-level array manipulation problems.

Real-World Applications

Duplicate removal is used in:

  1. Database systems
  2. Search engines
  3. Data cleaning systems
  4. Log processing
  5. Analytics pipelines

Common Mistakes

  1. Incorrect pointer movement
  2. Overwriting elements incorrectly
  3. Forgetting sorted array property
  4. Returning incorrect unique count

Interview Tips

Interviewers often expect:

  1. In-place modification
  2. O(n) traversal
  3. Proper Two Pointer usage

Always explain why sorted arrays make duplicate detection easier.

Related Questions

  1. Move Zeroes
  2. Remove Element
  3. Merge Sorted Arrays
  4. Sort Colors
  5. Rearrange Array

Final Takeaway

The Remove Duplicates from Sorted Array problem is a fundamental Two Pointer problem that teaches efficient in-place array modification and duplicate handling techniques. Understanding this problem builds a strong foundation for advanced array manipulation and optimization problems.