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

Question

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 1

You can use this : https://www.php.net/manual/ro/function.max.php

$test = array(
           array('G', 'M', 2, 2),
           array(1, 2222, 3)
         );
 $arr = max($test);

// output ->

array(4) {
  [0]=>
  string(1) "G"
  [1]=>
  string(1) "M"
  [2]=>
  int(2)
  [3]=>
  int(2)
}

Answer 2

Not sure about the performance, but I think the following should work:

$count = array_map('count', $input_arr);
$min = array_keys($count , max($count))[0];
$largest_arr = $input_arr[$min];

Or even:

$counts = array_map('count', $input_arr);
$key = array_flip($counts)[max($counts)];
$largest_arr = $input_arr[$key];

Answer 3

1) Sort the multi-dim array by the element sizes:
Choose an algorithm that runs in O(n logn) worst case, e.g. Heap Sort (comparison of sorting algorithms).

2) Choose the last element.
This runs in O(1)

So if you implement the sorting algorithm yourself and assuming that fetching the array length is O(1) and not linear (no counting every time you ask for the length), you can do it in O(n logn)

I can't comment on any PHP methods which do this for you since I'm not using it.

Answer 4

Just for fun:

array_multisort($result = array_map('count', $array), SORT_DESC);
echo $result[0];

Answer 5

$max = 0;
foreach($array as $obj)
{
    if($obj->dnum > $max)
    {
        $max = $obj->dnum;
    }
}

or

$numbers = array();
foreach($array as $obj)
{
    $numbers[] = $obj->dnum;
}
$max = max($numbers);

or ...

Read more in that article - Get the maximum value from an element in a multidimensional array? or How to find the largest array from a multi dimensional array

Answer 6

How about this:

function accmp(&$a, &$b) {  return count($a)<count($b)?-1:1; }
$arraylist=array(array(1,2),array(1,2,3),array(1),array(1,2,3,4,5,6),array(1,2,3,4),array(2,3,4));
echo 'original arraylist:<br>'; print_r($arraylist); echo '<br>';
usort($arraylist,'accmp');
echo 'largest array::<br>'; print_r(end($arraylist)); echo '<br>';
echo 'largest size = '.count(end($arraylist))

Just sort array-element in arraylist in ascending order of count(array-element) and take last element.