16 Jun 2023•PHP•Hard

First Missing Positive

find the smallest missing positive integer using array as hash table by placing each number at its correct index.

use the array itself as a hash table. for each number, place it at index (number - 1) if it's in valid range [1, n]. then scan to find first index where nums[i] != i + 1.

the key insight is that for an array of length n, the answer must be in [1, n+1]. by placing numbers at their correct positions, we can identify the missing one in a second pass.

algorithm

place each number at index (num - 1) if 1 ≤ num ≤ n
swap to place numbers correctly, handle duplicates
scan array to find first missing positive

complexity

O(n) time: each element visited at most twice. O(1) space excluding input array.

Solution files

PHP•first-missing-positive/solution.php

class Solution {

function firstMissingPositive($nums) {
    $n = count($nums);
    
    for ($i = class="syntax-number">0; $i < $n; $i++) {
        while ($nums[$i] > class="syntax-number">0 && $nums[$i] <= $n && $nums[$nums[$i] - class="syntax-number">1] != $nums[$i]) {
            $temp = $nums[$nums[$i] - class="syntax-number">1];
            $nums[$nums[$i] - class="syntax-number">1] = $nums[$i];
            $nums[$i] = $temp;
        }
    }

    for ($i = class="syntax-number">0; $i < $n; $i++) {
        if ($nums[$i] != $i + class="syntax-number">1) {
            return $i + class="syntax-number">1;
        }
    }

    return $n + class="syntax-number">1;
}
}

$solution = new Solution();
$nums1 = [class="syntax-number">1, class="syntax-number">2, class="syntax-number">0];
$nums2 = [class="syntax-number">3, class="syntax-number">4, -class="syntax-number">1, class="syntax-number">1];
$nums3 = [class="syntax-number">7, class="syntax-number">8, class="syntax-number">9, class="syntax-number">11, class="syntax-number">12];

echo $solution->firstMissingPositive($nums1) . class="syntax-string">"\n";
echo $solution->firstMissingPositive($nums2) . class="syntax-string">"\n";
echo $solution->firstMissingPositive($nums3) . class="syntax-string">"\n";