Minimum Impossible Or - Leetcode Solution

Problem Statement:

Given an integer array nums, return the minimum non-negative integer that is missing from nums.

Example 1:

Input: nums = [0,1,2,3,4,5,6,7,8,9] Output: 10 Example 2:

Input: nums = [9,8,7,6,5,4,3,2,1,0] Output: 10

Approach:

The minimum non-negative integer missing from the array nums can only be in the range [0, N+1], where N is the size of the array. This is because if the array had all the integers in the range [0,N], then the minimum missing integer would be N+1.

Thus, we can create a boolean array of size N+1 and mark all the integers present in the input array nums. Then we iterate over the boolean array and return the first index that is not marked as present.

Code:

class Solution { public: int minMissingElement(vector<int>& nums) { int n = nums.size(); vector<bool> present(n+1, false); for(int i=0; i<n; ++i) { if(nums[i] < n+1) present[nums[i]] = true; } for(int i=0; i<=n; ++i) { if(!present[i]) return i; } return n+1; } };

Time Complexity:

We iterate over the array nums once to mark the present integers in O(N) time. Then we iterate over the boolean array once to find the minimum missing integer in O(N) time. Thus, the total time complexity of the solution is O(N).

Space Complexity:

We create a boolean array of size N+1 to mark the present integers. Thus, the space complexity of the solution is O(N).

Note:

The problem can also be solved using a hash set or by sorting the input array and iterating over it. However, these approaches have a higher time complexity than the boolean array approach.

1