Remove Duplicates - Innoskrit

Innoskrit July 30, 2022 Innoskrit Masterclass DSA Sheet, Two Pointers

Problem Statement

Given an array of sorted numbers, remove all duplicates from it. After removing the duplicates in-place return the new length of the array.

In-place: Do not use Extra Space.

Example:

Input: arr: [1, 1, 2, 3, 3, 3, 4, 6, 9, 9]
Output: 6
Explanation: Elements 1, 3, 9 are present more than once in an array and 2, 4, 6 only once. So, new length of the array will be 6 with [1, 2, 3, 4, 6, 9].

Code

Java

C++

Python

class Innoskrit {

	public static int removeDuplicates(int arr[]) {
		int unique = 0;
		
		for(int duplicate = 1; duplicate < arr.length; duplicate++) {
		    if(arr[unique] != arr[duplicate]) {
		        arr[unique+1] = arr[duplicate];
		        unique++;
		    }
		}
		
		return unique+1;
	}

	public static void main(String[] args) {

		int arr[] = new int[] {1, 1, 2, 3, 3, 3, 4, 6, 9, 9};
		int ans = Innoskrit.removeDuplicates(arr);
		System.out.println(ans);
		
	}
}

#include<bits/stdc++.h>
using namespace std;

class Innoskrit {
    
public:
	static int removeDuplicates(vector<int> &arr) {
		int unique = 0;
		
		for(int duplicate = 1; duplicate < arr.size(); duplicate++) {
		    if(arr[unique] != arr[duplicate]) {
		        arr[unique+1] = arr[duplicate];
		        unique++;
		    }
		}
		
		return unique+1;
	}
};

int main() {

	vector<int> arr = {1, 1, 2, 3, 3, 3, 4, 6, 9, 9};
	int ans = Innoskrit::removeDuplicates(arr);
	cout << ans;
	return 0;
	
}

class Innoskrit:
    
    @staticmethod
    def remove_duplicates(arr):
        unique = 0
        
        for duplicate in range(1, len(arr)):
		    if arr[unique] != arr[duplicate]:
		        arr[unique+1] = arr[duplicate]
		        unique += 1
        
        return unique+1
        
if __name__ == '__main__':
    arr = [1, 1, 2, 3, 3, 3, 4, 6, 9, 9]
    ans = Innoskrit.remove_duplicates(arr)
    print(ans)

Output:

Time and Space Complexity

Time Complexity: O(N)

Space Complexity: O(1)