Find count of smaller no of elements in an array and the solution needs to be 2n

user_4353828 0
Viewed 68

Hi i am stuck with a problem where in i have to find out the count of smaller no of element in an array i have implemented what we call as a brute force method but this isn't the optimised solution, can anyone help me out with the optimise solution for the code below

<?php
    function find_small_count($arr){
        $no_count = []; 
        foreach ($arr as $key => $value){
            $no_count[$key] = 0;
            foreach ($arr as $key1 => $value){
                if ($arr[$key1] < $arr[$key]) {
                    $no_count[$key]++;
                }
            }
        }
        return $no_count;
    }   
    print_r(find_small_count(['8','1','2','2','5']));
?>

Where in the expected Output should be [4,0,1,1,3]

data-structures php
1 Answers

I have three solutions for you. Let me explain

Working code sandbox

Solution 1

Use array_filter to return only qualified elements and then count the filtered array to get the count.

## Solution 1:

function find_small_count($arr)
{
    $response = [];
    foreach ($arr as $valueToSearch) {
        $filtered = array_filter($arr, function ($value) use ($valueToSearch) {
            return $value < $valueToSearch;
        });
        $response[] = ['valueToSearch' => $valueToSearch, 'count' => count($filtered)];
        
    }
    return $response;
}
print_r(find_small_count(['8', '1', '2', '2', '5']));

Solution 2

Sort the array in ascending order. When doing so your array has all numbers lesser than the current element appearing before it (in the array). Therefore the key for the array will be the count of all those numbers that are less than the current value, excluding the current number (keys start with 0).

Exception will be when a number appears twice, like 2 in your case. If we were to use key as the count in your case the first 2 will have count 1 and second 2 will have count 2, which is incorrect. Do note that the first 2 does give you the correct count.

To avoid this we can use array_unique and remove the duplicates. That will leave you with only one 2 in your response (the first one) and will give you the correct count.

You may think what about 5. For that we can fallback on the behavior of array_unique to preserve the keys. Hence even after array_unique 5 will retain its key, ie. 3. And our objective is accomplished. The only side effect is that the response will be [4,0,1,3] instead of [4,0,1,1,3]. So if that works you can use this method.

function find_small_count_two($arr){
    $response = [];
    sort($arr);
    $arrUniqueAndSorted = array_unique($arr);
    foreach ($arrUniqueAndSorted as $key => $value){
        $response[] = ['valueToSearch' => $value, 'count' => $key];
    }
    return $response;
}
print_r(find_small_count_two(['8', '1', '2', '2', '5']));

Solution 3

Use array_search. From the docs

Searches the array for a given value and returns the first corresponding key if successful

Same logic as Solution 2 but this one avoids array_unique

function find_small_count_three($arr){
    $response = [];
    sort($arr);
    foreach ($arr as $valueToCount){
        $count =array_search($valueToCount, $arr);
        $response[] = ['valueToSearch' => $valueToCount, 'count' => $count];
    }
    return $response;
}
user_48821340
Related