coderz.py

Problem Statement (Asked By Stripe)

You are given an array of integers. Your task is to find the smallest missing positive integer in O(N) time using O(1) additional space. In other words, identify the smallest positive number that is not present in the array.

The array may include:

• Negative numbers
• Zero
• Duplicates

You are allowed to modify the input array in-place to achieve the result.

Examples:

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

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

Problem link: https://leetcode.com/problems/first-missing-positive/

---

If we didn’t have the linear time constraint, solving this problem would be simpler: we could sort the array, ignore negative numbers, and iterate over the sorted array to find the first positive number that doesn’t match its index. However, sorting takes O(nlog⁡n), which isn’t efficient enough for this problem.

To achieve O(n) time, we need to use a clever approach. The first missing positive number will always lie between 1 and n+1 (where n is the length of the array). We can disregard numbers that are negative or greater than nnn. The main idea is to rearrange the elements in the array such that every positive number is positioned at its correct index (i.e., value 1 at index 0, value 2 at index 1, and so on).

We traverse the array, and whenever we find a number within the range [1, n], we swap it to its correct position. We repeat this process until all numbers are either correctly placed or ignored. This ensures that the numbers from 1 to n are positioned correctly if they exist in the array.

Finally, we iterate through the array to find the first index where the number doesn’t match the expected value. If all numbers are in their correct positions, the missing positive number is n+1.

Approach 1: Rearranging In-Place (Optimal, O(n) Time and O(1) Space)

public class MissingPositive {

    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Rearrange numbers to their correct positions
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 &amp;&amp; nums[i] <= n &amp;&amp; nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        // Find the first missing positive
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println("First Missing Positive: " + firstMissingPositive(nums)); // Output: 2
    }
}

Approach 2: Using a Set (Simpler, O(n) Time and O(n) Space)

Alternatively, we can use a set to store all the numbers and then use a counter starting at 1. Increment the counter until we find a number that isn’t in the set.

import java.util.HashSet;

public class MissingPositive {

    public static int firstMissingPositive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int i = 1;
        while (set.contains(i)) {
            i++;
        }
        return i;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println("First Missing Positive: " + firstMissingPositive(nums)); // Output: 2
    }
}

Explanation:

1. Rearranging In-Place:
   • The elements are rearranged such that the number x is placed at index x−1 if x is within the range [1, n].
   • After rearranging, iterate through the array to find the first index i where the value isn’t i+1.
2. Using a Set:
   • Store all numbers in a set.
   • Start a counter at 1 and check for its presence in the set. Increment the counter until a missing value is found.

Time Complexity:

• Rearranging in-place: O(n) (each number is swapped at most once).
• Using a set: O(n) for traversal and lookup.

Space Complexity:

• Rearranging in-place: O(1) (no extra space used apart from input array).
• Using a set: O(n) (extra space for the set).

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.