Find the Smallest Positive Missing Number

Title: Find the Smallest Positive Missing Number

The smallest-missing-positive problem is a favorite array question in technical interviews because it looks simple but hides several traps around negatives, duplicates, and out-of-range values. You are given an unsorted array of integers, and the task is to find the smallest positive integer that does not appear in it. In this guide, you’ll learn an in-place technique that solves the problem in O(n) time without allocating any extra array.

By the end of this tutorial, you’ll understand why the answer can never exceed n + 1, how to place every value at its correct index using swaps, and which interview follow-up questions build directly on this idea.

Understanding the Problem

You are given an array arr of n integers that may include negatives, zero, duplicates, and values larger than n. You must return the smallest positive integer that is absent from the array.

For example, if the input is:

int[] arr = {3, 4, -1, 1};

Then the expected output is:

int smallestMissing = 2;

A key observation drives every efficient solution: for an array of n elements, the answer is always between 1 and n + 1. If all of 1 through n are present, the answer is n + 1; otherwise some value inside that range is missing. This bounds the search space and rules out needing to look at values larger than n at all.

Approach: Placing Values at Their Correct Index

The idea is to use the array itself as a hash table. If a value v is in the range 1 to n, its correct home is index v - 1. We walk through the array and swap every in-range value into that position. Once every value that can be placed correctly has been placed, a single scan reveals the first index whose value does not match its position, which is exactly the smallest missing positive integer.

Here are the steps:

1. Let n be the length of arr.
2. For each index i from 0 to n - 1, repeatedly check whether arr[i] is a positive value within 1 to n and is not already sitting at its correct index.
3. If so, swap arr[i] with the value currently at index arr[i] - 1.
4. Keep swapping at the same index i until the value there is out of range, non-positive, or already correctly placed.
5. After the placement pass, scan the array again from index 0.
6. Return i + 1 for the first index where arr[i] != i + 1.
7. If every index matches, return n + 1.

Java Program to Find the Smallest Positive Missing Number

Here is the complete, runnable Java program that implements the in-place placement approach:

public class SmallestMissingPositive {

    public static int findSmallestMissingPositive(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {
                int correctIndex = arr[i] - 1;
                int temp = arr[correctIndex];
                arr[correctIndex] = arr[i];
                arr[i] = temp;
            }
        }

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

        return n + 1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, -1, 1};
        int result = findSmallestMissingPositive(arr);
        System.out.println("Smallest missing positive: " + result);
    }
}

Explanation of the Program

The findSmallestMissingPositive method first reads n, the length of arr. The outer for loop visits every index once, but the inner while loop is what actually moves values into place.

The while condition checks three things before swapping: arr[i] > 0 rules out negatives and zero, arr[i] <= n rules out values that could never be the answer, and arr[arr[i] - 1] != arr[i] stops the loop once the target cell already holds the same value, which prevents an infinite loop on duplicates.

When all three conditions hold, correctIndex is computed and the values at arr[i] and arr[correctIndex] are swapped. Each swap places at least one value in its final position, which is why the total number of swaps across the whole run is bounded by n.

The second loop scans the now-partially-sorted array. The first index where the stored value does not equal i + 1 reveals the smallest missing positive integer. If the loop completes without finding a mismatch, every value from 1 to n is present, so the method returns n + 1.

Step-by-Step Trace

Let’s trace the placement pass on the input arr = [2, 1, 4, 3, -1, 6], where n = 6. The expected output is 5, since 1 through 4 and 6 are present but 5 is missing. Each row shows one outer-loop iteration after any inner swaps settle.

After the placement pass, the array is [1, 2, 3, 4, -1, 6]. Scanning from index 0, the first mismatch is at index 4, where arr[4] = -1 but the expected value is 5. The method returns 5. The invariant is that after the placement pass, every index i either holds the value i + 1 or cannot hold it, so the first mismatch marks the smallest missing positive integer.

Examples

Example 1: A Negative Value Breaks the Sequence

