Make Unique Array
You are given an array ‘ARR’ of size ‘N,’ and you have to tell the minimum number of elements that need to be removed such that the array contains all distinct elements. More formally, there should not be any ‘I’ and ‘J’ such that ‘I’ != ‘J’ and ‘ARR’[‘I’] = ‘ARR’[‘J’].

For example:

Given ‘N’ = 4, 'ARR' = { 1, 2, 1, 2} Then the answer is 2 because 1 and 2 are repeated once therefore we need to remove 2 elements.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array. The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output Format :

For each test case, You are supposed to return an integer denoting the minimum number of elements to remove from the array, such that the array contains all distinct elements.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Make Unique Array

You are given an array ‘ARR’ of size ‘N,’ and you have to tell the minimum number of elements that need to be removed such that the array contains all distinct elements. More formally, there should not be any ‘I’ and ‘J’ such that ‘I’ != ‘J’ and ‘ARR’[‘I’] = ‘ARR’[‘J’].

For example:

Given ‘N’ = 4, 
'ARR' = { 1, 2, 1, 2} 
Then the answer is 2 because 1 and 2 are repeated once therefore we need to remove 2 elements.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output Format :

For each test case, You are supposed to return an integer denoting the minimum number of elements to remove from the array, such that the array contains all distinct elements.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 5000
0 <= 'ARR[i]’ <= 10 ^ 6

Time Limit: 1 sec.

Accepted Answer

Brute force

The idea is to maintain an array which contains only unique elements, then for each element in the given array search whether the unique array has that element or not. In the return ‘N’ minus the size of the unique array.

The steps are as follows:

Maintain an array ‘uniqueArray’ which contains only unique elements.
Declare function ‘findElement’:
- Which takes the ‘uniqueArray’ and ‘val’ to find as parameters.
- It searches for the ‘val’ in ‘uniqueArray’ and returns true if found else false.
For every element in the array check if it is present in the ‘uniqueArray’ if not then add in the ‘uniqueArray’
Return ‘N’ - size of ‘uniqueArray’ as the final result.

Space Complexity: O(1)Explanation:

O(N).

Since we are using an array to store elements hence, the overall space complexity is O(1).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number given.

Since in the worst case we are traversing the whole array for each element, the final time Complexity will be O(N ^ 2).

Python (3.5)

'''

    Time Complexity : O(N ^ 2)

    Space Complexity : O(N)



    Where 'N' is the size of the array.

'''





def findElement(uniqueArray, val):



    for i in uniqueArray:

        if i == val:

            return True



    return False







def minElementsToRemove(arr):



    n = len(arr)



    uniqueArray = []



    for i in range(n):

        if findElement(uniqueArray, arr[i]) == False:

            uniqueArray.append(arr[i])



    return n - len(uniqueArray)

Java (SE 1.8)

/*

	Time Complexity : O(N ^ 2)

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



import java.util.ArrayList;



public class Solution {



	private static Boolean findElement(ArrayList uniqueArray, int val) {

		for (int i : uniqueArray) {

			if (i == val) {

				return true;

			}

		}



		return false;

	}





	public static int minElementsToRemove(ArrayList arr) {



		int n = arr.size();



		ArrayList uniqueArray = new ArrayList();



		for (int i = 0 ; i < n ; i++) {

			if (findElement(uniqueArray, arr.get(i)) == false) {

				uniqueArray.add(arr.get(i));

			}

		}



		return (n - uniqueArray.size());



	}

}

C++ (g++ 5.4)

/*

	Time Complexity : O(N ^ 2)

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



bool findElement(vector &uniqueArray, int val)

{

	for (int i : uniqueArray)

	{

		if (i == val)

		{

			return true;

		}

	}



	return false;

}



int minElementsToRemove(vector &arr)

{

	int n = arr.size();



	vector uniqueArray;



	for (int i = 0 ; i < n ; i++)

	{

		if (findElement(uniqueArray, arr[i]) == false)

		{

			uniqueArray.push_back(arr[i]);

		}

	}



	return (n - uniqueArray.size());

}

Accepted Answer

Sorting

The idea is to sort the array and then check if the consecutive elements are the same. If they are, then we increase the counter to remove elements.

The steps are as follows:

Maintain a variable ‘minRemoves,’ which denotes the minimum number of elements we have to remove.
Sort the array in ascending order.
Maintain a variable ‘prev’ which tells us what the previous element that we encountered was.
Loop from i = 0 to i = ‘N’ - 1.
- If the current element, i.e., ‘arr’[‘i’], is equal to the ‘prev’, then increase ‘minRemoves’ by 1.
- Else change ‘prev’ to ‘arr’[‘i’].
Return ‘minRemoves’ as the final result.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space hence, the overall space complexity is O(1).

Time Complexity: O(nlogn)Explanation:

O(N*log(N)), where ‘N’ is the number given.

Since we are sorting the array and traversing the array once, the time complexity is O(N + N*log(N)). Hence, the final time complexity will be O(N*log(N)).

C++ (g++ 5.4)

/*

	Time Complexity : O(N*log(N))

	Space Complexity : O(1)



	Where 'N' is the size of the array.

*/



