First Missing Positive

                                            
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && 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;
    }
};

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

                                            
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

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

                                            
public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    let n = nums.length;
    
    for (let i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    
    return n + 1;
};

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

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function firstMissingPositive($nums) {
        $n = count($nums);
        for ($i = 0; $i < $n; $i++) {
            while ($nums[$i] > 0 && $nums[$i] <= $n && $nums[$i] != $nums[$nums[$i] - 1]) {
                $temp = $nums[$i];
                $nums[$i] = $nums[$temp - 1];
                $nums[$temp - 1] = $temp;
            }
        }
        
        for ($i = 0; $i < $n; $i++) {
            if ($nums[$i] != $i + 1) {
                return $i + 1;
            }
        }
        
        return count($nums) + 1;
    }
}

                                            
class Solution {
    func firstMissingPositive(_ nums: [Int]) -> Int {
        var nums = nums
        var i = 0
        
        while i < nums.count {
            if nums[i] > 0 && nums[i] <= nums.count && nums[nums[i] - 1] != nums[i] {
                nums.swapAt(i, nums[i] - 1)
            } else {
                i += 1
            }
        }
        
        for i in 0..<nums.count {
            if nums[i] != i + 1 {
                return i + 1
            }
        }
        
        return nums.count + 1
    }
}

                                            
class Solution {
    fun firstMissingPositive(nums: IntArray): Int {
        var i = 0
        while (i < nums.size) {
            if (nums[i] > 0 && nums[i] <= nums.size && nums[nums[i] - 1] != nums[i]) {
                val temp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = temp
            } else {
                i++
            }
        }
        
        for (j in 0 until nums.size) {
            if (nums[j] != j + 1) {
                return j + 1
            }
        }
        
        return nums.size + 1
    }
}

                                            
class Solution {
  int firstMissingPositive(List<int> nums) {
    Set<int> numSet = Set.from(nums);
    int i = 1;
    while (numSet.contains(i)) {
      i++;
    }
    return i;
  }
}

                                            
func firstMissingPositive(nums []int) int {
    n := len(nums)

    for i := 0; i < n; i++ {
        for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        }
    }

    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }

    return n + 1
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def first_missing_positive(nums)
    n = nums.length
    (0..n-1).each do |i|
        while nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] do
            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        end
    end

    (0..n-1).each do |i|
        return i + 1 if nums[i] != i + 1
    end

    return n + 1
end

                                            
impl Solution {
    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        let n = nums.len() as i32;

        for i in 0..n {
            while nums[i as usize] > 0 && nums[i as usize] <= n && nums[(nums[i as usize] - 1) as usize] != nums[i as usize] {
                let idx = nums[i as usize] as usize - 1;
                let tmp = nums[idx];
                nums[idx] = nums[i as usize];
                nums[i as usize] = tmp;
            }
        }

        for i in 0..n {
            if nums[i as usize] != i + 1 {
                return i + 1;
            }
        }

        n + 1
    }
}

                                            
(define/contract (first-missing-positive nums)
  (-> (listof exact-integer?) exact-integer?)
  (let ((n (+ 1 (apply max nums))))
    (let loop ((i 1))
      (cond
        ((not (member i nums)) i)
        (else (loop (+ i 1)))
        ))
  ))

                                            
-spec first_missing_positive(Nums :: [integer()]) -> integer().
first_missing_positive(Nums) ->
    case lists:seq(1, length(Nums) + 1) -- Nums of
        [] -> length(Nums) + 1;
        [X | _] -> X
    end.

To solve this coding challenge of finding the smallest positive integer that is not present in the given unsorted integer array

nums

, we need to implement an algorithm that operates in O(n) time complexity and uses O(1) auxiliary space. Let's break down the solution in a very detailed manner.

Explanation

Objective : Find the smallest missing positive integer in an unsorted array
nums

.
Constraints : The search should be confined to O(n) time and O(1) auxiliary space. This is crucial as it guides our approach to the problem.
Understanding the Problem :

Given a list of integers, some may be negative, some positive.
We need to find the smallest positive integer that is not present in the list.
For example, given
[3,4,-1,1]

, the smallest positive integer missing is
2

.

Initial Thoughts:

Ordinarily, one might sort the array or use additional storage to track the presence of integers. However, due to the O(n) time and O(1) space constraints, these approaches are not feasible. Instead, we need to rearrange the array elements such that each positive integer

i

is placed in the index

i-1

Plan:

Rearrange the array : Iterate over the list to place each number
nums[i]

in its correct position.
Identify the first missing positive : Iterate over the rearranged list to find the first index where the value does not match the index + 1.

Detailed Steps in Pseudocode:

Rearranging :

Loop through each element in the array.
For each element
nums[i]

, if it's a positive integer within the valid range (1 to n) and not already at the correct position, swap it with the element at the index
nums[i] - 1

.
Repeat this process until all elements are either out of the valid range or at their correct positions.

Finding the Missing Positive :

Loop through the rearranged array.
If
nums[i]

is not equal to
i + 1

, then
i + 1

is the smallest missing positive integer.
If no mismatch is found, then the missing integer is
n + 1

.

Pseudocode:

                                            
function find_first_missing_positive(nums):
# Rearrange the elements in the array
length_of_nums = length of nums
for i from 0 to length_of_nums - 1:
# While the current element is in the valid range and not in its correct spot
while 1 <= nums[i] <= length_of_nums and nums[nums[i] - 1] != nums[i]:
# Swap the element to its correct position
temp = nums[nums[i] - 1]
nums[nums[i] - 1] = nums[i]
nums[i] = temp

# Identify the first missing positive integer
for i from 0 to length_of_nums - 1:
# If the current element is not in the correct position
if nums[i] != i + 1:
return i + 1

# If all elements are in the correct position
return length_of_nums + 1

Step-by-Step Explanation:

Initialization :

Start with the input array
nums

.
Calculate the length of the array
length_of_nums

.

Rearranging the Elements :

Iterate with index
i

from
0

to
length_of_nums - 1

.
For each
nums[i]

, if it is within the valid range (1 to
length_of_nums

) and not already placed correctly (checked with
nums[nums[i] - 1] != nums[i]

), swap it with the element at its correct position
nums[i] - 1

.
This ensures that by the end of the loop, all valid positive integers up to
n

are placed in their respective positions if possible.

Finding the Missing Positive :

After rearranging, iterate over the modified array.
Check each position
i

.
If
nums[i]

is not equal to
i + 1

, then the missing number is
i + 1

because the number meant to be in that index is missing.
If no such index is found, return
length_of_nums + 1

as it indicates that all numbers from 1 to
length_of_nums

are present.

By following this methodology, you ensure the solution adheres to the constraints of O(n) time complexity and O(1) auxiliary space while identifying the smallest missing positive integer effectively.