First Missing Positive Leetcode Solution
First Missing Positive Leetcode Problem :
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Example :
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Wildcard Matching Leetcode Problem Solution :
Constraints :
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 – 1
Example 1:
Input: [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Example 2:
Input: [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
Approach:
- Since they’ve asked us to find out the smallest positive integer, then there’s no point of having the negative numbers in array.
- All the negative numbers in the array is replaced by 0.
- Check if the number one(1) is present in array or not. If not then you’ve got the answer :-))), just return 1.
- Otherwise sort the array and find out for that first element whose difference is greater than 1. If found, then store the result in a variable and break the loop.
- If the value of the variable is same even before and after the iteration, then return (last element + 1).
Complexity:
Time complexity :
- The first loop iterates through the nums vector to set negative values to zero. This loop has a time complexity of O(n), where n is the size of the nums vector.
- The second loop counts the number of ones in the nums vector. This loop also has a time complexity of O(n).
- Sorting the nums vector using sort takes O(n * log(n)) time complexity.
- The third loop iterates through the sorted nums vector to find the first missing positive integer. This loop has a time complexity of O(n).
Space complexity:
- The code uses a few integer variables like n, ones, and ele, which have constant space complexity, O(1).
- The input vector nums is modified in place, so no additional space is used for it.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
int firstMissingPositive(vector& < int> nums)
{
int n = nums.size();
for(int i = 0; i < n; i++)
{
if(nums[i] < 0)
nums[i] = 0;
}
int ones = 0;
for(auto x: nums)
{
if(x == 1)
ones++;
}
if(ones == 0)
return 1;
sort(nums.begin(), nums.end());
int ele = -1;
for(int i = 1; i < n; i++) { if(nums[i] - nums[i-1] > 1)
{
ele = nums[i-1] + 1;
break;
}
}
return ele == -1 ? ++nums[n-1] : ele;
}
};
Java
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] < 0) {
nums[i] = 0;
}
}
int ones = 0;
for (int x : nums) {
if (x == 1) {
ones++;
}
}
if (ones == 0) {
return 1;
}
Arrays.sort(nums);
int ele = -1;
for (int i = 1; i < n; i++) {
if (nums[i] - nums[i - 1] > 1) {
ele = nums[i - 1] + 1;
break;
}
}
return ele == -1 ? ++nums[n - 1] : ele;
}
}
Python
class Solution:
def firstMissingPositive(self, nums):
n = len(nums)
for i in range(n):
if nums[i] < 0:
nums[i] = 0
ones = 0
for x in nums:
if x == 1:
ones += 1
if ones == 0:
return 1
nums.sort()
ele = -1
for i in range(1, n):
if nums[i] - nums[i - 1] > 1:
ele = nums[i - 1] + 1
break
return ele + 1 if ele == -1 else ele
Login/Signup to comment