First Missing Positive

class Solution {
public:
    int smallestMissingPositive(vector<int>& nums) {
        int length = nums.size();

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

        for (int idx = 0; idx < length; idx++) {
            if (nums[idx] != idx + 1) {
                return idx + 1;
            }
        }

        return length + 1;
    }
};

The given C++ solution focuses on finding the smallest missing positive integer from an unordered list. This solution implements a space-efficient algorithm with a time complexity of O(n), where n is the number of elements in the input vector. Below is a concise summary of the steps involved:

1. Iterate through each element of the vector, using a while loop that continues until the index reaches the length of the vector.
2. Inside the loop, check if the current element is a positive number and within the range from 1 to the length of the array. Also, verify if it is not already in its correct position (i.e., value nums[index] is not at its position nums[nums[index] - 1]).
3. If the element is not in the correct position, swap it with the number at its intended position.
4. If no swap is needed, increment the index.
5. After the while loop, start another loop that iterates through the vector to find the first position where the number idx + 1 is not at the index idx.
6. Return the first such index found as the smallest missing positive number.
7. If all numbers are in their correct positions, return the length of the list plus one.

This algorithm effectively rearranges the elements without using additional space, and then simply checks for the first gap in the sequence of the numbers starting from one.

class Solution {

    public int findMissingPositive(int[] array) {
        int size = array.length;

        int pos = 0;
        while (pos < size) {
            int targetPos = array[pos] - 1;
            if (array[pos] > 0 && array[pos] <= size && array[pos] != array[targetPos]) {
                exchange(array, pos, targetPos);
            } else {
                pos++;
            }
        }

        for (pos = 0; pos < size; pos++) {
            if (array[pos] != pos + 1) {
                return pos + 1;
            }
        }

        return size + 1;
    }

    private void exchange(int[] array, int first, int second) {
        int temp = array[first];
        array[first] = array[second];
        array[second] = temp;
    }
}

In the provided Java solution to the "First Missing Positive" problem, the method findMissingPositive is employed to determine the smallest missing positive integer in a given array. Here's a succinct overview of how the solution operates:

1. Iterate over the elements of the input array using a while loop. Assign each number to its correct position as per its value. For example, the integer 4 should ideally be at the position 3 (array index 3-1).
2. Use the exchange helper method to swap numbers until every positive integer that can be correctly positioned within the array bounds is placed at index = value - 1.
3. After the while loop concludes, starting again from the beginning of the modified array, compare each element's value to its index plus one. The first position where this does not match (i.e., array[pos] != pos + 1) determines the smallest missing positive integer.
4. If all positions match correctly, the array contains all integers from 1 to size, thus, return size + 1 as the smallest missing positive integer.

This method ensures an efficient scan and rearrangement of array elements, exploiting the properties of indices and elements values for an optimal solution. It refrains from using additional space and operates directly on the input, leveraging position swapping to reach the solution.

int smallestPositiveMissing(int* arr, int size) {
    int length = size;
    int index = 0;
    while (index < length) {
        int properPos = arr[index] - 1;
        if (arr[index] > 0 && arr[index] <= length && arr[index] != arr[properPos]) {
            int swapTemp = arr[index];
            arr[index] = arr[properPos];
            arr[properPos] = swapTemp;
        } else {
            index++;
        }
    }
    for (index = 0; index < length; index++) {
        if (arr[index] != index + 1) {
            return index + 1;
        }
    }
    return length + 1;
}

The problem is about finding the smallest missing positive integer from an array using C. The provided function smallestPositiveMissing utilizes an efficient algorithm that modifies the array in place, achieving a solution without additional space, except for a few local variables.

Here’s a concise explanation of how the function works:

1. Initialize length to the size of the array and set index to 0.

2. Use a while loop to iterate through the array. For each element, determine its appropriate position (properPos) in a sorted array of positive integers starting from 1. The calculation for properPos is arr[index] - 1.

3. Check for three conditions before swapping:

   • The element is positive.
   • The element does not exceed the array length.
   • The element is not already in its correct position.

   If all these conditions are met, swap the element at index with the element at properPos.

4. If the conditions are not met, simply increment the index.

5. After rearranging, use a for loop to go through the array. The first index where the condition arr[index] != index + 1 holds true is the smallest missing positive integer.

6. If the loop completes without finding any missing positive integer, return length + 1 as all integers from 1 to length are present.

This function executes in linear time, i.e., O(n), where n is the number of elements in the array, and provides an optimal solution for the problem of finding the smallest missing positive integer.

var findFirstMissing = function (arr) {
    let length = arr.length;
    let position = 0;
    while (position < length) {
        let targetIndex = arr[position] - 1;
        if (arr[position] > 0 && arr[position] <= length && arr[position] != arr[targetIndex]) {
            [arr[position], arr[targetIndex]] = [arr[targetIndex], arr[position]];
        } else {
            position++;
        }
    }
    for (position = 0; position < length; position++) {
        if (arr[position] != position + 1) {
            return position + 1;
        }
    }
    return length + 1;
};

The given JavaScript function named findFirstMissing is designed to find the smallest positive integer that is missing from an unsorted array arr. The algorithm uses the concept of placing each element at its correct index if possible, then checking to find the first missing positive integer by comparing array values to their indices.

• The function takes an array of integers as an input.
• It initializes the variable length to store the length of the array and position to iterate through the array.
• A while loop iterates over the array, and for each element, it checks if it can be swapped to its correct position, defined as element value-1. This process tries to sort the array in a specific order, particularly arranging positives in the front slots.
• A second loop then examines the array from the beginning to identify the smallest missing element. It achieves this by checking if the value at each index matches the index plus one (since array indices are zero-based).
• If a mismatch is found, the missing positive number is returned as index + 1.
• If all elements match their expected positions, the function returns length + 1, which would be the next consecutive integer missing from the sequence.

This method is efficient for finding the smallest missing positive integer because it attempts to sort relevant items in-place without using additional space and directly inspects the sequence from the lowest possible integer (1). The algorithm effectively handles arrays containing negative numbers, zeros, and positive integers.

class Solution:
    def findSmallestMissing(self, values: List[int]) -> int:
        length = len(values)
        index = 0
        while index < length:
            correct_pos = values[index] - 1
            if 0 < values[index] <= length and values[index] != values[correct_pos]:
                values[index], values[correct_pos] = values[correct_pos], values[index]
            else:
                index += 1

        for j in range(length):
            if values[j] != j + 1:
                return j + 1

        return length + 1

The provided Python 3 implementation focuses on finding the first missing positive integer in an unsorted list. The function findSmallestMissing determines the smallest number that does not appear in the list values.

• The function first determines the length of the input list to manage loop iterations correctly.
• It then employs a while loop to place each integer at its correct index in the list. This is achieved by swapping elements into their rightful positions based on the calculation correct_pos = values[index] - 1.
• The condition within the loop (0 < values[index] <= length and values[index] != values[correct_pos]) ensures the swapping occurs only when the value is positive, does not exceed the list's length, and is not already in its correct position.
• The subsequent for loop checks through the list to identify the first index j where the condition values[j] != j + 1 holds true, thereby identifying the smallest missing positive integer.
• If all positions are correctly occupied, the function returns length + 1, which would be the next positive integer outside the maximum range covered by the list.

This method is efficient as it reorganizes the list in place (O(n) time complexity) and then performs a linear scan to find the missing integer. This approach ensures optimal performance for finding the first missing positive from a given unordered list of integers.