php: check if an array has duplicates

Question

I'm sure this is an extremely obvious question, and that there's a function that does exactly this, but I can't seem to find it. In PHP, I'd like to know if my array has duplicates in it, as efficiently as possible. I don't want to remove them like array_unique does, and I don't particularly want to run array_unique and compare it to the original array to see if they're the same, as this seems very inefficient. As far as performance is concerned, the "expected condition" is that the array has no duplicates.

I'd just like to be able to do something like

if (no_dupes($array))
    // this deals with arrays without duplicates
else
    // this deals with arrays with duplicates

Is there any obvious function I'm not thinking of?
How to detect duplicate values in PHP array?
has the right title, and is a very similar question, however if you actually read the question, he's looking for array_count_values.

Juanajuanita

Do you just want to know if there are any duplicates or the quantity and value of said duplicates etc? – That

I only need to know if there are any duplicates. Returning a boolean is perfect. – Juanajuanita

Honestly I think if(count($array) == count(array_unique($array))) is the best you can get. You have to traverse the array this way or another and I think the built-in are optimized for that. array_flip could be considered too. – Badajoz

@Felix, you can do better than that. That does three loops, one to create the unique array, one to count it, and one to count the original. – Nunez

@Mike Sherov: Are you sure? I couldn't find anything about it, but I had hoped that PHP arrays have some internal property that keeps track of the length. Do you have an information about this? I would be very interested. – Badajoz

@Felix, I was always taught that count was an expensive operation in PHP, and that it required looping through. Maybe that's wrong. – Nunez

@Felix, have a look at these: maettig.com/code/php/php-performance-benchmarks.php josephscott.org/archives/2010/01/php-count-performance mikegerwitz.com/2010/03/28/php-performance-array-iteration I'm not really sure where that leaves us. Yes, doing count() multiples times is slow, but it may well be faster than my answer. – Nunez

Answer 1

You can do:

function has_dupes($array) {
    $dupe_array = array();
    foreach ($array as $val) {
        if (++$dupe_array[$val] > 1) {
            return true;
        }
    }
    return false;
}

Nunez

I like it! Just keep in mind that even with an early return this is an O(n) function. In addition to the overhead of foreach and tracking $dupe_array, I'd love to see some benchmarking. I'd guess for array's with no duplicates, utilizing native functions is faster. Definitely better than O(n^2) though. Nice. – Torrance

Has a little problem: only works correctly if the values are strings or numbers. – Coachwhip

