paint-brush
Java Algorithms: First Missing Positive (LeetCode)by@top4ikru
10,245 reads
10,245 reads

Java Algorithms: First Missing Positive (LeetCode)

by Leonid ZemenkovJanuary 10th, 2023
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

The First Missing Positive problem is an algorithm problem that requires finding the smallest positive integer that is not present in a given unsorted array of integers. The goal is to find the missing positive integer with the least value in the array in O(n) time complexity and O(1) space complexity. This problem can be solved by modifying the original array in-place and using the array indices to mark the presence of positive integers in the array.
featured image - Java Algorithms: First Missing Positive (LeetCode)
Leonid Zemenkov HackerNoon profile picture

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.

Whenever we know how to solve an array problem using a HashMap but extra space is not allowed, try using the array itself as a HashMap.

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! ✌