First Missing Positive

Hard Arrays

Find the smallest missing positive integer in O(n) time and O(1) space by placing each value at its correct index (cyclic sort).

Sample input

[3, 4, -1, 1]

Sample output

Solution

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

print(first_missing_positive([3, 4, -1, 1]))

function firstMissingPositive(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const j = nums[i] - 1;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

console.log(firstMissingPositive([3, 4, -1, 1]));

public class Main {
    static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int j = nums[i] - 1;
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
    }
}

fun firstMissingPositive(nums: IntArray): Int {
    val n = nums.size
    for (i in 0 until n) {
        while (nums[i] in 1..n && nums[nums[i] - 1] != nums[i]) {
            val j = nums[i] - 1
            val t = nums[i]
            nums[i] = nums[j]
            nums[j] = t
        }
    }
    for (i in 0 until n) {
        if (nums[i] != i + 1) return i + 1
    }
    return n + 1
}

fun main() {
    println(firstMissingPositive(intArrayOf(3, 4, -1, 1)))
}

func firstMissingPositive(_ nums: inout [Int]) -> Int {
    let n = nums.count
    for i in 0..<n {
        while nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i] {
            let j = nums[i] - 1
            nums.swapAt(i, j)
        }
    }
    for i in 0..<n {
        if nums[i] != i + 1 { return i + 1 }
    }
    return n + 1
}

var nums = [3, 4, -1, 1]
print(firstMissingPositive(&nums))

int firstMissingPositive(List<int> nums) {
  final n = nums.length;
  for (var i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
      final j = nums[i] - 1;
      final t = nums[i];
      nums[i] = nums[j];
      nums[j] = t;
    }
  }
  for (var i = 0; i < n; i++) {
    if (nums[i] != i + 1) return i + 1;
  }
  return n + 1;
}

void main() {
  print(firstMissingPositive([3, 4, -1, 1]));
}

#include <iostream>
#include <vector>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

int main() {
    vector<int> nums = {3, 4, -1, 1};
    cout << firstMissingPositive(nums) << endl;
    return 0;
}

#include <stdio.h>

int firstMissingPositive(int *nums, int n) {
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int j = nums[i] - 1;
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

int main() {
    int nums[] = {3, 4, -1, 1};
    printf("%d\n", firstMissingPositive(nums, 4));
    return 0;
}