Scott Arciszewski Scott Arciszewski - 1 month ago 10
PHP Question

Quick Way to Find the Largest Array in a Multidimensional Array?

Situation: I have a multidimensional array with a variable number of elements. e.g.

array(N) {
0 => array(3) { ... },
1 => array(8) { ... },
2 => array(1) { ... },
...
M => array(12) { ... },
...
N-1 => array(7) { ... }
}


And I would like to find the maximum number of elements in this sub-array (in the example above, it would be 12). A straightforward solution would be an O(N) linear search.

<?php
function max_length($2d_array) {
$max = 0;
foreach($2d_array as $child) {
if(count($child) > $max) {
$max = count($child);
}
}
return $max;
}


However, I can't help but wonder if there's some clever trick to optimize this lookup. So my question is a two-parter (though an answer to either part would solve it):


  • Is there an algorithm that performs this search faster than O(N) without requiring special requirements (pre-sorted, etc)?

  • Is there an obscure PHP function somewhere that will perform this search in native code rather than my userland PHP script?


Answer

Okay, @DefuseSec on Twitter had this to say:

https://twitter.com/DefuseSec/status/435842054195671040

I'm inclined to believe that's the answer to this question.