The array contains 1, but not 2, since the negative value -1 occupies a slot instead. The smallest missing positive is 2.

int[] arr = {3, 4, -1, 1};
System.out.println(findSmallestMissingPositive(arr));
// Output: 2

Example 2: Zero Does Not Count as Positive

Even though 0 is present, it is not a positive integer, so it never satisfies the answer. With 1 and 2 both present, the answer becomes 3.

int[] arr = {1, 2, 0};
System.out.println(findSmallestMissingPositive(arr));
// Output: 3

Example 3: No Value in Range Is Present

None of the values are within 1 to n, so the placement pass makes no swaps at all and the very first index immediately reveals the answer, 1.

int[] arr = {7, 8, 9, 11, 12};
System.out.println(findSmallestMissingPositive(arr));
// Output: 1

Common Mistakes to Avoid

The swap-based approach is compact, but each line hides a trap that catches learners. Watch out for these:

• Skipping the duplicate check - omitting arr[arr[i] - 1] != arr[i] from the while condition causes an infinite loop whenever a duplicate value tries to swap with itself. Always compare the target cell to the current value before swapping.
• Missing the range guard - forgetting arr[i] <= n lets the algorithm index past the end of the array for large values, throwing ArrayIndexOutOfBoundsException. Both bounds, arr[i] > 0 and arr[i] <= n, must gate every swap.
• Returning the loop index instead of index + 1 - the scanning phase must return i + 1, not i, because array positions are zero-based but the answer is one-based.
• Forgetting the all-present case - leaving out the final return n + 1 after the scan loop produces the wrong result when the array already contains every value from 1 to n.
• Mutating an array the caller still needs - the swaps reorder the original array in place. If the caller expects the input order preserved, clone the array before calling findSmallestMissingPositive.

Edge Cases to Test

Before you call the solution complete, run it through these inputs. They cover the boundaries interviewers probe for:

• Empty array
• Single-element array such as {1} or {-5}
• Array containing 0
• All negative elements
• Array already equal to {1, 2, ..., n}
• Duplicate values within the valid range
• Every value greater than n
• Array containing Integer.MAX_VALUE

Additional Considerations

The placement approach runs in O(n) time. Although the while loop can iterate more than once per index, every successful swap places one additional value in its final position, so the total number of swaps across the entire run is bounded by n. The method uses O(1) auxiliary memory because it reorders the array in place instead of allocating a boolean presence array.

If you are not allowed to modify the input, a boolean array of size n + 1 is an equally fast alternative: mark present[v] = true for every in-range value, then scan for the first unmarked index starting at 1. This trades the O(1) space guarantee for a simpler, read-only pass.

Both approaches assume the array fits comfortably in memory. For extremely large inputs, consider the streaming follow-up discussed below.

Interview Follow-up Questions

The smallest-missing-positive problem is a launchpad for several deeper interview questions. Expect to be asked some of these:

• What if the input array must remain unmodified? - copy the array first, or use a boolean present array of size n + 1 instead of swapping values in place.
• What if you need the k-th smallest missing positive integer instead of just the first? - run the same placement pass, then scan for mismatches while counting them, returning the index where the count reaches k.
• What if the array also needs to report the smallest missing integer including negatives? - shift every value by the array’s minimum so the problem reduces back to the positive case, then shift the answer back.
• What if the input arrives as a stream too large to hold in memory? - maintain a bitset over a bounded candidate range as values stream in, since the answer can never exceed the count of elements seen so far plus one.

Conclusion

Finding the smallest positive missing number looks like a search problem, but the placement trick turns it into a single-pass, constant-space algorithm. The key insight, that the answer can never exceed n + 1, is what lets you use the array itself as a hash table instead of reaching for extra memory.

Try adapting the program to return the k-th missing positive integer, or compare it against the boolean-array alternative to see the space-versus-mutation trade-off firsthand. These small variations prepare you for the follow-up questions interviewers love to ask.

You can learn more about array algorithms here: Arrays.