Remove Duplicates from Sorted Array using Two Pointers - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpaceDetailed Ex

Visualization Player

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

Solution❯

Understanding the Problem

We are given a sorted array, and we need to remove duplicate elements in-place, meaning without using extra space. After removing the duplicates, we should return the count of unique elements. The key point to note is that the array is already sorted, so any duplicate elements will be next to each other.

Example to Understand the Problem

Let’s consider this example:

Input: [1, 1, 2, 3, 3]

Expected Output: Length = 3, Modified Array = [1, 2, 3]

This means we have to keep only one occurrence of each number, maintaining the original order, and return how many unique numbers are now present at the start of the array.

Step-by-Step Solution

To solve this, we will use a two-pointer technique:

  • i – This pointer will track the last position of the unique element found.
  • j – This pointer will move through the array to find the next unique value.

We start by assuming the first element is unique, so we place i at index 0 and j at index 1. As j moves forward:

  • If arr[j] != arr[i], we have found a new unique number.
  • We increment i and copy arr[j] to arr[i].
  • This keeps all the unique elements grouped at the start of the array.

Applying the Steps to the Example

Original: [1, 1, 2, 3, 3]
i = 0, j = 1 → arr[j] == arr[i] → skip
j = 2 → arr[2] != arr[0] → i++, arr[1] = arr[2] → [1, 2, 2, 3, 3]
j = 3 → arr[3] != arr[1] → i++, arr[2] = arr[3] → [1, 2, 3, 3, 3]
j = 4 → arr[4] == arr[2] → skip

Resulting array: [1, 2, 3, _, _] (We can ignore the remaining elements)

Return value: i + 1 = 3

Handling Edge Cases

  • Empty Array: No elements to process, return 0.
  • Single Element: Already unique, return 1.
  • All Duplicates: Only one unique value remains. For example, [5, 5, 5] → [5]
  • All Unique: No changes required. For example, [1, 2, 3] remains the same, and return original length.

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int removeDuplicates(int arr[], int n) {
    if (n == 0) return 0;
    int i = 0;
    for (int j = 1; j < n; j++) {
        if (arr[j] != arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

int main() {
    int arr[] = {1, 1, 2, 2, 3, 4, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = removeDuplicates(arr, n);
    printf("After removing duplicates: ");
    for (int i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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]


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...