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
array_key_exists is much faster than
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)
array_intersect_key would fail in case you have duplicate values in an array.