- Problem Statement<\/a><\/li>
- Approach 1: Looping Over Positive Integers<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Approach 2: Hashing Method<\/a><\/li>
- C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul>
- Approach 3<\/a><\/li>
- C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul>
- Approach 4<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Approach 5:<\/a><\/li>
- C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul>
- Approach 6<\/a><\/li>
- C++ Implementation For The Approach<\/a><\/li>
- Java Implementation For The Approach<\/a><\/li>
- Python Implementation For The Approach<\/a><\/li><\/ul>
- FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given an array containing both positive and negative numbers, find the smallest positive number excluded from the array.<\/p>\n\n\n\n
Sample Test Cases<\/strong><\/p>\n\n\n\n
Input 1:<\/strong> a = [2, 3, 7, 6, 8, -1, -10, 15]
Output 1:<\/strong> 1
Explanation 1:<\/strong> 1 is the smallest positive integer missing from the array.<\/p>\n\n\n\nInput 2:<\/strong> a = [2, 3, -7, 6, 8, 1, -10, 15]
Output 2:<\/strong> 4
Explanation 2:<\/strong> 4 is the smallest positive integer missing from the array.<\/p>\n\n\n\nApproach 1: Looping Over Positive Integers<\/h2>\n\n\n\n
We can solve the problem naively by looping over all the positive integers and checking if each of them is present in the array or not. Whenever a number is not found in the array, we return it and break the algorithm.<\/p>\n\n\n\n
C++ Code<\/span><\/h3>\n\n\n\n
int getMEX(vector < int > & a) {\n bool found = false;\n for (int i = 1;; i++) {\n found = false;\n for (auto x: a) {\n if (x == i) {\n found = true;\n break;\n }\n }\n if (!found) {\n return i;\n }\n }\n}<\/pre>\n\n\n\nJava Code<\/span><\/h3>\n\n\n\n
public static int getMEX(int[] a) {\n boolean found = false;\n for (int i = 1;; i++) {\n found = false;\n for (int j = 0; j < a.length; j++) {\n int x = a[j];\n if (x == i) {\n found = true;\n break;\n }\n }\n if (!found) {\n return i;\n }\n }\n}<\/pre>\n\n\n\nPython Code<\/span><\/h3>\n\n\n\n
def getMEX(a):\n found = False\n n = len(a)\n for i in range(1, n + 2):\n found = False\n for j in range(n):\n if a[j] == i:\n found = True\n break\n if found == False:\n return i<\/pre>\n\n\n\n
Complexity Analysis<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n * n)<\/li>
- Space Complexity: O(1)<\/li><\/ul>\n\n\n\n
Approach 2: Hashing Method<\/h2>\n\n\n\n
We can solve this problem in linear time by using hashing. We loop over all the positive numbers, and check if it is present in the array or not by using a lookup table or hash map in O(1) time. The first element not found in the array will be the answer.<\/p>\n\n\n\n
C++ Implementation<\/span><\/h3>\n\n\n\n
int getMEX(vector < int > & a) {\n int n = a.size();\n unordered_set < int > hash(a.begin(), a.end());\n for (int i = 1; i <= n + 1; i++) {\n if (hash.find(i) == hash.end()) {\n return i;\n }\n }\n}<\/pre>\n\n\n\nJava Implementation<\/span><\/h3>\n\n\n\n
public static int getMEX(int[] a) {\n int n = a.length;\n HashSet < Integer > hash = new HashSet < Integer > ();\n for (int i = 0; i < n; i++) {\n hash.add(a[i]);\n }\n for (int i = 1; i <= n + 1; i++) {\n if (!hash.contains(i)) {\n return i;\n }\n }\n return -1;\n}<\/pre>\n\n\n\nPython Implementation<\/span><\/h3>\n\n\n\n
def getMEX(a):\n n = len(a)\n b = a\n hash = set(b)\n for i in range(1, n + 2):\n if i not in hash:\n return i<\/pre>\n\n\n\n
Complexity Analysis<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n)<\/li>
- Space Complexity: O(n)<\/li><\/ul>\n\n\n\n
Approach 3<\/h2>\n\n\n\n
The algorithm is described as follows:<\/p>\n\n\n\n
- Move all the non-positive numbers to the left side of the array and separate out the positive numbers. After applying this function, all the nonpositive numbers in the array must appear before any positive number in the array.<\/li>
- We now start iterating on the array from the index which has the first positive element. For each element ele<\/strong>, to mark that it is present in the array, we change the value at index ele <\/strong>to its negative. Then, we again iterate on the array and return the first index with a positive value.<\/li><\/ul>\n\n\n\n
<\/figure>\n\n\n\n
C++ Implementation<\/span><\/h3>\n\n\n\n
int distribute(int a[], int n) {\n int j = 0;\n for (int i = 0; i < n; i++) {\n if (a[i] <= 0) {\n swap(a[i], a[j]);\n j++;\n }\n }\n return j;\n}\nint getMEXUtil(int a[], int till) {\n for (int i = 0; i < till; i++) {\n if (abs(a[i]) - 1 < till && a[abs(a[i]) - 1] > 0) {\n a[abs(a[i]) - 1] *= (-1);\n }\n }\n for (int i = 0; i < till; i++) {\n if (a[i] > 0) {\n return i + 1;\n }\n }\n return till + 1;\n}\nint getMEX(int a[], int n) {\n int moved = distribute(a, n);\n return getMEXUtil(a + moved, n - moved);\n}<\/pre>\n\n\n\nJava Implementation<\/span><\/h3>\n\n\n\n
public static int distribute(int a[], int n) {\n int j = 0;\n for (int i = 0; i < n; i++) {\n if (a[i] <= 0) {\n int temp = a[i];\n a[i] = a[j];\n a[j] = temp;\n j++;\n }\n }\n return j;\n}\npublic static int getMEXUtil(int a[], int till) {\n for (int i = 0; i < till; i++) {\n if (Math.abs(a[i]) - 1 < till && a[Math.abs(a[i]) - 1] > 0) {\n a[Math.abs(a[i]) - 1] *= (-1);\n }\n }\n for (int i = 0; i < till; i++) {\n if (a[i] > 0) {\n return i + 1;\n }\n }\n return till + 1;\n}\npublic static int getMEX(int a[], int n) {\n int moved = distribute(a, n);\n int[] aCopy = new int[n - moved];\n int j = 0;\n for (int i = moved; i < n; i++) {\n aCopy[j] = a[i];\n j++;\n }\n return getMEXUtil(aCopy, n - moved);\n}<\/pre>\n\n\n\nPython Implementation<\/span><\/h3>\n\n\n\n
def distribute(a, n):\n j = 0\n for i in range(n):\n if a[i] <= 0:\n temp = a[i]\n a[i] = a[j]\n a[j] = temp\n j += 1\n return j\n\n\ndef getMEXUtil(a, n):\n for i in range(n):\n x = abs(a[i])\n if x - 1 < n and a[x - 1] > 0:\n a[x - 1] *= -1\n for i in range(n):\n if a[i] > 0:\n return i + 1\n return n + 1\n\n\ndef getMEX(a, n):\n moved = distribute(a, n)\n return getMEXUtil(a[moved:], n - moved)<\/pre>\n\n\n\n
Complexity Analysis<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n)<\/li>
- Space Complexity: O(1)<\/li><\/ul>\n\n\n\n
Approach 4<\/h2>\n\n\n\n
We can solve this problem by making an auxiliary array of size the same as that of our given array. Now we traverse our original array, and whenever we find a positive value in the array, we update the index equal to that value with 1. Then we make another traversal through the auxiliary array and return the index + 1 <\/strong>\u00a0of the first 0 encountered.<\/p>\n\n\n\n
C++ Code<\/h3>\n\n\n\n
int getMEX(vector < int > & a, int n) {\n vector < bool > found(n + 2, false);\n for (auto x: a) {\n if (x > 0 && x <= n) {\n found[x] = true;\n }\n }\n for (int i = 1; i <= n + 1; i++) {\n if (!found[i]) {\n return i;\n }\n }\n return n + 1;\n}<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
public static int getMEX(int[] a, int n) {\n boolean[] found = new boolean[n + 2];\n for (int x: a) {\n if (x > 0 && x <= n) {\n found[x] = true;\n }\n }\n for (int i = 1; i <= n + 1; i++) {\n if (!found[i]) {\n return i;\n }\n }\n return n + 1;\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
def getMEX(a, n):\n found = [False] * (n + 2)\n for i in range(n):\n if a[i] > 0 and a[i] <= n:\n found[a[i]] = True\n for i in range(1, n + 2):\n if found[i] == False:\n return i\n return n + 1<\/pre>\n\n\n\n
Complexity Analysis<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n)<\/li>
- Space Complexity: O(n)<\/li><\/ul>\n\n\n\n
Approach 5:<\/h2>\n\n\n\n
The algorithm is described as follows:<\/p>\n\n\n\n
- If 1 is not present in the array, return 1.<\/li>
- Traverse the array and change every element less than 1 or greater than n<\/strong> to 1.<\/li>
- Traverse the array again and for each element a[i], update it to a[(a[i] – 1) % n] += n.<\/li>
- Again traverse the array and return the first index which has a value less than or equal to n. If not found, return n + 1<\/strong>.<\/li><\/ul>\n\n\n\n
C++ Implementation<\/h3>\n\n\n\n
int getMEX(vector < int > & a, int n) {\n bool ok = false;\n for (int i = 0; i < n; i++) {\n ok |= (a[i] == 1);\n }\n if (!ok) {\n return 1;\n }\n for (auto & x: a) {\n if (x <= 0 || x > n) {\n x = 1;\n }\n }\n for (int i = 0; i < n; i++) {\n a[((a[i] - 1) % n + n) % n] += n;\n }\n int result = n + 1;\n for (int i = 0; i < n; i++) {\n if (a[i] <= n) {\n result = i + 1;\n break;\n }\n }\n return result;\n}<\/pre>\n\n\n\nJava Implementation<\/h3>\n\n\n\n
public static int getMEX(int[] a, int n) {\n boolean ok = false;\n for (int i = 0; i < n; i++) {\n ok |= (a[i] == 1);\n }\n if (!ok) {\n return 1;\n }\n for (int i = 0; i < n; i++) {\n if (a[i] <= 0 || a[i] > n) {\n a[i] = 1;\n }\n }\n for (int i = 0; i < n; i++) {\n a[((a[i] - 1) % n + n) % n] += n;\n }\n int result = n + 1;\n for (int i = 0; i < n; i++) {\n if (a[i] <= n) {\n result = i + 1;\n break;\n }\n }\n return result;\n}<\/pre>\n\n\n\nPython Implementation<\/h3>\n\n\n\n
def getMEX(a, n):\n if 1 not in a:\n return 1\n for i in range(n):\n if a[i] <= 0 or a[i] > n:\n a[i] = 1\n for i in range(n):\n a[((a[i] - 1) % n + n) % n] += n\n for i in range(n):\n if a[i] <= n:\n return i + 1\n return n + 1<\/pre>\n\n\n\n
Complexity Analysis:<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n)<\/li>
- Space Complexity: O(1)<\/li><\/ul>\n\n\n\n
Approach 6<\/h2>\n\n\n\n
The algorithm is described as follows:<\/p>\n\n\n\n
- Traverse the array, and while a[i] > 1<\/strong> and a[i] <= n<\/strong> and a[i] != a[a[i] – 1], <\/strong>conditions are true, swap a[i]<\/strong> with a[a[i] – 1].<\/strong><\/li>
- Traverse the array again, and return the first index where a[i] != i + 1.<\/strong> If such an index is not found, return n + 1.<\/strong><\/li><\/ul>\n\n\n\n
C++ Implementation For The Approach<\/h3>\n\n\n\n
int getMEX(vector < int > & a, int n) {\n for (int i = 0; i < n; i++) {\n while (a[i] > 0 && a[i] <= n && a[i] != a[a[i] - 1]) {\n swap(a[i], a[a[i] - 1]);\n }\n }\n int result = n + 1;\n for (int i = 1; i <= n; i++) {\n if (i != a[i - 1]) {\n result = i;\n break;\n }\n }\n return result;\n}<\/pre>\n\n\n\nJava Implementation For The Approach<\/h3>\n\n\n\n
public static int getMEX(int[] a, int n) {\n for (int i = 0; i < n; i++) {\n while (a[i] > 0 && a[i] <= n && (a[i] != a[a[i] - 1])) {\n int temp = a[a[i] - 1];\n a[a[i] - 1] = a[i];\n a[i] = temp;\n }\n }\n int result = n + 1;\n for (int i = 1; i <= n; i++) {\n if (i != a[i - 1]) {\n result = i;\n break;\n }\n }\n return result;\n}<\/pre>\n\n\n\nPython Implementation For The Approach<\/h3>\n\n\n\n
def getMEX(a, n):\n for i in range(n):\n while a[i] > 0 and a[i] <= n and a[i] != a[a[i] - 1]:\n temp = a[a[i] - 1]\n a[a[i] - 1] = a[i]\n a[i] = temp\n for i in range(n):\n if a[i] != (i + 1):\n return i + 1\n return n + 1<\/pre>\n\n\n\n
Complexity Analysis<\/strong><\/p>\n\n\n\n
- Time Complexity: O(n)<\/li>
- Space Complexity: O(1)<\/li><\/ul>\n\n\n\n
FAQs<\/h2>\n\n\n\n
Q. Can this problem be solved by using sorting?<\/strong>
A. Yes, this problem can be solved using standard sorting algorithms, albeit in O(nlogn).<\/p>\n\n\n\nQ. What is the complexity of the lookup operations of hashmap in approach 2?<\/strong>
A. The lookup time complexity of hashmaps is amortized O(1)<\/strong> with the use of a good hash function.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array containing both positive and negative numbers, find the smallest positive number excluded from…\n","protected":false},"author":5,"featured_media":3689,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[560],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3607"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3607"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3607\/revisions"}],"predecessor-version":[{"id":3688,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3607\/revisions\/3688"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3689"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Traverse the array again, and return the first index where a[i] != i + 1.<\/strong> If such an index is not found, return n + 1.<\/strong><\/li><\/ul>\n\n\n\n
- Traverse the array, and while a[i] > 1<\/strong> and a[i] <= n<\/strong> and a[i] != a[a[i] – 1], <\/strong>conditions are true, swap a[i]<\/strong> with a[a[i] – 1].<\/strong><\/li>
- Java Implementation For The Approach<\/a><\/li>
- Java Implementation<\/a><\/li>
- Java Code<\/a><\/li>
- Java Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Java Code<\/a><\/li>
- Approach 1: Looping Over Positive Integers<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-8-1024x557.png\")
<\/figure>\n\n\n\n