This code gave me an undefined offset error in PHP. Instead, I did: foreach ( $a as $v ) { if ( array_key_exists($v,$dupe) { return true; } else { $dupe[$v] = true; } – Haemostat

How does this even work? Since $dupe_array has not been defined with any values, $dupe_array[$val] should return an undefined index! – Breathe

what does ++dupe_array[$val] means? and isn't it suppose to be ++dupe_arrays[$key] because simply $val is not $key? – Silden

The idea behind ++dupe_array[$val] is to count how often each array value appears. But since the values are not initialized, this does not work without notices (in PHP 7.1). However, if you want to keep the counting behaviour, you can fix the code by adding if (!isset($dupe_array[$val])) {$dupe_array[$val] = 0} before the current if-block. – Andalusite

Answer 2

I know you are not after array_unique(). However, you will not find a magical obvious function nor will writing one be faster than making use of the native functions.

I propose:

function array_has_dupes($array) {
   // streamline per @Felix
   return count($array) !== count(array_unique($array));
}

Adjust the second parameter of array_unique() to meet your comparison needs.

Torrance

thanks for the suggestion. My thought at finding a better algorithm is simply that, technically speaking, once you've finished running whatever the builtin array_unique does, you should be able to know if there were any dupes. Thus, anything that does at least as much work as array_unique does more work than necessary. Although yeah, if such a function doesn't exist, I don't particularly feel like writing it. – Juanajuanita

If you only care about if it has dupes, then that's what I would do. If you care about more than just if it has dupes, then you're right, the above may do more work than it needs. Anything you write is going to be O(n^2). Even if you bail out early. As you said, it's not common that you have dupes. So is it worth your time to make something magical? – Torrance

Magical? Sure it's a microoptimization, but it's not "magic" to write your own function, and I'm not sure it's that a better solution is that much harder to write than this. – Nunez

@Mike, never said anything of the sort. Just questioning if it was worth the developer's time in this particular instance based on the specification of the original question. No worries. – Torrance

@Jason, I wasn't trying to come off harsh. I was just trying to convey that it doesn't always hurt to seek your own solution when you already know the easy way. – Nunez

@Mike. Agreed. And ultimately it's how we all get better. I was just devil's advocate, in this case, saying that there's nothing wrong with the easy way. – Torrance

@Jason, yup. I too have been bitten before by premature optimization. – Nunez

@JasonMcCreary I think you meant to say O(n log n) as the simple solution is just sort the array which is O(n log n) and then run through it once to find duplicates. – Leonhard

I came here only to find exactly this answer:) – Corrida

You should give us some clue what the second parameter does. – Maihem

Elegant, but array_unique is somewhat slow. If you know the array to only contain integers and strings, you can replace it with array_flip for much faster results. – Memory

Answer 3

Performance-Optimized Solution

If you care about performance and micro-optimizations, check this one-liner:

function no_dupes(array $input_array) {
    return count($input_array) === count(array_flip($input_array));
}

Description:
Function compares number of array elements in $input_array with array_flip'ed elements. Values become keys and guess what - keys must be unique in associative arrays so not unique values are lost and final number of elements is lower than original.

Warning:
As noted in the manual, array keys can be only type of int or string so this is what you must have in original array values to compare, otherwise PHP will start casting with unexpected results. See https://3v4l.org/7bRXI for an example of this fringe-case failure mode.

Proof for an array with 10 million records:

• The top-voted solution by Jason McCreary: 14.187316179276s 🐌🐌🐌🐌🐌🐌🐌🐌🐌🐌🐌🐌🐌🐌
• The accepted solution by Mike Sherov: 2.0736091136932s 🐌🐌
• This answer's solution: 0.14155888557434s 🐌/10

Test case:

<?php

$elements = array_merge(range(1,10000000),[1]);

$time = microtime(true);
accepted_solution($elements);
echo 'Accepted solution: ', (microtime(true) - $time), 's', PHP_EOL;

$time = microtime(true);
most_voted_solution($elements);
echo 'Most voted solution: ', (microtime(true) - $time), 's', PHP_EOL;

$time = microtime(true);
this_answer_solution($elements);
echo 'This answer solution: ', (microtime(true) - $time), 's', PHP_EOL;

function accepted_solution($array){
 $dupe_array = array();
 foreach($array as $val){
  // sorry, but I had to add below line to remove millions of notices
  if(!isset($dupe_array[$val])){$dupe_array[$val]=0;}
  if(++$dupe_array[$val] > 1){
   return true;
  }
 }
 return false;
}

function most_voted_solution($array) {
   return count($array) !== count(array_unique($array));
}

function this_answer_solution(array $input_array) {
    return count($input_array) === count(array_flip($input_array));
}

Notice that accepted solution might be faster in certain condition when not unique values are near the beginning of huge array.

Communard

Can you explain why is this faster? Also this returns the contrary. So to have a fair comparison you should test with : function most_voted_solution($array) { return count($array) === count(array_unique($array)); } – Alvord

@ErdalG. this is faster because array_flip is native PHP function written in C and flip is pretty simple operation. After flipping not unique values are removed as they could create array key conflict. – Communard

Answer 4

$hasDuplicates = count($array) > count(array_unique($array)); 

Will be true if duplicates, or false if no duplicates.

Wenz

This is pretty much a retread of @JasonMcCreary's answer. https://mcmap.net/q/224597/-php-check-if-an-array-has-duplicates – Taut

But It is throwing duplicate values error even when array has empty values. I have posted answer #3146107 below – Deltoro

Answer 5

$duplicate = false;

 if(count(array) != count(array_unique(array))){
   $duplicate = true;
}

Gignac

This is pretty much a retread of @JasonMcCreary's answer. https://mcmap.net/q/224597/-php-check-if-an-array-has-duplicates – Taut

Answer 6

Here's my take on this… after some benchmarking, I found this to be the fastest method for this.

function has_duplicates( $array ) {
    return count( array_keys( array_flip( $array ) ) ) !== count( $array );
}

…or depending on circumstances this could be marginally faster.

function has_duplicates( $array ) {
    $array = array_count_values( $array );
    rsort( $array );
    return $array[0] > 1;
}

Anima

Not sure why you need array_keys() in your answer. array_flip() already condenses your array if the values are the same. Also, != is a sufficient compararor, since the types are inherently the same out of count() (you're the one that mentioned benchmarking). Therefore return count(array_flip($arr)) != count($arr); should be sufficient. – Save

The techniques in this answer have the same vulnerabilities as @s3m3n's function. 3v4l.org/3FlBJ This is an "apples-vs-oranges" comparison, so I'll argue that any benchmark comparisons are inappropriate because the function do not offer identical behavior. – Taut

Answer 7

To remove all the empty values from the comparison you can add array_diff()

if (count(array_unique(array_diff($array,array("")))) < count(array_diff($array,array(""))))

Reference taken from @AndreKR answer from here

Deltoro

Answer 8

Two ways to do it efficiently that I can think of:

1. inserting all the values into some sort of hashtable and checking whether the value you're inserting is already in it(expected O(n) time and O(n) space)

2. sorting the array and then checking whether adjacent cells are equal( O(nlogn) time and O(1) or O(n) space depending on the sorting algorithm)

stormdrain's solution would probably be O(n^2), as would any solution which involves scanning the array for each element searching for a duplicate

Tswana

Answer 9

Keep it simple, silly! ;)

Simple OR logic...

function checkDuplicatesInArray($array){
    $duplicates=FALSE;
    foreach($array as $k=>$i){
        if(!isset($value_{$i})){
            $value_{$i}=TRUE;
        }
        else{
            $duplicates|=TRUE;          
        }
    }
    return ($duplicates);
}

Regards!

Dipteral

#BadCode - The best ways to do this check with functions of PHP itself. – Pressurize

I find variable variables to generally unattractive solution. This technique may fail in certain scenarios. 3v4l.org/kGLWT Moreso, from PHP7.4 and up. – Taut

Answer 10

Find this useful solution

function get_duplicates( $array ) {
    return array_unique( array_diff_assoc( $array, array_unique( $array ) ) );
}

After that count result if greater than 0 than duplicates else unique.

Yeo

Despite being a one-liner, this technique appears to be doing more processing than other posted answers. To check if an array is empty without calling count(), just do a falsey check using !: 3v4l.org/O4g3F – Taut

Answer 11

I'm using this:

if(count($array)==count(array_count_values($array))){
    echo("all values are unique");
}else{
    echo("there's dupe values");
}

I don't know if it's the fastest but works pretty good so far

Sorilda

Some data types will cause this technique to fail, so this is not a reliable/robust solution. 3v4l.org/FSr7P – Taut

Answer 12

One more solution from me, this is related to performance improvement

$array_count_values = array_count_values($array);
if(is_array($array_count_values) && count($array_count_values)>0)
{
   foreach ($array_count_values as $key => $value)
   {
      if($value>1)
      {
        // duplicate values found here, write code to handle duplicate values            
      }
   }
}

Deltoro

Answer 13

The shortest one

function no_dupes($array) {
    return $array === array_unique($array);
}

Eskilstuna

Answer 14

As you specifically said you didn't want to use array_unique I'm going to ignore the other answers despite the fact they're probably better.

Why don't you use array_count_values() and then check if the resulting array has any value greater than 1?

That

Answer 15

Php has an function to count the occurrences in the array http://www.php.net/manual/en/function.array-count-values.php

Accession

Answer 16

You can do it like that way also: This will return true if unique else return false.

$nofollow = (count($modelIdArr) !== count(array_unique($modelIdArr))) ? true : false;

Dael

This is pretty much a retread of @JasonMcCreary's answer. https://mcmap.net/q/224597/-php-check-if-an-array-has-duplicates I have voted to delete this post. – Taut

Answer 17

The simple solution but quite faster.

$elements = array_merge(range(1,10000000),[1]);

function unique_val_inArray($arr) {
    $count = count($arr);
    foreach ($arr as $i_1 => $value) {
        for($i_2 = $i_1 + 1; $i_2 < $count; $i_2++) {
            if($arr[$i_2] === $arr[$i_1]){
                return false;
            }
        }
    }
    return true;
}

$time = microtime(true);
unique_val_inArray($elements);
echo 'This solution: ', (microtime(true) - $time), 's', PHP_EOL;

Speed - [0.71]!

Telson

Answer 18

function hasDuplicate($array){
  $d = array();
  foreach($array as $elements) {
    if(!isset($d[$elements])){
      $d[$elements] = 1;
    }else{
      return true;
    } 
  } 
  return false;
}

Aphrodisia

Where is the explanation of what this source code will accomplish? – Candlewick