#include 



int minElementsToRemove(vector &arr)

{

	int n = arr.size();



	// Sort the array.

	sort(arr.begin(), arr.end());



	// To keep track of previous element.

	int prev = 1e8;

	int minRemoves = 0;



	for (int i = 0 ; i < n ; i++)

	{

		if (arr[i] != prev)

		{

			prev = arr[i];

		}

		else

		{

			minRemoves++;

		}

	}



	return minRemoves;

}

Python (3.5)

'''

    Time Complexity : O(N*log(N))

    Space Complexity : O(1)



    Where 'N' is the size of the array.

'''





def minElementsToRemove(arr):



    n = len(arr)



    # Sort the array.

    arr.sort()



    # To keep track of previous element.

    prev = 100000000

    minRemoves = 0



    for i in range(n):



        if arr[i] != prev:

            prev = arr[i]



        else:

            minRemoves += 1



    return minRemoves

Java (SE 1.8)

/*

	Time Complexity : O(N*log(N))

	Space Complexity : O(1)



	Where 'N' is the size of the array.

*/



import java.util.Collections;

import java.util.ArrayList;



public class Solution {



	public static int minElementsToRemove(ArrayList arr) {

		int n = arr.size();



		// Sort the array.

		Collections.sort(arr);



		// To keep track of previous element.

		int prev = 100000000;

		int minRemoves = 0;



		for (int i = 0 ; i < n ; i++) {

			if (arr.get(i).intValue() != prev) {

				prev = arr.get(i).intValue();

			} else {

				minRemoves++;

			}

		}



		return minRemoves;

	}

}

Accepted Answer

Hash Map

The idea is to use a hash map, which stores all the elements we have seen so far, and if any element re-appears, then we remove it. Else we mark that element as present.

The steps are as follows:

Maintain a variable ‘minRemoves’, which denotes the minimum number of elements we have to remove.
Maintain a Hash-Map ‘present to mark all the elements that are present.
Loop from 0 to ‘N’ - 1 to traverse ‘arr’:
- If ‘arr[i]’ is already present in the hashmap, then increase ‘minRemoves’ by 1.
- Else mark ‘arr[i]’ as present.
Return ‘minRemoves’ as the final result.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the number given.

Since we are just doing a linear sweep hence, the overall time complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number given.

Since we are just doing a linear sweep hence, the overall time complexity is O(N).

C++ (g++ 5.4)

/*

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



#include 



int minElementsToRemove(vector &arr)

{

	int n = arr.size();



	unordered_map present;

	int minRemoves = 0;



	for (int i = 0; i < n; i++)

	{

		// If the current element is present in array.

		if (present[arr[i]])

		{

			// Increase the number of removes.

			minRemoves++;

		}

		else

		{

			// Else recoganize that element is present.

			present[arr[i]] = true;

		}

	}



	return minRemoves;

}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the size of the array.

'''





def minElementsToRemove(arr):



    n = len(arr)



    present = {}

    minRemoves = 0



    for i in range(n):



        # If the current element is present in array.

        if (arr[i] in present):

            # Increase the number of removes.

            minRemoves += 1



        else:

            # Else recoganize that element is present.

            present[arr[i]] = True



    return minRemoves

Java (SE 1.8)

/*

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



import java.util.ArrayList;

import java.util.HashMap;



public class Solution {



	public static int minElementsToRemove(ArrayList arr) {



		int n = arr.size();



		HashMap present = new HashMap<>();

		int minRemoves = 0;



		for (int i = 0; i < n; i++) {



			// If the current element is present in array.

			if (present.containsKey(arr.get(i))) {

				// Increase the number of removes.

				minRemoves++;

			} else {

				// Else recoganize that element is present.

				present.put(arr.get(i), true);

			}

		}



		return minRemoves;

	}

}

For example:

Input format:

Output Format :

Note:

Constraints:

Top Nagarro Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer

Top HR questions asked in Nagarro Senior Software Engineer