# Detecting duplicates

Detecting duplicates is part of a collection of standard algorithms.

Detecting duplicates means determining if an array contains at least one value more than once.

## Unsorted array

For an array not known to be sorted, each value is checked against each subsequent value.

### Algorithm

``````Loop through every value, excluding the last.
Loop through every value after the value from the outer loop.
If the values match
Return true.

Return false.
``````

### Implementation in Java

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

return false;
}
``````

Skipping the last element in the outer loop is not strictly required. If the outer loop is allowed to run up to and including the last element, the inner loop will not run when the outer loop visits the last element.

The inner loop cannot skip the last element.

### Alternate algorithm

``````Loop through every value.
Loop through every value.
If the indexes are different and the values match
Return true.

Return false.
``````

### Alternate implementation

``````public static boolean hasDuplicate(int[] vals)
{
for(int i = 0; i < vals.length; i++)
{
for(int j = 0; j < vals.length; j++)
{
if(i != j && vals[i] == vals[j])
return true;
}
}

return false;
}
``````

As in the previous algorithm, the outer loop can skip the last element if desired. The inner loop cannot skip the last element.

## Sorted array

If an array is known to be sorted, detecting duplicates can be done more easily and much more efficiently.

The sort order (ascending vs descending) doesn’t matter. Duplicate values will be in adjacent positions in the array. The algorithm works as long as all duplicate values are adjacent, regardless of whether the values are actuall in order.

### Algorithm

``````Loop through the array, excluding the first value.
If the current value matches the value immediately before it
Return true.

Return false.
``````

### Implementation in Java

``````public static boolean hasDuplicateSorted(int[] vals)
{
for(int i = 1; i < vals.length; i++)
{
if(vals[i - 1] == vals[i])
return true;
}

return false;
}
``````

When skipping one or more elements, my preference is to start the loop later rather than end it earlier. This avoids the somewhat odd condition `i < vals.length - 1` in the alternate solution below.

### Alternate loop

``````public static boolean hasDuplicateSorted(int[] vals)
{
for(int i = 0; i < vals.length - 1; i++)
{
if(vals[i] == vals[i + 1])
return true;
}

return false;
}
``````

Some programmers prefer to skip the last value instead of the first. In this case, the values at indexes `i` and `i + 1` are checked.