class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;

        int p = 0;
        while (p < nums.length){
            if (nums[p] == p + 1 || nums[p] <= 0 || nums[p] > nums.length){
                p++;
            }
            else if (nums[nums[p] - 1] != nums[p]){
                swap(nums, p, nums[p] - 1);
            }
            else{
                p++;
            }
        }

        p = 0;
        while (p < nums.length && nums[p] == p + 1){
            p++;
        }

        return p + 1;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}