Suppose we have a sorted list A. We have to return the length of the array after removing all duplicate entries. We have to perform this in O(1) extra space. So we have to do the operation in-place.
For an example, suppose A = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6] Then the output will be 6, as there are six distinct elements.
To solve this, follow these steps −
- If the list is empty, return 0
- otherwise, initially take prev = first element of A. And define length = 0
- for i := 1 to n-1, do
- if A[i] is not the same as prev, then
- length := length + 1
- prev := A[i]
- if A[i] is not the same as prev, then
- return length
Let us see the implementation to get a better understanding
Example (Python)
Live Demo
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 0: return 0 length = 1 previous = nums[0] index = 1 for i in range(1,len(nums)): if nums[i] != previous: length += 1 previous = nums[i] nums[index] = nums[i] index+=1 return length input_list = [1,1,2,2,2,3,3,3,3,4,5,5,5,6] ob1 = Solution() print(ob1.removeDuplicates(input_list))Input
[1,1,2,2,2,3,3,3,3,4,5,5,5,6]Output
6
Updated on 28-Apr-2020 15:59:22
- Related Questions & Answers
- Remove Duplicates from Sorted Array II in C++
- Remove Duplicates from Sorted List in C++
- Remove Duplicates from Sorted List II in C++
- How to remove duplicates from a sorted linked list in android?
- How to remove duplicates from the sorted array and return the length using C#?
- How to remove duplicates from the sorted array and return the non-duplicated array using C#?
- Removing duplicates from a sorted array of literals in JavaScript
- Python - Ways to remove duplicates from list
- Remove duplicates from a array of objects JavaScript
- Remove duplicates from array with URL values in JavaScript
- Java Program to Remove Duplicates from an Array List
- Remove Consecutive Duplicates in Python
- Remove all duplicates from a given string in Python
- Remove array duplicates by property - JavaScript
- Python program to remove Duplicates elements from a List?
View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
Given a sorted array, the task is to remove the duplicate elements from the array.
Examples:
Input : arr[] = {2, 2, 2, 2, 2} Output : arr[] = {2} new size = 1 Input : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5} Output : arr[] = {1, 2, 3, 4, 5} new size = 5Method 1: (Using extra space)
- 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 count of unique elements. Let this count be j.
- Copy j elements from temp[] to arr[] and return j
C++
#include <iostream>
using namespace std;
int removeDuplicates(int arr[], int n)
{
if (n == 0 || n == 1)
return n;
int temp[n];
int j = 0;
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
temp[j++] = arr[n - 1];
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
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;
}
C
#include <stdio.h>
int removeDuplicates(int arr[], int n)
{
if (n == 0 || n == 1)
return n;
int temp[n];
int j = 0;
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
temp[j++] = arr[n - 1];
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
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++)
printf("%d ", arr[i]);
return 0;
}
Java
class Main {
static int removeDuplicates(int arr[], int n)
{
if (n == 0 || n == 1)
return n;
int[] temp = new int[n];
int j = 0;
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
temp[j++] = arr[n - 1];
for (int i = 0; i < j; i++)
arr[i] = temp[i];
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);
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
Python3
def removeDuplicates(arr, n):
if n == 0 or n == 1:
return n
temp = list(range(n))
j = 0;
for i in range(0, n-1):
if arr[i] != arr[i+1]:
temp[j] = arr[i]
j += 1
temp[j] = arr[n-1]
j += 1
for i in range(0, j):
arr[i] = temp[i]
return j
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
n = len(arr)
n = removeDuplicates(arr, n)
for i in range(n):
print ("%d"%(arr[i]), end = " ")
C#
using System;
class GFG {
static int removeDuplicates(int []arr, int n)
{
if (n == 0 || n == 1)
return n;
int []temp = new int[n];
int j = 0;
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i+1])
temp[j++] = arr[i];
temp[j++] = arr[n-1];
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
public static void Main ()
{
int []arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
int n = arr.Length;
n = removeDuplicates(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
Javascript
<script>
function removeDuplicates(arr, n)
{
if (n==0 || n==1)
return n;
var temp = new Array(n);
var j = 0;
for (var i=0; i<n-1; i++)
if (arr[i] != arr[i+1])
temp[j++] = arr[i];
temp[j++] = arr[n-1];
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;
n = removeDuplicates(arr, n);
for (var i=0; i<n; i++)
document.write( arr[i]+" ");
</script>
Time Complexity : O(n)
Auxiliary Space : O(n)
Method 2: (Constant extra space)
Just maintain a separate index for same array as maintained for different array in Method 1.
Implementation:
C++
#include<iostream>
using namespace std;
int removeDuplicates(int arr[], int n)
{
if (n==0 || n==1)
return n;
int j = 0;
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;
}
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;
}
Java
class Main
{
static int removeDuplicates(int arr[], int n)
{
if (n == 0 || n == 1)
return n;
int j = 0;
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);
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
}
Python3
# Python3 program to remove # duplicate elements # This function returns new # size of modified array def removeDuplicates(arr, n): 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(0, n-1): if arr[i] != arr[i+1]: arr[j] = arr[i] j += 1 arr[j] = arr[n-1] j += 1 return j # Driver code 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(0, n): print (" %d "%(arr[i]), end = " ")C#
using System;
class GfG {
static int removeDuplicates(int []arr, int n)
{
if (n == 0 || n == 1)
return n;
int j = 0;
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 ()
{
int []arr = {1, 2, 2, 3, 4, 4,
4, 5, 5};
int n = arr.Length;
n = removeDuplicates(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
Javascript
<script>
function removeDuplicates(arr , n) {
if (n == 0 || n == 1)
return n;
var j = 0;
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);
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
</script>
Time Complexity : O(n)
Auxiliary Space : O(1)
This article is contributed by Sahil Chhabra. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.