PHP – Best Way to Compare Two Arrays

PHP Code Snippet

Recently while solving a challenge on HackerEarth, I had to find the intersection between two arrays. And to the best of my knowledge, I had used array_intersect – which is pretty much well known to all of us. However, it exceeds 5 seconds of computation time when the input is quite large. PHP arrays behave like hash-maps. Also, while searching for something in hash-maps, it’s hashes are used to find out if a value exists in the hash-table. Similarly, it’s faster to search for arrays using their keys.

This is one reason why isset/array_key_exists is much faster than in_array and array_search because the former uses array keys while the latter uses values to search. It was evident to me at this point of time that array_intersect wouldn’t work for my use case and hence I used array_intersect_key. Since I wanted to compare values instead of keys, I did an array_flip on both subjects and then applied array_intersect_key on them. Doing this solved my problem as most of the test cases were completed within 5 seconds.

Time Complexity of Array Intersection Functions

array_intersect_key if intersection 100% do O(Max(param_i_size)*∑param_i_count, for all i), if intersection 0% intersect O(∑param_i_size, for all i)

array_intersect if intersection 100% do O(n^2*∑param_i_count, for all i), if intersection 0% intersect O(n^2)

Note that array_intersect_key would fail in case you have duplicate values in an array.

Leave a Reply