Remove duplicates from Sorted Array-O(n) Time and O(1) Space

We don’t need to keep a hash set because the array is sorted. An element would appear one after the other. Therefore, our primary task is to determine whether the current element is identical to the prior one.

Detailed implementation:

• The index of the following separate item will be stored in idx, therefore start with idx = 1. We start idx with 1 since the first item is the first distinct item and there is nothing before it.
• For each i = 0 to n-1, loop through the array.
• Assign arr[idx] = arr[i] and increase idx at each index i if arr[i] differs from arr[i-1].
• The unique elements in the first idx places are contained in arr[] after the loop.

C++

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

C

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

Java

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] + " ");
        }
    }
}

Python

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=" ")

Output

1 2 3 4 5