Remove duplicates from Sorted Array

Given a sorted array arr[] of size n, the goal is to rearrange the array so that all distinct elements appear at the beginning in sorted order. Additionally, return the length of this distinct sorted subarray.

Note: The elements after the distinct ones can be in any order and hold any value, as they don't affect the result.

Examples: 

Input: arr[] = [2, 2, 2, 2, 2]
Output: [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: [1, 2, 3, 4, 5]

Input: arr[] = [1, 2, 3]
Output: [1, 2, 3]
Explanation : No change as all elements are distinct.

Using Hash Set - Works for Unsorted Also - O(n) Time and O(n) Space

• Use a hash set or dictionary to store elements already processed
• Initialize index of result array as 0.
• Traverse through the input array. If an element is not in the hash set, put it at the result index and insert into the set.

#include <iostream> #include <vector> #include <unordered_set> using namespace std; int removeDuplicates(vector<int>& arr) {    // To track seen elements  unordered_set<int> s;     // To maintain the new size of the array  int idx = 0;   for (int i = 0; i < arr.size(); i++) {  if (s.find(arr[i]) == s.end()) {   s.insert(arr[i]);   arr[idx++] = arr[i];   }  }    // Return the size of the array   // with unique elements  return s.size();  } int main() {  vector<int> arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int newSize = removeDuplicates(arr);  for (int i = 0; i < newSize; i++)   cout << arr[i] << " ";  return 0; } 

import java.util.HashSet; class GfG {  static int removeDuplicates(int[] arr) {    // To track seen elements  HashSet<Integer> s = new HashSet<>();    // To maintain the new size of the array  int idx = 0;   for (int i = 0; i < arr.length; i++) {  if (!s.contains(arr[i])) {   s.add(arr[i]);   arr[idx++] = arr[i];   }  }  // Return the size of the array   // with unique elements  return idx;  }  public static void main(String[] args) {  int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int newSize = removeDuplicates(arr);  for (int i = 0; i < newSize; i++) {  System.out.print(arr[i] + " ");  }  } } 

def removeDuplicates(arr): # To track seen elements seen = set() # To maintain the new size of the array idx = 0 for i in range(len(arr)): if arr[i] not in seen: seen.add(arr[i]) arr[idx] = arr[i] idx += 1 # Return the size of the array  # with unique elements return idx if __name__ == "__main__": arr = [1, 2, 2, 3, 4, 4, 4, 5, 5] newSize = removeDuplicates(arr) for i in range(newSize): print(arr[i], end=" ") 

using System; using System.Collections.Generic; class GfG {  static int removeDuplicates(int[] arr) {    // To track seen elements  HashSet<int> s = new HashSet<int>();    // To maintain the new size of the array  int idx = 0;  for (int i = 0; i < arr.Length; i++) {  if (!s.Contains(arr[i])) {   s.Add(arr[i]);  arr[idx++] = arr[i];  }  }  // Return the size of the array   // with unique elements  return idx;  }  static void Main() {  int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int newSize = removeDuplicates(arr);  for (int i = 0; i < newSize; i++) {  Console.Write(arr[i] + " ");  }  } } 

function removeDuplicates(arr) {    // To track seen elements  const s = new Set();    // To maintain the new size of the array  let idx = 0;  for (let i = 0; i < arr.length; i++) {  if (!s.has(arr[i])) {  s.add(arr[i]);  arr[idx++] = arr[i];  }  }  // Return the size of the array   // with unique elements  return idx; } // Driver code const arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]; const newSize = removeDuplicates(arr); console.log(arr.slice(0, newSize).join(' ')); 

1 2 3 4 5 

Expected Approach - O(n) Time and O(1) Space

Since the array is sorted, we do not need to maintain a hash set. All occurrences of an element would be consecutive. So we mainly need to check if the current element is same as the previous element or not.

Step by step implementation:

• Start with idx = 1 (idx is going to hold the index of the next distinct item. Since there is nothing before the first item, we consider it as the first distinct item and begin idx with 1.
• Loop through the array for i = 0 to n-1.
  • At each index i, if arr[i] is different from arr[i-1], assign arr[idx] = arr[i] and increment idx.
• After the loop, arr[] contains the unique elements in the first idx positions.

#include <iostream> #include <vector> using namespace std; int removeDuplicates(vector<int>& arr) {  int n = arr.size();  if (n <= 1)  return n;  // Start from the second element  int idx = 1;     for (int i = 1; i < n; i++) {  if (arr[i] != arr[i - 1]) {  arr[idx++] = arr[i];  }  }  return idx; } int main() {  vector<int> arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int newSize = removeDuplicates(arr);  for (int i = 0; i < newSize; i++)   cout << arr[i] << " ";  return 0; } 

#include <stdio.h> int removeDuplicates(int arr[], int n) {  if (n <= 1)  return n;   // Start from the second element  int idx = 1;    for (int i = 1; i < n; i++) {  if (arr[i] != arr[i - 1]) {  arr[idx++] = arr[i];  }  }  return idx; } int main() {  int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int n = sizeof(arr) / sizeof(arr[0]);  int newSize = removeDuplicates(arr, n);    for (int i = 0; i < newSize; i++)   printf("%d ", arr[i]);  return 0; } 

class GfG {  static int removeDuplicates(int[] arr) {  int n = arr.length;  if (n <= 1)  return n;   // Start from the second element  int idx = 1;     for (int i = 1; i < n; i++) {  if (arr[i] != arr[i - 1]) {  arr[idx++] = arr[i];  }  }  return idx;  }  public static void main(String[] args) {  int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int newSize = removeDuplicates(arr);  for (int i = 0; i < newSize; i++) {  System.out.print(arr[i] + " ");  }  } } 

def removeDuplicates(arr): n = len(arr) if n <= 1: return n # Start from the second element idx = 1 for i in range(1, n): if arr[i] != arr[i - 1]: arr[idx] = arr[i] idx += 1 return idx if __name__ == "__main__": arr = [1, 2, 2, 3, 4, 4, 4, 5, 5] newSize = removeDuplicates(arr) for i in range(newSize): print(arr[i], end=" ") 

using System; class GfG {  static int removeDuplicates(int[] arr) {  int n = arr.Length;  if (n <= 1)  return n;   // Start from the second element  int idx = 1;   for (int i = 1; i < n; i++) {  if (arr[i] != arr[i - 1]) {  arr[idx++] = arr[i];  }  }  return idx;  }  static void Main() {  int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};  int newSize = removeDuplicates(arr);  for (int i = 0; i < newSize; i++) {  Console.Write(arr[i] + " ");  }  } } 

function removeDuplicates(arr) {  const n = arr.length;  if (n <= 1)  return n;   // Start from the second element  let idx = 1;   for (let i = 1; i < n; i++) {  if (arr[i] !== arr[i - 1]) {  arr[idx++] = arr[i];  }  }  return idx; } // Driver code const arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]; const newSize = removeDuplicates(arr); console.log(arr.slice(0, newSize).join(' ')); 

1 2 3 4 5