Find Duplicate Elements in an Array

Have you ever found yourself looking for a missing sock in a pile of laundry, only to find two socks that look exactly the same? It’s a common experience, but it’s also a perfect example of finding duplicates in a real-world situation. Just like in a pile of laundry, duplicates can appear in other places too, like in lists of numbers or arrays.

Take a moment to think about a story from the life of Richard Branson, the founder of Virgin Group. He faced countless obstacles and failures, but he never gave up. He kept searching for solutions, just like we search for that missing sock. In programming, finding duplicates in an array is like solving one of those small but important problems. It might seem simple, but it’s a crucial step in organizing and understanding data.

So, how do we find duplicates in an array? Let’s dive into this interesting problem and explore different ways to solve it.

Problem statement

You’re given an array, a list of numbers. Some numbers might appear more than once. Your task is to identify and return those duplicate numbers.

Sample input

1[1, 2, 3, 4, 5, 3, 2, 1]

Sample output

1[1, 2, 3]

Explanation:
In this example, the numbers 1, 2, and 3 appear more than once in the array. These are the duplicates, and they need to be identified and returned.

Understanding the problem

At first glance, the problem might seem straightforward. However, it’s essential to think about how we can approach it in the most efficient way. Imagine if you had a huge pile of laundry and needed to find every duplicate sock. You wouldn’t want to go through the pile over and over again. Similarly, in programming, we aim to find a solution that avoids unnecessary work.

Brute force approach

The simplest way to find duplicates is to compare each element with every other element in the array. If you find two elements that are the same, you’ve found a duplicate! This method works, but it’s not very efficient, especially if the array is large.

Pseudocode

Let’s break down the solution in a simple way that even beginners can follow. Here’s the pseudocode in plain English:

• Create an empty set to store unique numbers.
• Create an empty list to store duplicate numbers.
• For each number in the array:
  • If the number is already in the set, add it to the list of duplicates.
  • If the number is not in the set, add it to the set.
• Return the list of duplicates.

This pseudocode captures the essence of the problem and outlines a clear path to the solution.

Python code

Let’s start with the most straightforward approach, where we compare each element with every other element.

1def find_duplicates(arr):
2    duplicates = []
3    n = len(arr)
4    
5    for i in range(n):
6        for j in range(i + 1, n):
7            if arr[i] == arr[j] and arr[i] not in duplicates:
8                duplicates.append(arr[i])
9    
10    return duplicates

Explanation

• We loop through each element in the array using two loops.
• The outer loop picks each element, and the inner loop compares it with every other element.
• If a match is found and it’s not already in the duplicates list, we add it.
• Finally, we return the list of duplicates.

Java code

1import java.util.*;
2
3public class FindDuplicates {
4    public static List<Integer> findDuplicates(int[] arr) {
5        List<Integer> duplicates = new ArrayList<>();
6        int n = arr.length;
7        
8        for (int i = 0; i < n; i++) {
9            for (int j = i + 1; j < n; j++) {
10                if (arr[i] == arr[j] && !duplicates.contains(arr[i])) {
11                    duplicates.add(arr[i]);
12                }
13            }
14        }
15        
16        return duplicates;
17    }
18}

C++ code

1#include <vector>
2
3std::vector<int> findDuplicates(std::vector<int>& arr) {
4    std::vector<int> duplicates;
5    int n = arr.size();
6    
7    for (int i = 0; i < n; i++) {
8        for (int j = i + 1; j < n; j++) {
9            if (arr[i] == arr[j] && std::find(duplicates.begin(), duplicates.end(), arr[i]) == duplicates.end()) {
10                duplicates.push_back(arr[i]);
11            }
12        }
13    }
14    
15    return duplicates;
16}

A smarter approach

A smarter way is to use a "set." In programming, a set is a collection of unique elements. You can use a set to keep track of the numbers you’ve seen as you go through the array. If you come across a number that’s already in the set, you’ve found a duplicate!

This approach is much more efficient because you only need to go through the array once, and you can immediately identify duplicates.

Now, let’s improve the solution using the set-based approach, which is more efficient.

Python code

1def find_duplicates(arr):
2    seen = set()
3    duplicates = []
4    
5    for num in arr:
6        if num in seen:
7            if num not in duplicates:
8                duplicates.append(num)
9        else:
10            seen.add(num)
11    
12    return duplicates

Explanation

• We use a set called seen to keep track of numbers we’ve encountered.
• As we go through the array, if a number is already in seen, we add it to duplicates (if it’s not already there).
• If it’s not in seen, we add it to seen.
• This method ensures we only pass through the array once, making it efficient.

Java code

1import java.util.*;
2
3public class FindDuplicates {
4    public static List<Integer> findDuplicates(int[] arr) {
5        Set<Integer> seen = new HashSet<>();
6        List<Integer> duplicates = new ArrayList<>();
7        
8        for (int num : arr) {
9            if (seen.contains(num)) {
10                if (!duplicates.contains(num)) {
11                    duplicates.add(num);
12                }
13            } else {
14                seen.add(num);
15            }
16        }
17        
18        return duplicates;
19    }
20}

C++ code

1#include <unordered_set>
2#include <vector>
3
4std::vector<int> findDuplicates(std::vector<int>& arr) {
5    std::unordered_set<int> seen;
6    std::vector<int> duplicates;
7    
8    for (int num : arr) {
9        if (seen.find(num) != seen.end()) {
10            if (std::find(duplicates.begin(), duplicates.end(), num) == duplicates.end()) {
11                duplicates.push_back(num);
12            }
13        } else {
14            seen.insert(num);
15        }
16    }
17    
18    return duplicates;
19}

Conclusion

Finding duplicate elements in an array might seem like a simple problem, but it teaches us valuable lessons about efficiency and problem-solving. Just like Richard Branson overcame challenges by finding smart solutions, you can also tackle programming problems with the right approach.

Whether you choose a brute force method or a more efficient one, understanding the problem and planning your solution is key. Remember, the goal is not just to solve the problem but to do it in the best way possible.

In the end, programming is about practice and patience. The more you practice, the better you’ll become at finding smart solutions to complex problems.