Question

Sorting and Searching

Given an unsorted array numbers of integers with duplicate values. Sort the array and remove the duplicates in-place such that each element appears only once in the input array and returns the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Find the time complexity of your removeDuplicates() method in Big-O notation and write that in a comment line on the top of your code.

Hints: Sort the array before finding the number of unique elements. You can use any sorting algorithm that you have learned in the class. Do not use the built-in sorting algorithm of java.

Clarification:

Confused why the returned value of removeDuplicates() method is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller (main() method) as well.

Example 1:

Input: {1, 2, 1}

Output: {1, 2}

Your removeDuplicates() method should return length = 2, with the two unique elements of numbers being 1 and 2. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: {2, 1, 0, 1, 2, 0, 3, 3, 2, 1}

Output: {0, 1, 2, 3}

Your removeDuplicates() method should return length = 4, with the four unique elements of numbers are 0, 1, 2, and 3. It doesn't matter what values are set beyond the returned length.

USE THIS CODE:

import java.util.Scanner;

class Main {
  
// add your sorting algorithm code here
  
public static int removeDuplicates(int[] numbers){
// your code goes here for removing duplicates
  
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("Enter the size of the array > ");
int n = scan.nextInt();
int[] numbers = new int[n];
System.out.print("Enter the array elements with duplicates in it > ");
for(int i = 0; i < n; i++){
numbers[i] = scan.nextInt();
}
int len = removeDuplicates(numbers);
for(int i = 0; i < len; i++)
System.out.print(numbers[i] + " ");
System.out.println();
scan.close();
}
}

Answer 1

SOLUTION TO YOUR QUESTION

The method removeDuplicates(int[] numbers) uses O(n²) Time Complexity

Code to copy:

import java.util.*;

class Main {
  
// This Method uses O(n^2) Time Complexity
// add your sorting algorithm code here
public static int removeDuplicates(int[] numbers){
int i, key, j, l=0;
  
// USING INSERTION SORT
for(i=1; i<numbers.length; i++){
key = numbers[i];
j = i-1;
  
while(j>=0 && numbers[j]>key){
numbers[j+1] = numbers[j];
j -=1;
}
numbers[j+1] = key;
}
  
// REMOVING DUPLICATE VALUES
for(int k=0; k<numbers.length-1; k++){
if(numbers[k]!=numbers[k+1]){
numbers[l++] = numbers[k];
}
}
  
numbers[l++] = numbers[numbers.length - 1];
  
return l;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
  
System.out.print("Enter the size of the array > ");
int n = scan.nextInt();
int[] numbers = new int[n];
  
System.out.print("Enter the array elements with duplicates in it > ");
for(int i = 0; i < n; i++){
numbers[i] = scan.nextInt();
}
  
int len = removeDuplicates(numbers);
  
for(int i = 0; i < len; i++)
System.out.print(numbers[i] + " ");
System.out.println();
scan.close();
}
}

SNAPSHOTS OF THE CODE:

SAMPLE OUTPUT: