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.

View original LeetCode question

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";