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.

Solution 1

You can do:

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

Solution 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.

Solution 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.

Solution 4

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

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

Solution 5

$duplicate = false;

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

View more solutions

Comments

[Admin]

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

[Mala]

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

[Felix Kling]

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.

[Mike Sherov]

@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.

[Felix Kling]

@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.

[Mike Sherov]

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

[Mike Sherov]

@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.

[Mala]

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.

[Jason McCreary]

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?

[Mike Sherov]

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.

[Jason McCreary]

@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.

[Mike Sherov]

@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.

[Jason McCreary]

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.

[Jason McCreary]

@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.

[Mike Sherov]

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

[Artefacto]

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

[FabianoLothor]

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

[EleventyOne]

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; }

[Alan Turing]

@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.

[cartbeforehorse]

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.

[Gino Pane]

I came here only to find exactly this answer:)

[aksu]

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

[Nikunj Madhogaria]

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

[Tgr]

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.

[Salam.MSaif]

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

[Milania]

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.

[J. Murray]

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

[Erdal G.]

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)); }

[s3m3n]

@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.

[mickmackusa]

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.

[mickmackusa]

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

[mickmackusa]

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

[mickmackusa]

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

[mickmackusa]

This is pretty much a retread of @JasonMcCreary's answer. stackoverflow.com/a/3145647/2943403

[mickmackusa]

This is pretty much a retread of @JasonMcCreary's answer. stackoverflow.com/a/3145647/2943403

[mickmackusa]

This is pretty much a retread of @JasonMcCreary's answer. stackoverflow.com/a/3145647/2943403 I have voted to delete this post.

[Prasad Patel]

But It is throwing duplicate values error even when array has empty values. I have posted answer stackoverflow.com/questions/3145607/… below