How to Detect and Remove Duplicates in an Array

Duplicate problems come in different forms. Sometimes you need to simply check if any duplicate exists. Sometimes you need to remove all duplicates and return unique elements. Sometimes you need to remove duplicates in place without extra space. Each variation has a different optimal approach.

To check if any duplicate exists, create an empty Hash Set. Iterate through the array. For each element, check if it already exists in the Hash Set. If it does, you have found a duplicate and can return true immediately. If not, add it to the Hash Set and continue. If the loop finishes without finding a duplicate, return false.

To collect all unique elements, create an empty Hash Set and an empty result list. Iterate through the array. For each element, if it is not already in the Hash Set, add it to both the Hash Set and the result list. If it is already in the Hash Set, skip it. The result list contains all unique elements in their original order.

If the array is sorted, duplicates are always adjacent. Use two pointers. The slow pointer tracks the position of the last unique element written. The fast pointer scans through the array. Whenever the fast pointer finds an element different from the element at the slow pointer, increment the slow pointer and copy the new unique element there.

If the array is unsorted and you need to remove duplicates in place without a Hash Set, sort the array first. Sorting brings all duplicates next to each other. Then apply the two pointer technique described in the previous step. The trade-off is that the original order of elements is not preserved.

To find which specific elements are duplicates, use a Hash Map to count the frequency of each element. Iterate through the array once and increment the count for each element. Then iterate through the Hash Map and collect all elements whose count is greater than one. These are the duplicates.

For arrays containing values in a specific range like one to N, use the array itself as a frequency tracker. For each element, go to the index equal to the absolute value of the element and negate the value there. If you try to negate a value that is already negative, the corresponding element is a duplicate. This achieves duplicate detection without any extra data structure.