In the First Mission Positive problem, you are given an array, and you must find the first positive integer missing from that array.<\/strong><\/p>\n\n\n\n This is important to note that if you are not given that the array is sorted always consider it unsorted and as it was not specified in the question the values of the array are only positive so we have to consider that it may contain negative values also. <\/p>\n\n\n\n For example, you are given array arr= [2, 1, -1, -3] in this case the ans is 3 as 1 and 2 are already present so the first missing positive number is 3. We are not returning 0 as 0 is neither positive nor negative.<\/p>\n\n\n\n The basic solution is to check for each positive number in the given array and if it is not present then that number will be the first missing positive number. Let’s understand by an example:<\/p>\n\n\n\n As we are checking for each number in the array, the maximum we need to check is the size of the array let’s say of array is n so the <\/em>time complexity is O(n^2). Space Complexity will be O(1) as we are not using any extra space.<\/p>\n\n\n\n As in the above approach, we see that the time complexity is around O(n^2) which is huge and we know we can easily find the first missing number in the sorted array just by iterating over that array. <\/p>\n\n\n\n To find the first missing positive in an array, we will first sort the array by sorting function and then make an int variable x=1 whose initial value will be 1 and keep on updating if it encounters the same value.<\/strong><\/p>\n\n\n\n For example, let’s take an array:<\/p>\n\n\n\n As we are sorting the array<\/a> and iterating the array for once the time complexity would become (n+ log (n)) which is approx O(nlog(n)). Here n is the size of the array. Space Complexity will be O(1) as we are not using any extra space.<\/p>\n\n\n\n As in the sorting approach time complexity is around O(log (n)) which is still too much. We can reduce this to O(n) by just observing the pattern as we know we have to find the first positive missing number. <\/p>\n\n\n\n We just keep on putting the positive value to its correct place if possible (as sometimes the positive value is larger than the size of the array in that case we cannot put this to its correct index) whenever we find they are not at the right position. <\/p>\n\n\n\n Let’s take an example:<\/p>\n\n\n\n Here is the C++ program to solve the First Missing Positive problem:<\/p>\n\n\n\n Here is the Java program to solve it:<\/p>\n\n\n\n You can implement it in Python with the following code:<\/p>\n\n\n\n Output:<\/strong><\/p>\n\n\n\n As we are just moving once in the loop the time complexity is O(n). <\/strong>Space Complexity will be O(1)<\/strong> as we are not using any extra space.<\/p>\n\n\n\n Finally, here is a small comparison of the three methods:<\/p>\n\n\n\n![\"Example](\"https:\/\/lh7-us.googleusercontent.com\/8hQsb7pO2IyFlo7mRqoAC7TUCVLhC9MwdYbxpZrRcawHspJKhNldwFL8kQO-XDYTxYt1WnMOJjHx50QOvswcmA7tkqWdo8uQtNuGvO2OLWy9ofZCx5eyDKmpmjoDN6l-I-vMma4Zz9mlpp1_OhBzXpw\")
Naive Approach<\/strong><\/h3>\n\n\n\n
\n
![\"Given](\"https:\/\/lh7-us.googleusercontent.com\/x0qbytpFxJOR-ZU1JgM6s78lsEpCfltkcZU0ccDH5v_IS_vXWTvXxs5tj6kqIXFmRzR-M5qSVWMD6JyIsnHe4xE2r9WEcAKhs2Zani7PlYPmbTnXBVrMtpkVlvnUTZH8e6_jnsqK6uaYgHDeFEJgdWY\")
\n
![\"Check](\"https:\/\/lh7-us.googleusercontent.com\/6-H0rhUEWw1586CfWZDp0tHCTWSazRAQ2NjItaRuxULpGcLQ2UzXFHKHybPUPgYGSLOBUP6IuJ3GFd6bfWL0gQgY5AhmnBpLAO3-Hp30TKnDp2A9JGg3IPg_KL-z_Y16mLApSpzB-c3oU473uFNtQ_0\")
\n
![\"Check](\"https:\/\/lh7-us.googleusercontent.com\/sjBVAO0UIEJR_TM6dmfT7fMLFkTtvcueFihIYM480UO6cqZQdtWOAPw1hybpwS3uUceEyIH8YNVYT-FFc-3FdK1zTDP1nMptAC__kjM5cWYWlSB-9Qnipi1lwqQ5ezRjszPGLvWBsll4Cn6aBsOUa-w\")
\n
Sorting to Find the First Missing Positive<\/strong><\/h3>\n\n\n\n
\n
![\"After](\"https:\/\/lh7-us.googleusercontent.com\/2a2rLO71SzsfQrG7AFmjF-rvVn5pRngq6l7ACaR5DHGDN1dzZn6p8R3zbnr_96VFvfYuZtvnLTL43dUAQq0V-Xs9JW6pqjUyhcSSjVHMRNKtIzmA8E3rMHNNCe4AucLINwGHptjptIzWqVbEbDPwngw\")
\n
![\"Checking](\"https:\/\/lh7-us.googleusercontent.com\/SyvIhYyTkKQNWUjtnDoQ7sGFBuSpHboI-sEYj8HLQwvvtAykxK4kJbNYpvpMis_g7E68HxDkWF007X7RM_PZLQBOwcZgLxFAu_vMGC8N9Zk0M_2JfB4ya8TeePugkYQQTzPgZpi8mH0OkzSHh1TPe1U\")
\n
Optimized Sorting with Swap Approach<\/strong><\/h2>\n\n\n\n
\n
C++ Code<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint main(){\n\n vector<int> arr= {1,2,4,2,-1,0,5};\n int i=0;\n \/\/ n is the size of the array\n int n= arr.size();\n\n \/\/ iterating over the array\n while(i<n){\n \/\/checking if value at that index is less than that index or not \n if((i+1)>arr[i] && arr[i]>0){\n \/\/ if value present at the index which is equal to the value of the current index is less than or equal to the value of the current index update the previous value to -1.\n if(arr[arr[i]-1]<=arr[i]) arr[arr[i]-1]=-1; \n \/\/ now swap the value at the current index and the value at the index where the index is the same as the value of current index\n swap(arr[arr[i]-1], arr[i]);\n }\n else i++;\n }\n\n \/\/checking for the first missing +ve number \n for(i=0; i<n;i++){\n if(arr[i]<=0 || arr[i]!=i+1) {\n cout<<i+1<<endl;\n goto he;\n }\n }\n\n cout<<n+1<<endl;\n he:;\n \n return 0;\n}<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
import java.util.*;\n\nclass Main {\n public static void main(String[] args) {\n List<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 4, 2, -1, 0, 5));\n int i = 0;\n int n = arr.size();\n\n while (i < n) {\n if ((i + 1) > arr.get(i) && arr.get(i) > 0) {\n if (arr.get(arr.get(i) - 1) <= arr.get(i)) {\n arr.set(arr.get(i) - 1, -1);\n }\n int temp1 = arr.get(i);\n int temp2 = arr.get(arr.get(i)-1);\n arr.set(temp1-1, temp1);\n arr.set(i, temp2);\n } else {\n i++;\n }\n }\n\n boolean flag=false;\n for (i = 0; i < n; i++) {\n if (arr.get(i) <= 0 || arr.get(i) != i + 1) {\n System.out.println(i + 1);\n flag=true;\n break;\n }\n }\n\n if(flag==false) System.out.println(n + 1);\n }\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
def main():\n arr = [1, 2, 4, 2, -1, 0, 5]\n i = 0\n n = len(arr)\n\n while i < n:\n if 0 < arr[i] < i + 1:\n if arr[arr[i] - 1] <= arr[i]:\n arr[arr[i] - 1] = -1\n arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i] - 1]\n else:\n i += 1\n\n for i in range(n):\n if arr[i] <= 0 or arr[i] != i + 1:\n print(i + 1)\n break\n else:\n print(n + 1)\n\n\nif __name__ == "__main__":\n main()<\/pre><\/div>\n\n\n\n
3<\/code><\/pre>\n\n\n\n