Main Tutorials

Java – Check if array contains duplicated value

This article shows a few ways to detect if an array contains a duplicated value.

  1. Java 8 Stream, compare the array size.
  2. TreeSet, compare the array size.
  3. Two for loops, classic algorithm, 0(n^2).
  4. Set, 0(n).
  5. Bitmap, boolean[] 0(n).

All the above solutions are tested with the below program and generate the same output. (except 5. Bitmap)

CheckDuplicateArray.java

package com.mkyong.basic;

import java.util.Arrays;

public class CheckDuplicateArray {

    public static void main(String args[]) {

        String[] sValueDuplicated = new String[]{"a", "b", "c", "d", "1", "e", "f", "1", "4", "z"};
        Integer[] iValueDuplicated = new Integer[]{2, 3, 1, 4, 99, 2, 9, 7, 88, 2};
        Integer[] iValuesUnique = new Integer[]{2, 3, 1, 4, 99, 5, 6, 7, 88, 9};

        System.out.println(isDuplicate(sValueDuplicated));    // true
        System.out.println(isDuplicate(iValueDuplicated));    // true
        System.out.println(isDuplicate(iValuesUnique));       // false

    }

    // public static <T> boolean isDuplicate(final T[] values) {}

}

Output

Terminal

  true
  true
  false

1. Java 8 Stream – distinct() + count()

The Java 8 stream’s distinct() method will extract all the unique values, and the count() will count the total size. And we can compare the size to find out if there is a duplicated value in an array.


  // Java 8 stream
  public static <T> boolean isDuplicate(final T[] values) {
      return Arrays.stream(values).distinct().count() != values.length;
  }

2. TreeSet

This example is similar to the above stream distinct solution. The TreeSet will automatically remove the duplicated values, and we can compare the size to find out if there is a duplicated value in an array.


  // TreeSet will remove the duplicated values
  public static <T> boolean isDuplicate(final T[] values) {

      TreeSet set = new TreeSet<T>(Arrays.asList(values));
      if (set.size() != values.length) {
          return true;
      } else {
          return false;
      }

  }

3. Two for loops

A 0(n^2) algorithm to find out the duplicated values. This example is a classic two for loops to determine if there is a duplicated value in an array.


  // O(n^2), increase time if array size increased
  public static <T> boolean isDuplicate(final T[] values) {

      for (int i = 0; i < values.length; i++) {
          for (int j = 0; j < values.length; j++) {
              if (i == j) continue; //same index position, ignore
              if (values instanceof String[]) {
                  if (values[i].equals(values[j])) {
                      return true;
                  }
              } else {
                  if (values[i] == values[j]) {
                      return true;
                  }
              }
          }
      }
      return false;

  }

4. Set

A 0(n) algorithm to find out the duplicated values. Loops the array; if the Set contains the value, return true for duplication. Otherwise, add the value to the Set.


  // O(n), faster
  public static <T> boolean isDuplicate(final T[] values) {
      Set set = new HashSet<T>();
      for (T s : values) {
          if (set.contains(s)) return true;
          set.add(s);
      }
      return false;
  }

5. Bitmap

A 0(n) algorithm to find out the duplicated values. This example only works for int or Integer type, and only if we know the max range of an array.


  // O(n), if you know the max range, try this, super fast
  public static boolean isDuplicate(final int[] values) {
      // range from 0 - 9999 + 1
      final int max = 9999;
      boolean[] bitmap = new boolean[max + 1];
      for (int item : values) {
          if (bitmap[item]) {
              return true;
          } else {
              bitmap[item] = true;
          }
      }
      return false;
  }

Explanation
Assume the int[] is from range 0 to 10, and we can create a boolean[] with a size of 10 + 1.


  int[] values = new int[]{2, 3, 6, 4, 2, 9};
  boolean[] bitmap = new boolean[10 + 1];  // index starts at 0

Initial all bitmap[0-10] to false. (default)


bitmap[0]   = false;
bitmap[1]   = false;
bitmap[2]   = false;
bitmap[3]   = false;
bitmap[4]   = false;
bitmap[5]   = false;
bitmap[6]   = false;
bitmap[7]   = false;
bitmap[8]   = false;
bitmap[9]   = false;
bitmap[10]  = false;

loop #1, new int[]{2, 3, 6, 4, 2, 9}, update bitmap[2] = true


bitmap[0]   = false;
bitmap[1]   = false;
bitmap[2]   = true;
bitmap[3]   = false;
bitmap[4]   = false;
bitmap[5]   = false;
bitmap[6]   = false;
bitmap[7]   = false;
bitmap[8]   = false;
bitmap[9]   = false;
bitmap[10]  = false;

loop #2, new int[]{2, 3, 6, 4, 2, 9}, update bitmap[3] = true


bitmap[0]   = false;
bitmap[1]   = false;
bitmap[2]   = true;
bitmap[3]   = true;
bitmap[4]   = false;
bitmap[5]   = false;
bitmap[6]   = false;
bitmap[7]   = false;
bitmap[8]   = false;
bitmap[9]   = false;
bitmap[10]  = false;

loop #3, new int[]{2, 3, 6, 4, 2, 9}, update bitmap[6] = true


bitmap[0]   = false;
bitmap[1]   = false;
bitmap[2]   = true;
bitmap[3]   = true;
bitmap[4]   = false;
bitmap[5]   = false;
bitmap[6]   = true;
bitmap[7]   = false;
bitmap[8]   = false;
bitmap[9]   = false;
bitmap[10]  = false;

loop #4, new int[]{2, 3, 6, 4, 2, 9}, update bitmap[4] = true


bitmap[0]   = false;
bitmap[1]   = false;
bitmap[2]   = true;
bitmap[3]   = true;
bitmap[4]   = true;
bitmap[5]   = false;
bitmap[6]   = true;
bitmap[7]   = false;
bitmap[8]   = false;
bitmap[9]   = false;
bitmap[10]  = false;

loop #5, new int[]{2, 3, 6, 4, 2, 9}, update bitmap[2] = true, wait, the bitmap[2] is already true, meaning this array contains duplicated value.


bitmap[0]   = false;
bitmap[1]   = false;
bitmap[2]   = true;
bitmap[3]   = true;
bitmap[4]   = true;
bitmap[5]   = false;
bitmap[6]   = true;
bitmap[7]   = false;
bitmap[8]   = false;
bitmap[9]   = false;
bitmap[10]  = false;

Download Source Code

References

About Author

author image
Founder of Mkyong.com, love Java and open source stuff. Follow him on Twitter. If you like my tutorials, consider make a donation to these charities.

Comments

Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments