[LeetCode] First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution: 

O(n) running time, O(n) extra space.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) { return 1; } HashSet<Integer> set = new HashSet<Integer>(); for (int num : nums) { set.add(num); } int num = 1; while (set.contains(num)) { num++; } return num; } }

O(n) running time, O(1) extra space.
This utilizes a smart trick by modifying the array to act as a HashSet. See a detailed discussion here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution { private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } private int partition(int[] nums) { int storeIdx = 0; for (int j = 0; j < nums.length; j++) { if (nums[j] > 0) { swap(nums, storeIdx, j); storeIdx++; } } return storeIdx; } public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) { return 1; } int numPos = partition(nums); for (int i = 0; i < numPos; i++) { if (Math.abs(nums[i]) - 1 < numPos) { if (nums[Math.abs(nums[i]) - 1] > 0) { nums[Math.abs(nums[i]) - 1] *= -1; } } } for (int i = 0; i < numPos; i++) { if (nums[i] > 0) { return i + 1; } } return numPos + 1; } }