Smallest Positive Missing

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Rearrange: place each number i at index i-1 if 1<=i<=n. Then scan for first index where arr[i]!=i+1.

Algorithm

1Cyclic sort: while arr[i] != i+1 and arr[i] in [1,n] and arr[i] != arr[arr[i]-1]: swap arr[i] with arr[arr[i]-1].
2Scan: first i where arr[i] != i+1, return i+1. If all placed: return n+1.

Common Pitfalls

•Ignore duplicates during cyclic sort (check arr[i]!=arr[arr[i]-1] before swap). Answer in range [1,n+1].

Smallest Positive Missing.java

Java

// Approach: Cycle sort or index marking to place each positive number at its correct position.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int missingNumber(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int i : arr)
            set.add(i);

        int ans = 1;
        while (!set.add(ans))
            ans++;

        return ans;
    }
}

Was this solution helpful?