Find largest positive integer x missing from unsorted array such that min(arr[]) < x < max(arr[])
Given an array arr[] containing integers. The task is to find the largest positive integer x missing from the array such that min(arr[]) < x < max(arr[]).
Examples
Input: arr[] = {2, 3, 7, 6, 8}
Output: 5
Explanation: 5 is the largest positive integer missing from arr[] and 2 < 5 < 8.Input: arr[] = { 2, 3, -7, 1, 4 }
Output: -1
Naive Approach: Sort the array in descending and return the first missing positive number. If none is missing, return -1.
Algorithm:
- Initialize variables max_val and min_val to store the maximum and minimum values in the given array, and initialize an array of size (max_val – min_val + 1) with all elements as 0.
- Traverse the given array and for each element, if it lies within the range [min_val, max_val], mark the corresponding index in the new array as 1.
- Traverse the new array starting from index 1 and find the first index i such that the corresponding element is 0. Return i + min_val as the answer.
- If no such index is found, return -1 to indicate that no missing positive integer was found in the given range.
Below is the implementation of the approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; // Function to find the largest positive integer missing int largestMissingPositive( int arr[], int n) { // Sort the array in descending order sort(arr, arr + n, greater< int >()); int max_num = arr[0]; int min_num = arr[n - 1]; int missing_num = -1; // Traverse the sorted array to find the missing number for ( int i = max_num - 1; i >= min_num + 1; i--) { bool found = false ; // Check if the current number is present in the // array for ( int j = 0; j < n; j++) { if (arr[j] == i) { found = true ; break ; } } // If the current number is not present, return it if (!found) { missing_num = i; break ; } } return missing_num; } // Driver's code int main() { int arr[] = { 2, 3, 7, 6, 8 }; int n = sizeof (arr) / sizeof (arr[0]); int missing_num = largestMissingPositive(arr, n); if (missing_num == -1) { cout << -1 << endl; } else { cout << missing_num << endl; } return 0; } |
Java
/*package whatever //do not write package name here */ import java.util.Arrays; public class Main { // Function to find the largest positive integer missing static int largestMissingPositive( int [] arr, int n) { // Sort the array in descending order Arrays.sort(arr); int maxNum = arr[n - 1 ]; int minNum = arr[ 0 ]; int missingNum = - 1 ; // Traverse the sorted array to find the missing number for ( int i = maxNum - 1 ; i >= minNum + 1 ; i--) { boolean found = false ; // Check if the current number is present in the array for ( int j = 0 ; j < n; j++) { if (arr[j] == i) { found = true ; break ; } } // If the current number is not present, return it if (!found) { missingNum = i; break ; } } return missingNum; } // Driver's code public static void main(String[] args) { int [] arr = { 2 , 3 , 7 , 6 , 8 }; int n = arr.length; int missingNum = largestMissingPositive(arr, n); if (missingNum == - 1 ) { System.out.println(- 1 ); } else { System.out.println(missingNum); } } } //This code is contributed by aeroabrar_31 |
Python3
def largestMissingPositive(arr): # Sort the array in descending order arr.sort(reverse = True ) maxNum = arr[ 0 ] minNum = arr[ - 1 ] missingNum = - 1 # Traverse the sorted array to find the missing number for i in range (maxNum - 1 , minNum, - 1 ): found = False # Check if the current number is present in the array for num in arr: if num = = i: found = True break # If the current number is not present, return it if not found: missingNum = i break return missingNum # Driver's code arr = [ 2 , 3 , 7 , 6 , 8 ] missingNum = largestMissingPositive(arr) if missingNum = = - 1 : print ( - 1 ) else : print (missingNum) |
C#
using System; using System.Linq; public class GFG { // Function to find the largest positive integer missing public static int LargestMissingPositive( int [] arr, int n) { // Sort the array in descending order Array.Sort(arr, (x, y) => y.CompareTo(x)); int max_num = arr[0]; int min_num = arr[n - 1]; int missing_num = -1; // Traverse the sorted array to find the missing // number for ( int i = max_num - 1; i >= min_num + 1; i--) { bool found = false ; // Check if the current number is present in the // array for ( int j = 0; j < n; j++) { if (arr[j] == i) { found = true ; break ; } } // If the current number is not present, return // it if (!found) { missing_num = i; break ; } } return missing_num; } public static void Main() { int [] arr = { 2, 3, 7, 6, 8 }; int n = arr.Length; int missing_num = LargestMissingPositive(arr, n); if (missing_num == -1) { Console.WriteLine(-1); } else { Console.WriteLine(missing_num); } } } |
Javascript
// JS code for the approach // Function to find the largest positive leteger missing function largestMissingPositive(arr, n) { // Sort the array in descending order arr.sort(); arr.reverse(); let max_num = arr[0]; let min_num = arr[n - 1]; let missing_num = -1; // Traverse the sorted array to find the missing number for (let i = max_num - 1; i >= min_num + 1; i--) { let found = false ; // Check if the current number is present in the // array for (let j = 0; j < n; j++) { if (arr[j] == i) { found = true ; break ; } } // If the current number is not present, return it if (!found) { missing_num = i; break ; } } return missing_num; } // Driver's code let arr = [ 2, 3, 7, 6, 8 ]; let n = arr.length; let missing_num = largestMissingPositive(arr, n); if (missing_num == -1) { console.log(-1); } else { console.log(missing_num); } |
5
Time Complexity: O(N logN)
Time Complexity: O(1)
Efficient Approach: This problem can be solved by using Hashing. Build a Hashmap of all positive elements in the given array. After building Hashmap, look in the HashMap from reverse, and return the first missing positive number. If none is missing, return -1.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find missing positive integer int firstMissingPositive(vector< int >& nums) { int n = nums.size(); // Map to store the elements map< int , int > m; for ( int i = 0; i < n; i++) { if (m.find(nums[i]) == m.end()) { m.insert({ nums[i], 1 }); } } int ans = 0; // Traversing the Hashmap from reverse for (ans = m.rbegin()->first; ans > 0; ans--) { if (m.find(ans) == m.end()) break ; } return ans; } // Driver code int main() { vector< int > arr = { 2, 3, 7, 6, 8 }; int missing = firstMissingPositive(arr) == 0 ? -1 : firstMissingPositive(arr); cout << missing; return 0; } |
Java
// Java program for above approach import java.util.*; class GFG { // Function to find missing positive integer public static int firstMissingPositive( int [] nums) { int n = nums.length; // Map to store the elements HashMap<Integer, Integer> m = new HashMap<>(); for ( int i = 0 ; i < n; i++) { if (m.containsKey(nums[i]) == false ) { m.put(nums[i], 1 ); } } int ans = 0 ; for (Map.Entry<Integer, Integer> temp : m.entrySet()) { ans = Math.max(ans, temp.getKey()); } // Traversing the Hashmap from reverse for (; ans > 0 ; ans--) { if (m.containsKey(ans) == false ) break ; } return ans; } // Driver code public static void main(String[] args) { int [] arr = { 2 , 3 , 7 , 6 , 8 }; if (firstMissingPositive(arr) == 0 ) System.out.print(- 1 ); else System.out.print(firstMissingPositive(arr)); } } // This code is contributed by Taranpreet |
Python3
# Python program for above approach # Function to find missing positive integer def firstMissingPositive(nums): n = len (nums) # Map to store the elements m = {} for i in range (n): if (nums[i] not in m): m[nums[i]] = 1 ans = 0 for itm in m.keys(): ans = max (ans, itm) # Traversing the Hashmap from reverse while (ans > = 0 ): if (ans not in m): break ans - = 1 return ans # Driver code arr = [ 2 , 3 , 7 , 6 , 8 ] missing = - 1 if firstMissingPositive(arr) = = 0 else firstMissingPositive(arr) print (missing) # This code is contributed by shinjanpatra |
C#
// C# program for above approach using System; using System.Collections.Generic; public class GFG { // Function to find missing positive integer public static int firstMissingPositive( int [] nums) { int n = nums.Length; // Map to store the elements Dictionary< int , int > m = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { if (m.ContainsKey(nums[i]) == false ) { m.Add(nums[i], 1); } } int ans = 0; foreach (KeyValuePair< int , int > temp in m) { ans = Math.Max(ans, temp.Key); } // Traversing the Hashmap from reverse for (; ans > 0; ans--) { if (m.ContainsKey(ans) == false ) break ; } return ans; } // Driver code public static void Main(String[] args) { int [] arr = { 2, 3, 7, 6, 8 }; if (firstMissingPositive(arr) == 0) Console.Write(-1); else Console.Write(firstMissingPositive(arr)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for above approach // Function to find missing positive integer const firstMissingPositive = (nums) => { let n = nums.length; // Map to store the elements let m = {}; for (let i = 0; i < n; i++) { if (!(nums[i] in m)) { m[nums[i]] = 1; } } let ans = 0; for (let itm in m) ans = Math.max(ans, itm); // Traversing the Hashmap from reverse for (; ans > 0; ans--) { if (!(ans in m)) break ; } return ans; } // Driver code let arr = [2, 3, 7, 6, 8]; let missing = firstMissingPositive(arr) == 0 ? -1 : firstMissingPositive(arr); document.write(missing); // This code is contributed by rakeshsahni </script> |
5
Time Complexity: O(N)
Auxiliary Space: O(N)