Smallest Positive Missing Number

You are given an integer array arr[]. Your task is to find the smallest positive number missing from the array.

Note: Positive number starts from 1. The array can have negative integers too.

Examples:

Input: arr[] = [2, -3, 4, 1, 1, 7]
Output: 3
Explanation: Smallest positive missing number is 3.

Input: arr[] = [5, 3, 2, 5, 1]
Output: 4
Explanation: Smallest positive missing number is 4.

Input: arr[] = [-8, 0, -1, -4, -3]
Output: 1
Explanation: Smallest positive missing number is 1.

Constraints:
1 <= arr.size() <= 10⁵
-10⁶ <= arr[i] <= 10⁶

Approach 01:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    // Function to find the smallest positive number missing from the array.
    int missingNumber(vector<int>& nums) {
        // Create an unordered set to remove duplicates
        unordered_set<int> uniqueNumbers(nums.begin(), nums.end());

        // Transfer unique numbers to a vector
        vector<int> sortedNumbers(uniqueNumbers.begin(), uniqueNumbers.end());

        // Sort the vector
        sort(sortedNumbers.begin(), sortedNumbers.end());

        // Initialize the smallest missing positive number
        int expectedNumber = 1;

        // Iterate through the sorted unique numbers to find the smallest missing positive number
        for (int num : sortedNumbers) {
            if (num > 0) {
                if (expectedNumber != num) {
                    return expectedNumber;
                } else {
                    ++expectedNumber;
                }
            }
        }

        // If all positive numbers are found in sequence, return the next expected number
        return expectedNumber;
    }
};

class Solution:
    # Function to find the smallest positive number missing from the array.
    def missingNumber(self, nums):
        # Remove duplicates using a set
        uniqueNumbers = set(nums)
        
        # Convert to a sorted list
        sortedNumbers = sorted(uniqueNumbers)
        
        # Initialize the smallest missing positive number
        expectedNumber = 1
        
        # Iterate through the sorted unique numbers
        for num in sortedNumbers:
            if num > 0:
                if expectedNumber != num:
                    return expectedNumber
                else:
                    expectedNumber += 1
        
        # If all positive numbers are found, return the next expected number
        return expectedNumber

Time Complexity

• Creating Unordered Set:

  Inserting the elements of the `nums` array into an unordered set takes \( O(N) \), where \( N \) is the number of elements in `nums`.

• Sorting the Unique Numbers:

  After removing duplicates, sorting the unique numbers requires \( O(U \log U) \), where \( U \) is the number of unique elements in the array.

• Iterating Through the Sorted Array:

  Iterating through the sorted unique numbers to find the missing number takes \( O(U) \).

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, so the final time complexity is \( O(U \log U) \), where \( U \leq N \) is the number of unique elements in the array.

Space Complexity

• Unordered Set:

  The unordered set stores all the unique numbers, taking \( O(U) \) space, where \( U \) is the number of unique elements in the array.

• Sorted Vector:

  The vector `sortedNumbers` also stores the unique numbers, requiring \( O(U) \) space.

• Auxiliary Variables:

  Constant space is used for variables like `expectedNumber` and loop variables, requiring \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(U) \), due to the unordered set and sorted vector.