in this problem, we need to find the first missing positive number in that given array its consisits of both positive numbers and negative numbers so we need focus on the positive numbers in problem name itself tells the first missing positive number let look at the test cases and also it is a Hard problem in Leetcode but easy to solve this using the unordered map
Let talk about the test cases in the problem there given three test cases we discuss each test case for clear understand how we apply the logic behind the problem why its hard problem
In example 1 let talk about what number is missing there no number is missing but the sequence of the number is missing right according the size of the array like 0 will not take consider why because of its not positive as well as not negative number 1 is positive and 2 is positive and 3 is the missing
This code implements a solution to the First Missing Positive problem, which requires finding the smallest positive integer missing from an unsorted array of integers. The approach uses an unordered_map for storing and looking up integers, ensuring constant time complexity for these operations. By leveraging this map, the solution efficiently checks for missing positive integers without explicitly sorting the array or performing extensive iterations.
The function starts by declaring an unordered_map named map and iterates over the input array nums to populate it. For each element in nums, the value of the integer is used as a key, and its index in the array is stored as the corresponding value. This ensures that every number in the array can be quickly looked up. The size of the array is stored in the variable n, which is later used to define the range for checking missing positive integers.
After the map is built, the function iterates over a range of numbers from 1 to 2n to find the first missing positive integer. The range 2n is chosen as a safe upper bound because the smallest missing positive integer will always lie within this range in the worst-case scenario. For each number in this range, the program checks if it exists in the map using the map.find() function. If the number is not found, it is returned immediately as the first missing positive integer.
The key operation here is the efficient use of the unordered_map's constant-time lookups to check the existence of numbers in the array. This eliminates the need to sort the array, which would require O(nlogn) time complexity. The solution is, therefore, time-efficient, with an average-case time complexity of O(n). However, the use of the unordered_map introduces additional space complexity of O(n), as it stores all elements in the input array.
Finally, while the function guarantees correctness, there is a fallback return value of 0, which is technically unreachable for valid inputs since the problem specifies that a positive integer is always missing. The solution could be optimized further by modifying the input array in place to avoid using extra space, achieving O(1) space complexity. Nonetheless, this implementation is straightforward and demonstrates a clear approach to solving the problem using hash maps for quick lookups.
CODE IN C++:
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_map<int,int>map;
int i;
int n=nums.size();
for(i=0;i<n;i++){
map[nums[i]]=i;
}
for(i=0;i<n+n;i++){
if(map.find(i+1)==map.end()){
return i+1;
}
}
return 0;
}
};
0 Comments