Remove Duplicates

Easy
0/40
Average time to solve is 15m
25 upvotes
Asked in companies
AmazonCIS - Cyber InfrastructurePayPal

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 2 2 3 4
5
10 11 23 23 23
Sample Output 1:
 1 2 3 4
 10 11 23
Explanation for Sample Input 1:
In the first test case, ‘2’ is a duplicate element, and there are two occurrences of ‘2’, so one ‘2’ is removed, and the resultant array becomes [1 2 3 4].

In the second test case, ‘23’ is a duplicate element, and there are three occurrences of ‘23’, so two occurrences of ‘23’ must be removed, and the resultant array becomes [10 11 23].
Sample Input 2 :
 2
 10
 1 3 3 3 3 3 4 9 23 35
 5
 10 10 10 10 10
Sample Output 2:
 1 3 4 9 23 35
 10
Hint

Can you traverse the whole array sequentially? 

Approaches (2)
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.
Time Complexity

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).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Remove Duplicates
Full screen
Console