Algorithm – First Missing Positive

Problem

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

Example:

Input: [1,2,4,0]
Output: 3

Input: [3,8,-1,1]
Output: 2

Input: [7,8,17,11,12]
Output: 1

Solution (Java)

public static int firstMissingPositiveNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0)
            return 1;
        int length = numbers.length;
        for (int i = 0; i < length; i++) {
            int num = numbers[i];
            while (numbers[i] <= length && numbers[i] > 0 && numbers[num - 1] != num){
                numbers[i] = numbers[num - 1];
                numbers[num - 1] = num;
                num = numbers[i];
            }
        }

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

Real life problems

Data validation

Suppose you have a dataset containing positive numbers, and you want to ensure that there are no missing positive numbers within a specific range. You can use a similar approach to iterate through the dataset and find the first missing positive number. This can be useful in data cleansing or verifying the integrity of a dataset.

Inventory management

In inventory management systems, it’s common to assign unique identifiers or serial numbers to items. If there is a gap or missing number in the sequence, it can indicate a missing item or an error in the inventory records. You can use a variant of this Swap and Sort algorithm to identify the first missing identifier in the sequence, helping to identify the missing item or correct any discrepancies.

Task assignment

In task management systems, you may have a list of tasks numbered from 1 to N. If there are missing task numbers in the sequence, it can indicate incomplete or unassigned tasks. By applying this algorithm, you can identify the first missing task number and take appropriate action, such as reassigning or completing the missing tasks.

Time complexity O(n)

Click here to check algorithm to merge k sorted list. And our facebook page is here

!!!! Happy coding !!!!