Remove duplicates from Sorted Array
Last Updated :
30 May, 2024
Given a sorted array arr[] of size N, the task is to remove the duplicate elements from the array.
Examples:
Input: arr[] = {2, 2, 2, 2, 2}
Output: arr[] = {2}
Explanation: All the elements are 2, So only keep one instance of 2.
Input: arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
Output: arr[] = {1, 2, 3, 4, 5}
Naive Approach (Using extra space):
The idea to solve the problem is to
Create a new array and store the unique elements in the new array. For checking duplicate elements, just check two adjacent elements are equal or not because the array is sorted.
Follow the steps mentioned below to implement the idea:
- Create an auxiliary array temp[] to store unique elements.
- Traverse input array and one by one copy unique elements of arr[] to temp[].
- Also, keep track of the count of unique elements. Let this count be j.
- Copy j elements from temp[] to arr[] and return j.
Below is the implementation of the above approach.
C++
// C++ program to remove duplicates
#include <bits/stdc++.h>
using namespace std;
// Function to remove duplicate elements This function
// returns new size of modified array.
int removeDuplicates(int arr[], int n)
{
// Return, if array is empty or
// contains a single element
if (n == 0 || n == 1)
return n;
int temp[n];
// Start traversing elements
int j = 0;
// If current element is not equal to next element
// then store that current element
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
// Store the last element as whether it is unique or
// repeated, it hasn't stored previously
temp[j++] = arr[n - 1];
// Modify original array
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// removeDuplicates() returns new size of array.
n = removeDuplicates(arr, n);
// Print updated array
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
// C program to remove duplicates
#include <stdio.h>
// Function to remove duplicate elements This function
// returns new size of modified array.
int removeDuplicates(int arr[], int n)
{
// Return, if array is empty or
// contains a single element
if (n == 0 || n == 1)
return n;
int temp[n];
// Start traversing elements
int j = 0;
// If current element is not equal to next element
// then store that current element
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
// Store the last element as whether it is unique or
// repeated, it hasn't stored previously
temp[j++] = arr[n - 1];
// Modify original array
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// removeDuplicates() returns new size of array.
n = removeDuplicates(arr, n);
// Print updated array
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
// Java program to remove duplicates
class Main {
// Function to remove duplicate elements This function
// returns new size of modified array.
static int removeDuplicates(int arr[], int n)
{
// Return, if array is empty or
// contains a single element
if (n == 0 || n == 1)
return n;
int[] temp = new int[n];
// Start traversing elements
int j = 0;
for (int i = 0; i < n - 1; i++)
// If current element is not equal to next
// element then store that current element
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
// Store the last element as whether it is unique or
// repeated, it hasn't stored previously
temp[j++] = arr[n - 1];
// Modify original array
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
int n = arr.length;
// removeDuplicates() returns new size of array
n = removeDuplicates(arr, n);
// Print updated array
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
# Python3 program to
# remove duplicates
# Function to remove
# duplicate elements
# This function returns new size of modified array
def removeDuplicates(arr, n):
# Return, if array is empty or contains
# a single element
if n == 0 or n == 1:
return n
temp = list(range(n))
# Start traversing elements
j = 0
for i in range(0, n-1):
# If current element is not equal to next
# then store that current element
if arr[i] != arr[i+1]:
temp[j] = arr[i]
j += 1
# Store the last element as whether it is unique
# or repeated, it isn't stored previously
temp[j] = arr[n-1]
j += 1
# Modify original array
for i in range(0, j):
arr[i] = temp[i]
return j
# Driver code
if __name__ == '__main__':
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
n = len(arr)
# removeDuplicates() returns new size of array.
n = removeDuplicates(arr, n)
# Print updated array
for i in range(n):
print("%d" % (arr[i]), end=" ")
# This code is contributed by aadityaburukwale.
// Simple C# program to remove
// duplicates
using System;
class GFG {
// Function to remove duplicate
// elements This function returns
// new size of modified array.
static int removeDuplicates(int []arr, int n)
{
// Return, if array is empty
// or contains a single element
if (n == 0 || n == 1)
return n;
int []temp = new int[n];
// Start traversing elements
int j = 0;
for (int i = 0; i < n - 1; i++)
// If current element is not equal
// to next element then store that
// current element
if (arr[i] != arr[i+1])
temp[j++] = arr[i];
// Store the last element as
// whether it is unique or
// repeated, it hasn't
// stored previously
temp[j++] = arr[n-1];
// Modify original array
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
// Driver code
public static void Main ()
{
int []arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
int n = arr.Length;
n = removeDuplicates(arr, n);
// Print updated array
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by nitin mittal.
<script>
// Simple JavaScript program to remove
// duplicates
// Function to remove duplicate elements
// This function returns new size of modified
// array.
function removeDuplicates(arr, n)
{
// Return, if array is empty
// or contains a single element
if (n==0 || n==1)
return n;
var temp = new Array(n);
// Start traversing elements
var j = 0;
for (var i=0; i<n-1; i++)
// If current element is not equal
// to next element then store that
// current element
if (arr[i] != arr[i+1])
temp[j++] = arr[i];
// Store the last element as whether
// it is unique or repeated, it hasn't
// stored previously
temp[j++] = arr[n-1];
// Modify original array
for (var i=0; i<j; i++)
arr[i] = temp[i];
return j;
}
var arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];
var n = arr.length;
// removeDuplicates() returns new size of
// array.
n = removeDuplicates(arr, n);
// Print updated array
for (var i=0; i<n; i++)
document.write( arr[i]+" ");
// This code is contributed by SoumikMondal
</script>
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach using Set :
By using set to remove duplicates from an input array and update the array with unique elements and finally return the count of unique elements.
- Use set to collect unique elements from the array.
- Updates the array with unique elements, modifying the size.
- Prints the modified array, now containing only unique elements.
C++
#include <bits/stdc++.h>
using namespace std;
int removeDuplicates(int arr[], int n) {
if (n <= 1)
return n;
set<int> uniqueElements;
for (int i = 0; i < n; ++i) {
uniqueElements.insert(arr[i]);
}
int index = 0;
for (auto it = uniqueElements.begin(); it != uniqueElements.end(); ++it) {
arr[index++] = *it;
}
return uniqueElements.size();
}
int main() {
int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
int n = sizeof(arr) / sizeof(arr[0]);
n = removeDuplicates(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
import java.util.HashSet;
import java.util.Set;
public class RemoveDuplicates {
// Function to remove duplicates from the array and return the count of unique elements
static int removeDuplicates(int[] arr, int n) {
if (n <= 1)
return n;
// Use a Set to store unique elements
Set<Integer> uniqueElements = new HashSet<>();
// Traverse the array and add elements to the Set
for (int i = 0; i < n; ++i) {
uniqueElements.add(arr[i]);
}
int index = 0;
// Iterate through unique elements and update the original array
for (int element : uniqueElements) {
arr[index++] = element;
}
// Return the count of unique elements
return uniqueElements.size();
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
int n = arr.length;
// Remove duplicates and get the count of unique elements
n = removeDuplicates(arr, n);
// Print the modified array containing unique elements
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
def remove_duplicates(arr):
n = len(arr)
if n <= 1:
return n
# Use a set to store unique elements
unique_elements = set(arr)
# Update the original array with unique elements
arr[:n] = unique_elements
# Return the count of unique elements
return len(unique_elements)
# Driver code
if __name__ == "__main__":
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
# Remove duplicates and get the count of unique elements
n = remove_duplicates(arr)
# Print the modified array containing unique elements
for i in range(n):
print(arr[i], end=" ")
# This code is contributed by shivamgupta0987654321
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to remove duplicates from the array and
// return the count of unique elements
static int RemoveDuplicates(int[] arr, int n)
{
if (n <= 1)
return n;
// Use a HashSet to store unique elements
HashSet<int> uniqueElements = new HashSet<int>();
// Traverse the array and add elements to the
// HashSet
for (int i = 0; i < n; ++i) {
uniqueElements.Add(arr[i]);
}
int index = 0;
// Iterate through unique elements and update the
// original array
foreach(int element in uniqueElements)
{
arr[index++] = element;
}
// Return the count of unique elements
return uniqueElements.Count;
}
public static void Main()
{
int[] arr = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
int n = arr.Length;
// Remove duplicates and get the count of unique
// elements
n = RemoveDuplicates(arr, n);
// Print the modified array containing unique
// elements
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
// This code is contributed by Susobhan Akhuli
<script>
// Javascript program for the above approach
class RemoveDuplicates {
// Function to remove duplicates from the array and return the count of unique elements
static removeDuplicates(arr) {
const n = arr.length;
if (n <= 1)
return n;
// Use a Set to store unique elements
const uniqueElements = new Set(arr);
// Convert Set back to array
const uniqueArray = Array.from(uniqueElements);
// Update the original array with unique elements
for (let i = 0; i < uniqueArray.length; ++i) {
arr[i] = uniqueArray[i];
}
// Return the count of unique elements
return uniqueArray.length;
}
}
const arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];
// Remove duplicates and get the count of unique elements
const n = RemoveDuplicates.removeDuplicates(arr);
// Print the modified array containing unique elements
for (let i = 0; i < n; i++) {
document.write(arr[i]+" ");
}
// This code is contributed by Susobhan Akhuli
</script>
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach:
This problem can be solved efficiently just by maintaining a separate index for the same array as maintained for different array in the previous method and replacing that element with the unique element.
Follow the steps mentioned below to implement the idea:
- Traverse input array from i = 0 to N:
- Keep track of the count of unique elements. Let this count be j.
- Swap arr[j] with arr[i].
- At last, return j.
Below is the implementation of the above approach.
C++
// C++ program to remove duplicates in-place
#include<bits/stdc++.h>
using namespace std;
// Function to remove duplicate elements
// This function returns new size of modified array.
int removeDuplicates(int arr[], int n)
{
if (n==0 || n==1)
return n;
// To store index of next unique element
int j = 0;
// Doing same as done in Method 1
// Just maintaining another updated index i.e. j
for (int i=0; i < n-1; i++)
if (arr[i] != arr[i+1])
arr[j++] = arr[i];
arr[j++] = arr[n-1];
return j;
}
// Driver code
int main()
{
int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// removeDuplicates() returns new size of array.
n = removeDuplicates(arr, n);
// Print updated array
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
// Java program to remove duplicates
class Main
{
// Function to remove duplicate elements
// This function returns new size of modified
// array.
static int removeDuplicates(int arr[], int n)
{
if (n == 0 || n == 1)
return n;
// To store index of next unique element
int j = 0;
// Doing same as done in Method 1
// Just maintaining another updated index i.e. j
for (int i = 0; i < n-1; i++)
if (arr[i] != arr[i+1])
arr[j++] = arr[i];
arr[j++] = arr[n-1];
return j;
}
public static void main (String[] args)
{
int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
int n = arr.length;
n = removeDuplicates(arr, n);
// Print updated array
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
}
/* This code is contributed by Harsh Agarwal */
def remove_duplicates(arr):
n = len(arr)
if n == 0 or n == 1:
return n
# To store index of next unique element
j = 0
# Doing same as done in Method 1
# Just maintaining another updated index i.e. j
for i in range(n - 1):
if arr[i] != arr[i + 1]:
arr[j] = arr[i]
j += 1
arr[j] = arr[n - 1]
return j + 1
# Driver code
if __name__ == "__main__":
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
n = len(arr)
# remove_duplicates() returns new size of array.
n = remove_duplicates(arr)
# Print updated array
for i in range(n):
print(arr[i], end=" ")
// simple C# program to remove
// duplicates
using System;
class GfG {
// Function to remove duplicate
// elements This function returns
// new size of modified array.
static int removeDuplicates(int []arr, int n)
{
if (n == 0 || n == 1)
return n;
// To store index of next
// unique element
int j = 0;
// Doing same as done in Method 1
// Just maintaining another updated
// index i.e. j
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
arr[j++] = arr[i];
arr[j++] = arr[n - 1];
return j;
}
// Driver code
public static void Main ()
{
int []arr = {1, 2, 2, 3, 4, 4,
4, 5, 5};
int n = arr.Length;
n = removeDuplicates(arr, n);
// Print updated array
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by parashar.
<script>
// simple javascript program to remove
// duplicates
// Function to remove duplicate elements
// This function returns new size of modified
// array.
function removeDuplicates(arr , n) {
if (n == 0 || n == 1)
return n;
// To store index of next unique element
var j = 0;
// Doing same as done in Method 1
// Just maintaining another updated index i.e. j
for (i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
arr[j++] = arr[i];
arr[j++] = arr[n - 1];
return j;
}
var arr = [ 1, 2, 2, 3, 4, 4, 4, 5, 5 ];
var n = arr.length;
n = removeDuplicates(arr, n);
// Print updated array
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by umadevi9616
</script>
Time Complexity: O(N)
Auxiliary Space: O(1)
Fastest Efficient Approach: Using Binary Search
The problem requires us to remove duplicate elements from a sorted array, i.e., we need to keep only one copy of each element in the array. Since the array is sorted, all duplicate elements will be adjacent to each other, so we can easily remove them by shifting the subsequent elements of the array to the left.
We can use two pointers i and j, where i points to the last unique element found so far, and j points to the current element being examined. If nums[i] and nums[j] are equal, we just increment j. Otherwise, we increment i and copy nums[j] to nums[i]. At the end, we return i+1, which represents the length of the modified array.
We Would be using Binary Search to solve the particular problem in the fastest way.
Implementation of the above approach:
C++
// C++ program to remove duplicates in-place
#include<bits/stdc++.h>
using namespace std;
// Function to remove duplicate elements
// This function returns new size of modified array.
//Using Binarey Search to solve the particular problem efficiently
int binarySearch(vector<int> &nums, int low, int high, int val){
int n = nums.size();
int res = -1;
while(low<=high){
int mid = low + (high-low)/2;
//Check for lower limit
if(nums[mid] <= val) low = mid+1;
//check for higher limit
else{
//move to higher limit
res = mid;
high = mid-1;
}
}
//check if not found
if(res == -1) return n;
return res;
}
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
int idx = 0; // It store indexing of unique elements.
while(idx != n){
int i = binarySearch(nums,idx+1,n-1,nums[idx]); // It finds upper bound of elememt.
if(i == n) return idx+1; // Means that we are not able to upper bound of element.
idx++;
nums[idx] = nums[i];
}
return idx+1;
}
// Driver code
int main()
{
vector<int> arr{1, 2, 2, 3, 4, 4, 4, 5, 5};
// removeDuplicates() returns new size of array.
int n = removeDuplicates(arr);
// Print updated array
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
import java.util.Arrays;
public class GFG {
// Function to remove duplicate elements
// This function returns new size of modified array.
// Using Binary Search to solve the particular problem efficiently
public static int binarySearch(int[] nums, int low, int high, int val) {
int n = nums.length;
int res = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check for lower limit
if (nums[mid] <= val)
low = mid + 1;
// Check for higher limit
else {
// Move to higher limit
res = mid;
high = mid - 1;
}
}
// Check if not found
if (res == -1)
return n;
return res;
}
public static int removeDuplicates(int[] nums) {
int n = nums.length;
int idx = 0; // It store indexing of unique elements.
while (idx != n) {
int i = binarySearch(nums, idx + 1, n - 1, nums[idx]); // It finds upper bound of element.
if (i == n)
return idx + 1; // Means that we are not able to find the upper bound of the element.
idx++;
nums[idx] = nums[i];
}
return idx + 1;
}
// Driver code
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
// removeDuplicates() returns new size of array.
int n = removeDuplicates(arr);
// Print updated array
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by akshitaguprzj3
def binary_search(nums, low, high, val):
n = len(nums)
res = -1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] <= val:
low = mid + 1
else:
res = mid
high = mid - 1
if res == -1:
return n
return res
def remove_duplicates(nums):
n = len(nums)
idx = 0 # It stores the indexing of unique elements.
while idx != n:
i = binary_search(nums, idx + 1, n - 1, nums[idx]) # It finds the upper bound of the element.
if i == n: # Means we are not able to find the upper bound of the element.
return idx + 1
idx += 1
nums[idx] = nums[i]
return idx + 1
# Driver code
if __name__ == "__main__":
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
# remove_duplicates() returns the new size of the array.
n = remove_duplicates(arr)
# Print the updated array
for i in range(n):
print(arr[i], end=" ")
# This code is contributed by rambabuguphka
using System;
using System.Collections.Generic;
class Program
{
// Function to remove duplicate elements
// This function returns the new size of the modified array.
// Using Binary Search to solve the particular problem efficiently
static int BinarySearch(List<int> nums, int low, int high, int val)
{
int n = nums.Count;
int res = -1;
while (low <= high)
{
int mid = low + (high - low) / 2;
// Check for lower limit
if (nums[mid] <= val)
low = mid + 1;
// Check for higher limit
else
{
// Move to the higher limit
res = mid;
high = mid - 1;
}
}
// Check if not found
if (res == -1)
return n;
return res;
}
static int RemoveDuplicates(List<int> nums)
{
int n = nums.Count;
int idx = 0; // It stores the indexing of unique elements.
while (idx != n)
{
int i = BinarySearch(nums, idx + 1, n - 1, nums[idx]); // It finds the upper bound
// of the element.
if (i == n)
return idx + 1; // Means that we are not able to find the upper
// bound of the element.
idx++;
nums[idx] = nums[i];
}
return idx + 1;
}
static void Main()
{
List<int> arr = new List<int> { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
// RemoveDuplicates() returns the new size of the array.
int n = RemoveDuplicates(arr);
// Print the updated array
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
}
// This code is contributed by shivamgupta0987654321
// Function to remove duplicate elements
// This function returns the new size of the modified array.
// Using Binary Search to solve the problem efficiently
function binarySearch(nums, low, high, val) {
let res = -1;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
// Check for lower limit
if (nums[mid] <= val) low = mid + 1;
// Check for higher limit
else {
// Move to higher limit
res = mid;
high = mid - 1;
}
}
// Check if not found
if (res === -1) return nums.length;
return res;
}
function removeDuplicates(nums) {
let n = nums.length;
let idx = 0; // It stores the index of unique elements.
while (idx !== n) {
let i = binarySearch(nums, idx + 1, n - 1, nums[idx]); // Find the upper bound of the element.
if (i === n) return idx + 1; // Means that we are not able to find the upper bound of the element.
idx++;
nums[idx] = nums[i];
}
return idx + 1;
}
// Driver code
let arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];
// removeDuplicates() returns the new size of the array.
let n = removeDuplicates(arr);
// Print the updated array
for (let i = 0; i < n; i++) {
console.log(arr[i]);
}
// This code is contributed by shivamgupta0987654321
Output:
1 2 3 4 5
Time Complexity: O(NlogN) , in the worst case we will traverse whole array when each element of array is unique.
Auxiliary Space: O(1),No extra space is used
Please Login to comment...