Most efficient way of detecting and removing elements in array based on elements' first and last value

Question

I want to remove rows from my array so that my result is an array that contains rows with unique first and last elements. If two (or more) rows have the same first and last value, I want to preserve the row with the lowest element count.

Say I have the following array:

$var = [
    [1, 2, 3],
    [1, 3],
    [1, 2, 4, 3],
    [1, 3, 4]
];

What I want is to remove all arrays from $var that have the first and last element the same as another array from $var but have more elements.

Because the first three rows all start with 1 and end with 3, only the second row containing [1, 3] should be kept.

The fourth row ([1, 3, 4]) uniquely starts with 1 and ends with 4, so it should also be kept.

The output should be:

[
    [1, 3],
    [1, 3, 4]
]

I am looking for the most efficient way of doing this, both in terms of memory and time. $var may have up to 100 arrays, and each individual array may have up to 10 elements in it. I thought of using some kind of comparison between all two elements (for(i=0;...) for(j=i+1;...) complexCompareFunction();), but I believe this isn't very efficient.

Answer 1

use current and end

$all = array();
foreach ($var as $idx=>$arr):
  $first = current($arr);
  $last  = end($arr);
  $size  = count($arr);
  $key   = $first.'.'.$last;
  if (isset($all[$key])):
    if ($size > $all[$key]):
      unset($var[$idx]);
    else:
      $all[$key] = $size;
    endif;
  else:
    $all[$key] = $size;
  endif;
endforeach;

ops ... you can iterate (again) at the end to ensure the already reduced sized array can be further removed

Answer 2

In general, yes, you are too worried about efficiency (as you wondered in another comment). Though PHP is not the most blisteringly-fast language, I would suggest building the most straightforward solution, and only worry about optimizing it or streamlining it if there is a noticeable issue with the end result.

Here is what I would do, off the top of my head. It is based off of ajreal's answer but hopefully will be easier to follow, and catch some edge cases which that answer missed:

// Assume $var is the array specified in your question

function removeRedundantRoutes( $var ){

    // This line sorts $var by the length of each route
    usort( $var, function( $x, $y ){ return count( $x ) - count( $y ); } );

    // Create an empty array to store the result in
    $results = array();

    // Check each member of $var
    foreach( $var as $route ){
        $first = $route[0];
        $last = $route[ count( $route ) - 1 ];
        if( !array_key_exists( "$first-$last", $results ) ){
            // If we have not seen a route with this pair of endpoints already,
            // it must be the shortest such route, so place it in the results array
            $results[ "$first-$last" ] = $route;
        }
    }

    // Strictly speaking this call to array_values is unnecessary, but
    // it would eliminate the unusual indexes from the result array
    return array_values( $results );
}