Finding Duplicates in an Array [Java Solution]

Repetition is something we want to avoid as much as possible, and doing the same thing over and over again gets tiring and boring. In programming, this is also a question of efficiency. You don’t want to repeat the same code all over the place, which is why functions exist. Similarly, if you have a list of items, you do not want duplicates because it becomes an unnecessarily long list.

Good Ol’ Days

In Java, the equivalent of a list would be an Array or an ArrayList. Most of the time, we do not want the items in a list to be repeated. Of course, there are exceptions; for instance, an Array can store a set of values, such as the ages of any group of people. Multiple people can have the same age, so we wouldn’t get rid of the duplicates if we want that data to be useful. Now, the problem with the matter is; What happens if we want to actually get rid of the duplicates or find if there are any duplicates in an Array? How can we do that?

The Problem at Hand

As an example, let’s use the following Array: [1, 2, 3, 1, 4, 5, 8, 6, 3]

The array above has two duplicates, numbers 1 and 3 appear twice in the array. We want to make an algorithm that finds either of these duplicates and returns true when it does.

There are multiple solutions, and here we are going to describe two of them. One will involve brute force and pure use of Arrays, while the other one will be more efficient, involving HashMaps.

Solution 1 — Brute Force

  public boolean containsDuplicate(int[] nums) {
      final int SIZE = nums.length;

      for(int i = 0; i < SIZE; i++) {
          for(int j = 0; j < SIZE; j++) {
            if(i != j) {
                if(nums[i] == nums[j]) {
                    return true;
                }
            }
          }
      }

      return false;
  }

// test input: int[] nums = {1, 2, 3, 1, 4, 5, 8, 6, 3}

The function in the code above will return either true if it can find a duplicate or false if it can’t. The primary data structure for this solution is the given input Array.

On the first line, we declare a constant variable that stores the length of the integer Array being passed to the function containsDuplicate. We use this variable to iterate through the same Array twice in a nested loop. A nested loop is like a ‘for’ loop inside another ‘for’ loop. The first loop goes from the first position to the last position on the Array nums. In other words, the first loop is going to run the code within it as long as the value of the variable i is less than the SIZE of the Array nums.

For each lap in the first loop, we do multiple laps on the second loop. For instance, when i=0 in the first loop, the second loop is going to run from j=0 to j=9 . Once the second lap, when i=1 , the second loop iterates again from j=0 to j=9. This means we are comparing each number in Array nums to the rest of the Array in each iteration.

For each outer loop iteration, we compare the value at position i to every value at position j in the inner loop.

If any number at position j is equal to the number at the position i then we can say we have found a duplicate, and we should return true. Otherwise, if we find no duplicates, then we return false when the loop is complete.

This solution would be O(N * N), aka O(N²). This is because we have nested loops that iterate or navigate the same input N times. The inner loop will navigate the Array numsN times every N times (each iteration of the outer loop); hence N * N.

Solution 2 —Using Hashmap

public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> numHistory = new HashMap<Integer, Integer>();

        for (int n : nums){
            if (!numHistory.containsKey(n)){
                numHistory.put(n, 1);
            }else{
                return true;
            }
        }

      return false;
  }

// test input: int[] nums = {1, 2, 3, 1, 4, 5, 8, 6, 3}

Unlike Arrays, hash maps allow us to add data more efficiently. When adding data to an Array, we can do it in constant time if we add it to the end of it. Nonetheless, suppose you want to insert some data in the middle or beginning of the Array. In that case, we cannot do so in constant time because we must copy the Array to a new place in memory where that new element can go in the middle or the beginning of it. The process of copying the Array to a new place in memory takes O(N) time, which is worse than constant time.

In this solution, we create a hash map called numHistory. A hash map is made of keys and values. Every key is going to have one value assigned to it. It would look something like this:

{
  "key_1": "some value",
  "key_2": "some value"
}

Each key name must be unique; however, their values do not have to be unique. A key name can be either a string or an integer value. In this problem, we use a hash map to store the visited numbers or the numbers we have already seen.

We then loop through the nums Array. For every element in the array, we check if there is a key n in our numHistory hash map. For example, in the first iteration of the for loop, n=1. If n is NOT in the hash map numHistory , then we put (create) a n key with an initial value of 1 in the numHistory hash map. Putting or adding something to a hash map takes a constant, O(1) time, on average. Else, if we can find a key n in the numHistory hash map, we immediately return true. Returning true immediately would terminate the loop before it can finish. This is because finding at least one duplicate satisfies the requirement.

Since we are only iterating the nums Array once, N times, our function runs in O(N) time.

Putting Everything Together

Both solutions solve the problem at hand just fine. Nonetheless, one solution takes more computer resources than the other one. The first solution is a good way to start solving this problem. We always have to start somewhere, and even if it is not the best solution, it solves the problem and allows you to work from there to improve it. We can only get to the second solution if you know what a hash map is. In this case, the only way to find out about the hash map is to look at others' solutions once you are done with your solution. Don’t get me wrong, brute force is a great start, but it is not a good enough end. Google is your friend. If you know how to google, you will find yourself those “Aha!” moments you need.

Clap and comment if you liked it! Suggestions and corrections are always welcomed!