Java Algorithms: First Missing Positive (LeetCode)

Task Description:

Given an unsorted integer array nums, return the smallest missing positive integer.

Complexity Conditions:

1. Time complexity: O(n)
2. Space complexity:  O(1)

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [-1,7,8,9,11,12,-10]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Solution:

Brute force approach

The first thing that comes to mind is to do brute force. The idea is simple; sort through all positive numbers from 1 until we find the first missing one.

Complexity:

1. Time complexity: O(n*n)
2. Space complexity:  O(1)

public int firstMissingPositive(int[] nums) {
    int positiveNumber = 1;
    while (true) {
        boolean exists = false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == positiveNumber) {
                exists = true;
                break;
            }
        }
        if (!exists) return positiveNumber;
        positiveNumber++;
    }
}

The problem is that for each number, we re-pass through the entire array. Let's try to reduce the number of iterations by allocating extra memory.

Approach 2: With Extra Space

We can use a HashMap or a boolean array of size N to remember which elements are in the array. And then, by simple enumeration, find the minimum positive element.

Complexity:

1. Time complexity: O(n)
2. Space complexity:  O(n)

public int firstMissingPositive(int[] nums) {
    Map<Integer, Boolean> map = new HashMap<>();
    for (int n: nums) {
        if (n > 0) {
            map.put(n, true);
        }
    }
    int number = 1;
    while(true) {
        if (map.get(number) == null) {
            return number;
        }
        number++;
    }
}

In the first loop on lines 3-7, we remember only positive numbers, since we will need to work with them further.

In the second loop on lines 9-13, we sequentially check the numbers starting from 1. If the number is on the map, then we move on, otherwise, return it.

Approach 3

To use the original array as a HashMap, we need to take a closer look at the problem statement. In the worst case, the array will contain all positive numbers from 1 to N (the length of the array), and then the answer will be N+1.

• Step 1. This means that all numbers less than 1 and greater than N are useless, and we can replace them with N+1. All numbers in the array are now positive, and in the range [1..N+1].

• Step 2. We can mark each cell that appears in the array by converting the index for that number to negative

• Step 3. Find the first index which is positive that is our answer.

Complexity:

1. Time complexity: O(n)
2. Space complexity:  O(1)

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    int fakeNumber = n + 1;
    
    // Step 1.
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = fakeNumber;
        }
    }
    
    // Step 2.
    for (int i = 0; i < n; i++) {
        int num = Math.abs(nums[i]); // point 1
        if (num == fakeNumber) { // point 2
            continue;
        }
        num--; // point 3
        if (nums[num] > 0) {
            nums[num] *= -1;
        }
    }
    
    // Step 3.
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            return i + 1;
        }
    }
    
    // otherwise return n+1
    return n + 1;
}

I would like to draw your attention to a few major points:

1. Since we mark cells with negation, we must ignore the sign when extracting.

2. In step 1, we changed all the numbers to ignore fakeNumber, so don't forget to ignore them.

3. Do not forget to decrease the value by 1; since, in java, indexing starts from zero (so the number 1 will be at pos 0).

The algorithm listed above gives us the following result.

I hope this article helped you understand how to solve this type of problem. I will be glad for your feedback.

See you soon! ✌