Task Description: Given an unsorted integer array , return the smallest missing positive integer. nums Complexity Conditions: Time complexity: O(n) 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: Time complexity: O(n*n) 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 or a of size N to remember which elements are in the array. And then, by simple enumeration, find the minimum positive element. HashMap boolean array Complexity: Time complexity: O(n) 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: Time complexity: O(n) 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: Since we mark cells with negation, we must ignore the sign when extracting. In step 1, we changed all the numbers to ignore so don't forget to ignore them. fakeNumber, 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! ✌

Understanding the Sliding Window Pattern: Efficient Utilization Through Examples

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

Java Algorithms: First Missing Positive (LeetCode)

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

How to Design a Messaging Service in Your 45-Minute System Design Interview

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

How to Design a Messaging Service in Your 45-Minute System Design Interview

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps