Checking whether an array contains all distinct values

Question

This method returns true if any arrays element is equal to another element value, returns False otherwise.

public static boolean distinctValues(int[] tmp){
 for (int i = tmp.length - 1; i > 0; i--) {
 for (int j = 1; j < i; j++) {
 System.out.println(j + ". " + tmp[i] + " and " + tmp[j] +
 " are " + (tmp[i] == tmp[j] ? "equal" : "not equal"));
 if (tmp[i] == tmp[j]) {
 return true;
 }
 }
 } 
 return false; 
}

Do You think its efficient and/or readable way to implement this?
If not, what would You suggest?

• hahn: your algorithm is O(n^2). i think you could sort (av. O(n log(n)) and then go through an array checking current prev values, whether they are equals

Answer 1

Naming

tmp isn't the best names for the parameter because is not actually temporary - any changes made to the array inside that method will be reflected in the array outside the method. A better name would be nums or something similar.

A method called distinctValues should not return true when there are duplicates so, the return statements should be swapped.

Convention

Instead of starting at arr.length - 1 and moving towards 0, a more common pattern for iterating over elements in a list in Java is starting at 0 and moving towards arr.length - 1:

for(int i=0; i < arr.length; i++){

in cases where you don't need to know what index you are currently examining and you do not need to modify the array it's prefered to use a for-each loop

for(int n : arr){

Algorithm

Your current algorithm works in O(n²) worst case. This can trivially be made to be O(n) at the cost of some memory using the algorithm described in this StackOverflow answer.

---

After the convention and naming changes above, your original code should look like this:

public static boolean distinctValues(int[] arr){
 for (int i = 0 i < arr.length-1; i++) {
 for (int j = i+1; j < arr.length; j++) {
 if (arr[i] == arr[j]) {
 return false;
 }
 }
 } 
 return true; 
}

and after implementing the new algorithm:

import java.util.Set;
import java.util.HashSet;
public static boolean distinctValues(int[] arr){
 Set<Integer> foundNumbers = new HashSet<Integer>();
 for (int num : arr) {
 if(foundNumbers.contains(num)){
 return false;
 }
 foundNumbers.add(num);
 } 
 return true; 
}

_{I originally used a BitSet instead of a HashSet. While BitSet is generally more efficient, it does not support negative values. If you can guarantee that no values in the array will be negative, BitSet is still the better option.}

Generalization

If this is for an assignment that asks for this to be implemented for an int[], you can ignore this part but, it's always good to generalize methods as much as possible. In this case int[] can be generalized to Iterable<Object>. The downside of this is that you can't call it on an Array and more; you have to first do Arrays.asList(arr)

public static boolean distinctValues(Iterable<Object> objs){
 Set<Object> foundObjects = new HashSet<>();
 for(Object o : objs){
 if(foundObjects.contains(o)){
 return false;
 }
 foundObjects.add(o);
 }
 return true; 
}

• froginvasion: This made me think about another solution. When using Guava (and I suppose other utility frameworks also support this) you can just do the following: Set s = Sets.newHashSet(yourList) and then compare the size of the set and the list.

Answer 2

Bug

First of all, you have a bug (off-by-one error) here:

for (int i = tmp.length - 1; i > 0; i--) {
 for (int j = 1; j < i; j++) {

Because j starts from 1, the first element will never be checked. For example, these test cases fail:

@Test
public void test_1_1_2_3_4() {
 int[] arr = {1, 1, 2, 3, 4};
 assertTrue(distinctValues(arr));
}
@Test
public void test_1_1() {
 int[] arr = {1, 1};
 assertTrue(distinctValues(arr));
}

The fix is simple, start j from 0:

for (int i = tmp.length - 1; i > 0; i--) {
 for (int j = 0; j < i; j++) {

Naming

My first guess from the method name was that a return value of true means the values are distinct = all unique. But that's not the case. The method returns true of there are duplicates, false if there are no duplicates.

It would be better to flip the return values. (Swap the return true and return false statements.)

The method parameter variable tmp is poorly named. Even arr would be better.

Readability

I don't find this jumble particularly easy to read:

System.out.println(j + ". " + tmp[i] + " and " + tmp[j] +
 " are " + (tmp[i] == tmp[j] ? "equal" : "not equal"));

This seems a little bit better:

String equalOrNot = tmp[i] == tmp[j] ? "equal" : "not equal";
System.out.printf(
 "%d. %d and %d are %s\n",
 j, tmp[i], tmp[j], equalOrNot
);

In any case, printing doesn't really belong in methods like this.

Answer 3

I would suggest favouring readability/brevity first. Optimizing only when needed.

A concise way (Java 8), but not optimal at performance-sight:

public static boolean distinctValues(int[] tmp) {
 return tmp.length == IntStream.of(tmp).boxed().collect(Collectors.toSet()).size();
 }

• abuzittin gillifirca: You could use use new HashSet<> instead of new HashSet<Object>, Collectors.toSet() instead of Collectors.toList, .size() could be chained after .collect(...).
• Spotted: @abuzittingillifirca you are right ! I updated my answer.

Answer 4

For better performance (not square time consuming) sort your array first and loop simply once over

package com.stackexchange.codereview;
import java.util.Arrays;
public class CheckAllArrayValuesAreDistinct {
 public static boolean allArrayValuesAreDistinct(final int[] arr) {
 // clone array to avoid unwanted changes
 int[] clone = arr.clone();
 // sort the array
 Arrays.sort(clone);
 // search for a pair of equal values
 for (int i = 0; i < clone.length - 1; i++) {
 if (clone[i] == clone[i + 1]) {
 return false;
 }
 }
 return true;
 }
}

Here a little not complete JUnit4 test case

package com.stackexchange.codereview;
import static org.junit.Assert.*;
import org.junit.Test;
public class CheckAllArrayValuesAreDistinctTest {
 @Test
 public void testAllArrayValuesAreDistinctPositive() {
 assertTrue(
 CheckAllArrayValuesAreDistinct.allArrayValuesAreDistinct(
 new int[]{ 0, 1, 2 } ));
 }
 @Test
 public void testAllArrayValuesAreDistinctNegative() {
 assertFalse(
 CheckAllArrayValuesAreDistinct.allArrayValuesAreDistinct(
 new int[]{ 0, 0, 1 } ));
 }
}

To complete the code and the test note zero and empty arrays, Pairs at start end and of array and different values