CPP: Smallest Positive integer

Solution for the Smallest Positive integer problem in Cpp

Problem Description

Given an array of integers A, determine the smallest positive integer (greater than 0) that does not appear in the array.

The array may contain:

  • Positive numbers
  • Negative numbers
  • Duplicate values

Only positive integers are relevant to the result.

The goal is to find the first missing value in the natural counting sequence starting from 1.

Example

  • Input: A = [1, 3, 6, 4, 1, 2] and the Output: 5
  • Input: A = [1, 2, 3] and the Output: 4
  • Input: A = [-1, -3] and the Output: 1

Notes

  • Only integers greater than zero affect the result
  • The smallest possible answer is always at least 1
  • Duplicate values do not change the outcome
  • The solution should scale efficiently for large input sizes

Constraints

  • Array size N is in the range [1 … 100,000]
  • Each element in A is in the range [−1,000,000 … 1,000,000]
  • Expected time complexity: O(N)
  • Expected space complexity: O(N) or better

Solution

cpp 
// you can use includes, for example:
// #include <algorithm>
#include <set>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // Implement your solution here

	// Target: 
	// Return smallest positive integer greater than 0
	// Which is not in the array
	
	// Examples:
    // A = [1, 3, 6, 4, 1, 2] : return 5
    // A = [1, 2, 3] : return 4
    // A = [-1, -3] : return 1

	// Extra Corner case:
	// A = [2, 3, 4] : return 1
	
	// Thinking:
	// We need to sort the input data (and having it unique is good too)
	// Data Structure (Set) is suitable : O(n log n)
	 
	// Then go through the Set : O(n)
	// 
	// 1. ignore the negative
	// 2. check if 1,2,... is exist

    unsigned int smallest_positive_int = 1;
    // sort with unique using set
    std::set<int> S (A.begin(), A.end());

    // check for the positive integer which is not in A 
    for (auto& n : S) {
        // scape the negative
        if (n < static_cast<const int> (smallest_positive_int)) continue;
        // if found check the next one
        else if(n == static_cast<const int> (smallest_positive_int)) smallest_positive_int++;
        // if did not found, return that it is missing
        else break;
    }
    return smallest_positive_int;
}