Code Challenge - array

For these code challenge we are again looking at traversing and working with arrays. First we will take a look at the problem, which was originally posed by Stripe.

The Problem

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3. You can modify the input array in-place. -Daily Coding Problem

Scoping

We will take a two step approach to this problem, will will filter out the negative values and loop until we find a missing value. We will create a method called findLowestMissingInt() which will take an array and return an integer.

Testing

We will start by writing tests and test cases matching the examples in the problem. Nothing too complicated here.

<?php

$testData = [
    ['input' => [3, 4, -1, 1], 'expected' => 2],
    ['input' => [1, 2, 0], 'expected' => 3],
];

function test(array $testData)
{
    foreach($testData as $testCase) {
        if($testCase['expected'] !== findLowestMissingInt($testCase['input'])) {
            echo 'FAIL'.PHP_EOL;
            continue;
        }

        echo 'PASS'.PHP_EOL;
    }
}

Our Solution

First we will create our method and filter out the negative values.

function findLowestMissingInt(array $input):int
{
    // Filter out values that are less than 1
    $positive = array_filter($input, fn($value) => $value > 0);
}

So what have we done here?

We have used the array_filter() function to remove the negative values from the given array. The array_filter() function takes an array and a callback as it's parameters. Each value is passed through the callback function and if the result is true, the value is returned to the resulting array.

We use a short closure, or arrow function, as our callback which simply checks that the value is positive (greater than 0). This results in an array we have named $positive containing only the positive values from the input array.

Now that we have our positive values, we are simply going to find the lowest values by counting up from 1 until we hit an integer that is not in the array.

function findLowestMissingInt(array $input):int
{
    // Filter out values that are less than 1
    $positive = array_filter($input, fn($value) => $value > 0);

    // Loop through and find the lowest missing integer
    $i = 1;
    while ($i > 0) {
        if(!in_array($i, $positive)) {
            return $i;
        }
        $i++;
    }
}

We use a while() loop to keep incrementing $i from 1 until we hit a value that is not in our $positives array.

Completed Code

<?php

// Data for testing
$testData = [
    ['input' => [3, 4, -1, 1], 'expected' => 2],
    ['input' => [1, 2, 0], 'expected' => 3],
];

// Test method
function test(array $testData)
{
    foreach($testData as $testCase) {
        if($testCase['expected'] !== findLowestMissingInt($testCase['input'])) {
            echo 'FAIL'.PHP_EOL;
            continue;
        }

        echo 'PASS'.PHP_EOL;
    }
}

// The solution method
function findLowestMissingInt(array $input):int
{
    // Filter out values that are less than 1
    $positive = array_filter($input, fn($value) => $value > 0);

    // Loop through and find the lowest missing integer
    $i = 1;
    while ($i > 0) {
        if(!in_array($i, $positive)) {
            return $i;
        }
        $i++;
    }
}

// Run the tests
test($testData);

Conclusion

We have solved the problem. We have taken a simple approach to the problem, and for the example data this will work just fine, however if we need to loop upto a large number then this is not going to be the most performant way.

How would you solve the problem?

Matt Lake