Smallest Positive Missing Number

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find smallest positive integer not in array. Cyclic sort / index marking.

Algorithm

1Cyclic sort: place each positive integer x at index x-1 (if 1<=x<=n). Then scan for first position where arr[i]!=i+1.

Common Pitfalls

•Same as LC 41. O(n) time O(1) space. Cyclic sort variant or mark visited by negating.

Smallest Positive Missing Number.java

Java

// Approach: Index marking. Place each number in its correct index position, then scan for first mismatch.
// Time: O(n) Space: O(1)
class Solution {
    // Function to find the smallest positive number missing from the array.
    public int missingNumber(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr) {
            if (num > 0)
                set.add(num);
        }

        int smallNum = 1;
        while (set.contains(smallNum))
            smallNum++;

        return smallNum;
    }
}

Was this solution helpful?