Remove Duplicates from Sorted Array

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.

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.

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.

Worked example

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

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.

Check index 2

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

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

Check index 3

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

Duplicate found. Do nothing.

Check index 4

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

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

Check index 5

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

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

Check index 6

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

Duplicate found. Do nothing.

Final Result:

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

#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;
}

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int i = 0;
    for (int j = 1; j < arr.size(); j++) {
        if (arr[j] != arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

int main() {
    vector<int> arr = {1, 1, 2, 2, 3, 4, 4};
    int k = removeDuplicates(arr);
    cout << "After removing duplicates: ";
    for (int i = 0; i < k; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

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

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

public class RemoveDuplicates {
    public static int removeDuplicates(int[] arr) {
        if (arr.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < arr.length; j++) {
            if (arr[j] != arr[i]) {
                i++;
                arr[i] = arr[j];
            }
        }
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 4, 4};
        int k = removeDuplicates(arr);
        System.out.print("After removing duplicates: ");
        for (int i = 0; i < k; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

function removeDuplicates(arr) {
    if (arr.length === 0) return 0;
    let i = 0;
    for (let j = 1; j < arr.length; j++) {
        if (arr[j] !== arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

const arr = [1, 1, 2, 2, 3, 4, 4];
const k = removeDuplicates(arr);
console.log("After removing duplicates:", arr.slice(0, k));

package main

import (
    "fmt"
)

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

func main() {
    arr := []int{1, 1, 2, 2, 3, 4, 4}
    k := removeDuplicates(arr)
    fmt.Print("After removing duplicates: ")
    for i := 0; i < k; i++ {
        fmt.Print(arr[i], " ")
    }
}

fn remove_duplicates(arr: &mut Vec<i32>) -> usize {
    if arr.is_empty() {
        return 0;
    }
    let mut i = 0;
    for j in 1..arr.len() {
        if arr[j] != arr[i] {
            i += 1;
            arr[i] = arr[j];
        }
    }
    i + 1
}

fn main() {
    let mut arr = vec![1, 1, 2, 2, 3, 4, 4];
    let k = remove_duplicates(&mut arr);
    print!("After removing duplicates: ");
    for i in 0..k {
        print!("{} ", arr[i]);
    }
}

fun removeDuplicates(arr: IntArray): Int {
    if (arr.isEmpty()) return 0
    var i = 0
    for (j in 1 until arr.size) {
        if (arr[j] != arr[i]) {
            i++
            arr[i] = arr[j]
        }
    }
    return i + 1
}

fun main() {
    val arr = intArrayOf(1, 1, 2, 2, 3, 4, 4)
    val k = removeDuplicates(arr)
    print("After removing duplicates: ")
    for (i in 0 until k) {
        print("${arr[i]} ")
    }
}

func removeDuplicates(_ arr: inout [Int]) -> Int {
    if arr.isEmpty { return 0 }
    var i = 0
    for j in 1..<arr.count {
        if arr[j] != arr[i] {
            i += 1
            arr[i] = arr[j]
        }
    }
    return i + 1
}

var arr = [1, 1, 2, 2, 3, 4, 4]
let k = removeDuplicates(&arr)
print("After removing duplicates:", terminator: " ")
for i in 0..<k {
    print(arr[i], terminator: " ")
}

function removeDuplicates(arr: number[]): number {
    if (arr.length === 0) return 0;
    let i = 0;
    for (let j = 1; j < arr.length; j++) {
        if (arr[j] !== arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

const arr: number[] = [1, 1, 2, 2, 3, 4, 4];
const k: number = removeDuplicates(arr);
console.log("After removing duplicates:", arr.slice(0, k));

Time complexity

Space complexity

O(1)

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