Remove Duplicates from Sorted Array using Two Pointers - Optimal Algorithm

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace Detailed Exmpl

Problem Statement❯

Given a sorted array of integers, your task is to remove the duplicate elements in-place such that each element appears only once. The relative order of the elements should be maintained.

  • You must perform this operation in-place with O(1) extra space.
  • After removing the duplicates, return the number of unique elements.
  • The first part of the array (up to that count) should hold the unique elements.

Examples❯

Input Array Returned Length Modified Array (first k elements) Description
[1, 1, 2] 2 [1, 2] 1 is repeated, only unique values retainedVisualization
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 5 [0, 1, 2, 3, 4] All duplicates removed, unique values in-placeVisualization
[1, 2, 3, 4] 4 [1, 2, 3, 4] No duplicates, array remains the sameVisualization
[1, 1, 1, 1] 1 [1] All elements are same, only one remainsVisualization
[5] 1 [5] Single element, no duplicates to removeVisualization
[] 0 [] Empty array, result is also emptyVisualization

Visualization Player

Solution❯

Since the input array is already sorted, any duplicates will appear next to each other. This makes it possible to remove duplicates by comparing each element with the previous one and only keeping the first occurrence of each value.

How It Works

We use a two-pointer approach to solve this efficiently in-place. One pointer (let’s call it i) will keep track of the position of the last unique element found. The other pointer (j) will move forward through the array, scanning for new unique elements.

Every time we find that arr[j] != arr[i], it means we’ve found a new value that hasn’t been seen yet. So we increment i and copy arr[j] into arr[i]. This way, all the unique elements are gathered at the beginning of the array in order.

What About Edge Cases?

  • Empty Array: If the input array has no elements, then there are no values to process, and the result is simply 0.
  • Single Element: An array with one value is already unique. So we return 1, and the array remains unchanged.
  • All Duplicates: For arrays like [2, 2, 2, 2], we keep only one '2', so the final length is 1.
  • All Unique: In a case like [1, 2, 3, 4], no changes are needed, and we return the original length.

Why This is Efficient

This method runs in O(n) time because we scan the array once. It also uses O(1) space since we don’t use any extra data structures—just the input array and two pointers. This makes it an optimal solution.

At the end, the array is modified so that the first k elements contain the unique values, and you can ignore the rest.

Algorithm Steps❯

  1. Given a sorted array arr.
  2. Use two pointers: i to track unique elements and j to iterate through the array.
  3. Start with i = 0 and j = 1.
  4. If arr[j] != arr[i], increment i and update arr[i] = arr[j].
  5. Continue this until j reaches the end of the array.
  6. The first i + 1 elements are the array with duplicates removed.

Code

Python
JavaScript
Java
C++
C
def remove_duplicates(arr):
    if not arr:
        return 0
    i = 0
    for j in range(1, len(arr)):
        if arr[j] != arr[i]:
            i += 1
            arr[i] = arr[j]
    return i + 1

# Sample Input
arr = [1, 1, 2, 2, 3, 4, 4]
k = remove_duplicates(arr)
print("After removing duplicates:", arr[:k])

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)Even if all elements are duplicates, the algorithm still iterates through the entire array once.
Average CaseO(n)Regardless of how many duplicates exist, each element is visited once using the two-pointer approach.
Worst CaseO(n)In the worst case where all elements are unique, the algorithm still makes a single pass through the array.

Space Complexity

O(1)

Explanation: The algorithm operates in-place and only uses two pointers to modify the array without allocating extra space.

Detailed Step by Step Example❯

Let's remove duplicates from the sorted array using the two-pointer technique.

{ "array": [1,1,2,2,3,4,4], "showIndices": true }

Initialize pointer i = 0 to track the last unique element. Start loop from j = 1.

Check index 1

Compare arr[1] = 1 with arr[0] = 1.

Duplicate found. Do nothing.

{ "array": [1,1,2,2,3,4,4], "showIndices": true, "highlightIndices": [0, 1], "labels": { "0": "i", "1": "j" } }

Check index 2

Compare arr[2] = 2 with arr[0] = 1.

Values are different. Increment i to 1 and set arr[1] = 2.

{ "array": [1,2,2,2,3,4,4], "showIndices": true, "highlightIndices": [1, 2], "labels": { "1": "i", "2": "j" } }

Check index 3

Compare arr[3] = 2 with arr[1] = 2.

Duplicate found. Do nothing.

{ "array": [1,2,2,2,3,4,4], "showIndices": true, "highlightIndices": [1, 3], "labels": { "1": "i", "3": "j" } }

Check index 4

Compare arr[4] = 3 with arr[1] = 2.

Values are different. Increment i to 2 and set arr[2] = 3.

{ "array": [1,2,3,2,3,4,4], "showIndices": true, "highlightIndices": [2, 4], "labels": { "2": "i", "4": "j" } }

Check index 5

Compare arr[5] = 4 with arr[2] = 3.

Values are different. Increment i to 3 and set arr[3] = 4.

{ "array": [1,2,3,4,3,4,4], "showIndices": true, "highlightIndices": [3, 5], "labels": { "3": "i", "5": "j" } }

Check index 6

Compare arr[6] = 4 with arr[3] = 4.

Duplicate found. Do nothing.

{ "array": [1,2,3,4,3,4,4], "showIndices": true, "highlightIndices": [3, 6], "labels": { "3": "i", "6": "j" } }

Final Result:

Array without duplicates (first i + 1 which is 4 elements): [1,2,3,4]