Remove Duplicates
Ninja is playing with numbers but hates when he gets duplicate numbers. Ninja is provided an array, and he wants to remove all duplicate elements and return the array, but he has to maintain the order in which the elements were supplied to him.

Input Format:

The first line contains a single integer T representing the number of test cases. The first line of each test case will contain the integer N. The second and last line contains N space-separated integers that denote the elements of the given array.

Output Format:

For each test case, return the new array that does not contain any duplicates of the input array. The output of each test case should be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Remove Duplicates

Ninja is playing with numbers but hates when he gets duplicate numbers. Ninja is provided an array, and he wants to remove all duplicate elements and return the array, but he has to maintain the order in which the elements were supplied to him.

Input Format:

The first line contains a single integer T representing the number of test cases. 

The first line of each test case will contain the integer N.

The second and last line contains N space-separated integers that denote the elements of the given array.

Output Format:

For each test case, return the new array that does not contain any duplicates of the input array.

The output of each test case should be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5*10^3
-10^5 <= arr[i] <= 10^5

Time Limit: 1 sec

Accepted Answer

Brute Force

We will traverse the whole array and check if that element previously occurred or not.

The steps are as follows:

We initialize a vector ‘ans’ to store the final non-duplicate elements.
We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- We will iterate over all the elements of the array excluding present element, i.e., j = 0 to j = N - 1:
  - If we get such positions such that arr[i] equals arr[j], then we replace all such arr[j] with -1.
We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- If arr[i] not equals -1, then we store the value in ‘ans’.
We will return ‘ans’ as the final answer.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of elements in the given array.

We are using a vector ‘ans’ to store the final result. Hence, the overall space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the total number of elements in the given array.

As we keep an element fixed and check for all values from1 to ‘N’, there are at most ‘N^2’ iterations. Hence the overall time complexity is O(N^2).

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(N)



    Where 'N' denotes the number of elements of the array

'''





def removeDuplicates(arr):



    # Vector to store final array

    ans = []



    n = len(arr)



    # For loop to traverse all the elements

    for i in range(n):



        # Loop to check for repeated characters

        for j in range(n):



            if (arr[i] == arr[j] and i != j):

                arr[j] = -1





    # For loop to include only unique elements

    for i in range(n):

        if (arr[i] != -1):

            ans.append(arr[i])





    # Return the final array

    return ans

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N)



    Where 'N' denotes the number of elements of the array

*/



import java.util.ArrayList;



public class Solution {

	public static ArrayList removeDuplicates(ArrayList arr) {



		// Vector to store final array

		ArrayList < Integer > ans = new ArrayList();



		int n = arr.size();

		// For loop to traverse all the elements

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



			// Loop to check for repeated characters

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



				if (arr.get(i).intValue() == arr.get(j).intValue() && i != j) {

					arr.set(j, -1);

				}

			}

		}



		// For loop to include only unique elements

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

			if (arr.get(i).intValue()  != -1) {

				ans.add(arr.get(i).intValue() );

			}



		}

		// Return the final array

		return ans;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N)



    Where 'N' denotes the number of elements of the array

*/



vector < int > removeDuplicates(vector < int > arr) {



  // Vector to store final array

  vector < int > ans;



  int n = arr.size();

  // For loop to traverse all the elements

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



    // Loop to check for repeated characters

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



      if (arr[i] == arr[j] && i != j) {

        arr[j] = -1;

      }

    }

  }



  // For loop to include only unique elements

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

    if (arr[i] != -1) {

      ans.push_back(arr[i]);

    }



  }

  // Return the final array

  return ans;



}

Accepted Answer

Hash Map

We will traverse the whole array and keep a count of the frequency of each element. If the frequency is one or more than one, then we return only one occurrence of that element only.

The steps are as follows:

We initialize a hash map ‘freqOfElements’ to store the frequency of each element and vector ‘ans’ to store the final non-duplicate elements.
We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- We will store the frequency of an element arr[i] in ‘freqOfElements’.
- If the element already exists in ‘m’ then increment freqOfElements[arr[i]].
We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- If freqOfElements[arr[i]] is not -1 then we store the value of arr[i] in ‘ans’.
- We change the value of freqOfElements[arr[i]] to -1.
We will return ‘ans’ as the final answer.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of elements in the given array.

We are using a vector ‘ans’ to store the final result. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of elements in the given array.

As we check for all values from1 to ‘N’, there are at most ‘N’ iterations. Hence the overall time complexity is O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' denotes the number of elements of the array

*/



#include 



vector  < int > removeDuplicates(vector < int > arr) {

  // Map to store the frequency of each character

  unordered_map < int, int > freqOfCharacters;



  // Vector to store final array

  vector < int > ans;



  int n = arr.size();

  // For loop to traverse all the elements

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



    // Mapping each element

    if (freqOfCharacters.find(arr[i]) != freqOfCharacters.end()) {

      freqOfCharacters[arr[i]] = freqOfCharacters[arr[i]] + 1;

    } else {

      freqOfCharacters[arr[i]] = 1;

    }



  }



  // For loop to include only unique elements

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

    if (freqOfCharacters.find(arr[i]) != freqOfCharacters.end() && freqOfCharacters[arr[i]] != -1) {

      ans.push_back(arr[i]);



      // After storing each unique element set mapping to -1

      freqOfCharacters[arr[i]] = -1;

    }

  }

  // Return the final array

  return ans;



}

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' denotes the number of elements of the array

*/



import java.util.ArrayList;

import java.util.HashMap;



public class Solution {

	public static ArrayList removeDuplicates(ArrayList arr) {

// Map to store the frequency of each character

		HashMap < Integer, Integer > freqOfCharacters = new HashMap();



		// Vector to store final array

		ArrayList < Integer > ans = new ArrayList();



		int n = arr.size();

		// For loop to traverse all the elements

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



			// Mapping each element

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

				freqOfCharacters.put( arr.get(i) , freqOfCharacters.get(arr.get(i)) + 1);

			} else {

				freqOfCharacters.put( arr.get(i) , 1);

			}



		}



		// For loop to include only unique elements

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

			if (freqOfCharacters.containsKey(arr.get(i)) && freqOfCharacters.get(arr.get(i)).intValue() != -1) {

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



				// After storing each unique element set mapping to -1

				freqOfCharacters.put( arr.get(i) , -1);

			}

		}

		// Return the final array

		return ans;



	}

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' denotes the number of elements of the array

'''



from collections import OrderedDict



def removeDuplicates(arr):



    # Map to store the frequency of each character

    freqOfCharacters = OrderedDict()



    # Vector to store final array

    ans = []



    n = len(arr)



    # For loop to traverse all the elements

    for i in range(n):



        # Mapping each element

        if (arr[i] in freqOfCharacters):

            freqOfCharacters[arr[i]] = freqOfCharacters.get(arr[i]) + 1



        else:

            freqOfCharacters[arr[i]] = 1



    # For loop to include only unique elements

    for i in range(n):

        if (arr[i] in freqOfCharacters and freqOfCharacters[arr[i]] != -1):

            ans.append(arr[i])



            # After storing each unique element set mapping to -1

            freqOfCharacters[arr[i]] = -1

            

            

    # Return the final array

    return ans

Ninja is playing with numbers but hates when he gets duplicate numbers. Ninja is provided an array, and he wants to remove all duplicate elements and return the array, but he has to maintain the order in which the elements were supplied to him.

Input Format:

Output Format:

Note:

Constraints:

Top TCS System Engineer interview questions & answers

Popular interview questions of System Engineer

Top HR questions asked in TCS System Engineer