- Problem Statement<\/a><\/li>
- Method – 1 (Using Sorting)<\/a><\/li>
- Solution 1 (Using extra space)<\/a><\/li>
- C\/C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Solution 2 (Without using extra space)<\/a><\/li>
- C\/C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul><\/ul>
- Method – 2 (Use of HashMaps)<\/a><\/li>
- C\/C++ Code For HashMaps<\/a><\/li>
- Java Code For HashMaps<\/a><\/li>
- Python Code For HashMaps<\/a><\/li><\/ul>
- FAQs<\/a><\/li>
- Q.1: How do you find duplicates in an array?<\/a><\/li>
- Q.2: How do you remove duplicates from an unsorted array in place?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given an array of integers, the task is to remove the duplicates from the array.<\/p>\n\n\n\n
<\/figure><\/div>\n\n\n\n
Method – 1 (Using Sorting)<\/span><\/h2>\n\n\n\n
Intuition:<\/strong><\/p>\n\n\n\n
Sorting will help in grouping duplicate elements together.<\/p>\n\n\n\n
Input array: 1 2 3 2 2 3 4
Sorted array: 1 2 2 2 3 3 4 (all 2\u2019s and 3\u2019s are grouped together).\u00a0<\/p>\n\n\n\nNow the problem is to remove duplicates from the sorted array.<\/p>\n\n\n\n
Solution 1 (Using extra space)<\/h3>\n\n\n\n
- Sort the given array.<\/li>
- Create an auxiliary array to store the unique elements and also maintain the count of unique elements.(here we will iterate over the sorted array and will put the first occurrence of each element in the auxiliary array and also maintain an integer to get the count of these unique elements which will also tell us about the index where the next element should be placed).<\/li>
- Copy elements from auxiliary array to given array.<\/li><\/ul>\n\n\n\n
C\/C++ Code<\/span><\/h4>\n\n\n\n
int removeDuplicates(int arr[], int n) {\n if(n == 0 || n == 1)\n return n;\n sort(arr, arr+n);\n int temp[n]; \n int i = 0, j = 0; \n temp[j++] = arr[i++];\n for( ; i<n; i++){\n if(arr[i] != arr[i-1]){\n temp[j++] = arr[i];\n }\n }\n for(i=0; i<j; i++){\n arr[i] = temp[j];\n }\n return j;\n}<\/pre>\n\n\n\nJava Code<\/h4>\n\n\n\n
public static int removeduplicates(int arr[], int n){\n if (n == 0 || n == 1) {\n return n;\n }\n Arrays.sort(arr); \n int[] temp = new int[n];\n int i = 0, j = 0;\n temp[j++] = arr[i++];\n for ( ; i < n - 1; i++) {\n if (arr[i] != arr[i-1]) {\n temp[j++] = arr[i];\n }\n }\n for (i = 0; i < j; i++) {\n arr[i] = temp[i];\n }\n return j;\n}<\/pre>\n\n\n\nPython Code<\/h4>\n\n\n\n
def removeDuplicates(arr, n):\n if n == 0 or n == 1:\n return n\n arr.sort();\n temp = list(range(n))\n j = 0\n temp[j] = arr[0] j+=1\n for i in range(1, n):\n if arr[i] != arr[i-1]:\n temp[j] = arr[i]\n j += 1\n \n for i in range(0, j):\n arr[i] = temp[i]\n\n return j<\/pre>\n\n\n\n
- Time complexity<\/strong> will be O(NlogN) because we have used sorting.<\/li>
- Space complexity<\/strong> will be O(N) using an extra array.<\/li><\/ul>\n\n\n\n
Solution 2 (Without using extra space)<\/h3>\n\n\n\n
The approach is the same as the above solution: just don\u2019t use the extra array instead do in-place swaps.<\/p>\n\n\n\n
We are using an integer to have the count of unique elements which will also tell us about the position where the new element should be placed in the same array.<\/p>\n\n\n\n
So starting from j = 0 indicates no unique elements are there and as we will iterate if we encounter any new element we put that element in jth position and will increase j.<\/p>\n\n\n\n
C\/C++ Implementation<\/span><\/h4>\n\n\n\n
int removeDuplicates(int arr[], int n) {\n if(n == 0 || n == 1)\n return n;\n sort(arr, arr+n); \n int j = 0; \n for(int i=1; i<n; i++){\n if(arr[i] != arr[i-1]){\n arr[++j]=arr[i];\n }\n }\n return j;\n}<\/pre>\n\n\n\nJava Implementation<\/h4>\n\n\n\n
public static int removeduplicates(int arr[], int n){\n if (n == 0 || n == 1) {\n return n;\n }\n Arrays.sort(arr); \n int j = 0;\n for ( int i = 0; i < n ; i++) {\n if (arr[i] != arr[i-1]) {\n arr[++j] = arr[i];\n }\n }\n return j;\n}<\/pre>\n\n\n\nPython Implementation<\/h4>\n\n\n\n
def removeDuplicates(arr, n):\n if n == 0 or n == 1:\n return n\n arr.sort();\n j = 1\n for i in range(1, n):\n if arr[i] != arr[i-1]:\n arr[j] = arr[i]\n j += 1\n return j<\/pre>\n\n\n\n
- Time complexity<\/strong> will be O(NlogN) because we have used sorting.<\/li>
- Space complexity<\/strong> will be O(N) using an extra array.<\/li><\/ul>\n\n\n\n
Method – 2 (Use of HashMaps)<\/span><\/h2>\n\n\n\n
We know we can use hashmaps when we need to know whether some element is present in it in O(1).<\/p>\n\n\n\n
So while traversing the array we will store the elements in a hashmap.<\/p>\n\n\n\n
And like approaches explained above we will place unique elements by checking whether the current element is already present in the hashmap or not.<\/p>\n\n\n\n
C\/C++ Code For HashMaps<\/span><\/h3>\n\n\n\n
int removeDuplicates(int arr[], int n) {\n if(n == 0 || n == 1)\n return n; \n int j = 0; unordered_map<int,int> mp; \n for(int i=0; i<n; i++){\n if(mp.find(arr[i])==mp.end()){ arr[j++] = arr[i]; }\n }\n return j;\n}<\/pre>\n\n\n\nJava Code For HashMaps<\/h3>\n\n\n\n
public static int removeduplicates(int arr[], int n){\n if (n == 0 || n == 1) {\n return n;\n }\n HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();\n int j = 0;\n for (int i=0; i < n; i++) {\n if (map.containsKey(arr[i])==0) {\n map.put(arr[i], 1); arr[j++] = arr[i];\n }\n }\n return j;\n}<\/pre>\n\n\n\nPython Code For HashMaps<\/h3>\n\n\n\n
def removeDuplicates(arr, n):\n if n == 0 or n == 1:\n return n mp = {i : 0 for i in arr}\n j = 0\n for i in range(0, n):\n if mp[arr[i]]==0:\n arr[j] = arr[i]\n j += 1 mp[arr[i]] = 1\n return j<\/pre>\n\n\n\n- Time complexity<\/strong> will be O(N) because of the use of hashmaps.<\/li>
- Space complexity<\/strong> will be O(N) using a hashmap.<\/li><\/ul>\n\n\n\n
\n\n\n\nPractice Problems<\/strong><\/p>\n\n\n\n
Remove Duplicates From Sorted Arrays<\/a>
Remove Element From An Array<\/a><\/p>\n\n\n\nFAQs<\/h2>\n\n\n\n
Q.1: How do you find duplicates in an array?<\/span><\/h3>\n\n\n\n
Ans: For finding duplicates we can use our hashmaps, and we can also find duplicates by sorting the array.<\/p>\n\n\n\n
Q.2: How do you remove duplicates from an unsorted array in place?<\/span><\/h3>\n\n\n\n
Ans: We can use hashmaps to maintain the frequency of each element and then we can remove the duplicates from the array.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array of integers, the task is to remove the duplicates from the array. Method…\n","protected":false},"author":5,"featured_media":3318,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[144,521],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3314"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3314"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3314\/revisions"}],"predecessor-version":[{"id":20737,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3314\/revisions\/20737"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3318"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Space complexity<\/strong> will be O(N) using a hashmap.<\/li><\/ul>\n\n\n\n
- Space complexity<\/strong> will be O(N) using an extra array.<\/li><\/ul>\n\n\n\n
- Space complexity<\/strong> will be O(N) using an extra array.<\/li><\/ul>\n\n\n\n
- Time complexity<\/strong> will be O(NlogN) because we have used sorting.<\/li>
- Q.2: How do you remove duplicates from an unsorted array in place?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code For HashMaps<\/a><\/li>
- Java Implementation<\/a><\/li>
- Java Code<\/a><\/li>
- C\/C++ Code<\/a><\/li>
- Method – 1 (Using Sorting)<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-15.png\")
<\/figure><\/div>\n\n\n\n