Leetcode: 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.

Understand the problem:
The problem gives an unsorted integer array, find the first missing positive integer. The problem requires that the runtime should be within O(n) and uses constant space. 

A naive approach:
A naive approach is first to sort the array. Then it is quite straightforward to solve the problem. Just compare each element with the result, if the difference is larger than 1, return the result + 1, else update the result as A[i]. If iterate the entire array and we did not find the result, return the last element of the array plus 1.

Code (Java):

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        }
        
        Arrays.sort(A);
        int result = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= 0) {
                continue;
            }
            
            if (A[i] - result > 1) {
                return result + 1;
            } else {
                result = A[i];
            }
        }
        return A[A.length - 1] + 1;
    }
}

A better Solution:
Since the problem requires for linear time complexity and constant space. We can think of using bucket sort idea. The idea is to check if the index i store the value i + 1, if not swap the the value A[i] to its desired index. After that, we iterate again the array and check the first position that i != A[i] + 1. 

Code (Java):

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        }
        int n = A.length;
        int i = 0;
        while (i < n) {
            if (A[i] != i + 1 && A[i] >= 1 && A[i] <= n && A[i] != A[A[i] - 1]) {
                swap(A, i, A[i] - 1);
            } else {
                i++;
            }
        }
        
        for (i = 0; i < n; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        
        return A[n - 1] + 1;
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Summary:
The take-away message for this question is when the question asks for O(n) time solution, and you found that it must be beneficial to sort the input array, bucket sort is a way to think about.