k-th missing element in an unsorted array

0 0 5 minutes read

Given an unsorted sequence a[], the task is to find the K-th missing contiguous element in the increasing sequence of the array elements i.e. consider the array in sorted order and find the kth missing number. If no k-th missing element is there output -1.
Note: Only elements exists in the range of minimum and maximum element to be considered.
Examples:

Input: arr[] = {2, 4, 10, 7}, k = 5
Output: 9
Missing elements in the given array: 3, 5, 6, 8, 9
5th missing is 9.

Input: arr[] = {1, 3, 4}, k = 5
Output: -1

Method-1: Sort the array and use the approach used in the k-th missing element in a sorted array.
Method-2:

Insert all the elements in an unordered_set.
Find the minimum and maximum element of the array.
Traverse the elements from minimum to maximum.
- Check if current element is present in the set or not.
- If not then check if this is kth missing by counting the missing elements.
- Return the current element if this is current missing.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum
// of minimum of all subarrays
int findKth(int arr[], int n, int k)
{
 
    unordered_set<int> missing;
    int count = 0;
 
    // Insert all the elements in a set
    for (int i = 0; i < n; i++)
        missing.insert(arr[i]);
 
    // Find the maximum and minimum element
    int maxm = *max_element(arr, arr + n);
    int minm = *min_element(arr, arr + n);
 
    // Traverse from the minimum to maximum element
    for (int i = minm + 1; i < maxm; i++) {
        // Check if "i" is missing
        if (missing.find(i) == missing.end())
            count++;
 
        // Check if it is kth missing
        if (count == k)
            return i;
    }
 
    // If no kth element is missing
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 10, 9, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << findKth(arr, n, k);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
    // Function to find the sum
    // of minimum of all subarrays
    static int findKth(int arr[], int n, int k) 
    {
 
        HashSet<Integer> missing = new HashSet<>();
        int count = 0;
 
        // Insert all the elements in a set
        for (int i = 0; i < n; i++)
        {
            missing.add(arr[i]);
        }
 
        // Find the maximum and minimum element
        int maxm = Arrays.stream(arr).max().getAsInt();
        int minm = Arrays.stream(arr).min().getAsInt();
 
        // Traverse from the minimum to maximum element
        for (int i = minm+1; i < maxm; i++)
        {
            // Check if "i" is missing
            if (!missing.contains(i)) 
            { 
                count++;
            }
 
            // Check if it is kth missing
            if (count == k)
            { 
                return i;
            }
        }
         
        // If no kth element is missing
        return -1;
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        int arr[] = {2, 10, 9, 4};
        int n = arr.length;
        int k = 5;
        System.out.println(findKth(arr, n, k));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python

# Python3 implementation of the above approach
 
# Function to find the sum
# of minimum of all subarrays
def findKth( arr, n, k):
 
    missing = dict()
    count = 0
 
    # Insert all the elements in a set
    for i in range(n):
        missing[arr[i]] = 1
 
    # Find the maximum and minimum element
    maxm = max(arr)
    minm = min(arr)
 
    # Traverse from the minimum to maximum element
    for i in range(minm + 1, maxm):
         
        # Check if "i" is missing
        if (i not in missing.keys()):
            count += 1
 
        # Check if it is kth missing
        if (count == k):
            return i
     
    # If no kth element is missing
    return -1
 
# Driver code
arr = [2, 10, 9, 4 ]
n = len(arr)
k = 5
print(findKth(arr, n, k))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the above approach 
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG 
{ 
 
    // Function to find the sum 
    // of minimum of all subarrays 
    static int findKth(int []arr, int n, int k) 
    { 
 
        HashSet<int> missing = new HashSet<int>(); 
        int count = 0; 
 
        // Insert all the elements in a set 
        for (int i = 0; i < n; i++) 
        { 
            missing.Add(arr[i]); 
        } 
 
        // Find the maximum and minimum element 
        int maxm = arr.Max(); 
        int minm = arr.Min(); 
 
        // Traverse from the minimum to maximum element 
        for (int i = minm + 1; i < maxm; i++) 
        { 
            // Check if "i" is missing 
            if (!missing.Contains(i)) 
            { 
                count++; 
            } 
 
            // Check if it is kth missing 
            if (count == k) 
            { 
                return i; 
            } 
        } 
         
        // If no kth element is missing 
        return -1; 
    } 
 
    // Driver code 
    public static void Main(String[] args) 
    { 
        int []arr = {2, 10, 9, 4}; 
        int n = arr.Length; 
        int k = 5; 
        Console.WriteLine(findKth(arr, n, k)); 
    } 
} 
 
// This code has been contributed by 29AjayKumar

PHP

<?php
// PHP implementation of the above approach 
 
// Function to find the sum 
// of minimum of all subarrays 
function findKth($arr, $n, $k)
{
 
    $missing = array();
    $count = 0;
 
    // Insert all the elements in a set 
    for ($i = 0; $i < $n; $i++)
        array_push($missing, $arr[$i]);
 
    $missing = array_unique($missing);
     
    // Find the maximum and minimum element 
    $maxm = max($arr);
    $minm = min($arr);
 
    // Traverse from the minimum to
    // maximum element 
    for ($i = $minm + 1; $i < $maxm; $i++)
    {
        // Check if "i" is missing 
        if (!in_array($i, $missing, false))
            $count += 1;
 
        // Check if it is kth missing 
        if ($count == $k) 
            return $i;
    }
     
    // If no kth element is missing 
    return -1;
}
 
// Driver code 
$arr = array(2, 10, 9, 4); 
$n = sizeof($arr); 
$k = 5;
 
echo findKth($arr, $n, $k);
 
// This code is contributed by Ryuga
?>

Javascript

<script>
 
// javascript implementation of the above approach
 
// Function to find the sum
// of minimum of all subarrays
function findKth(arr, n, k)
{
 
    var missing = new Set();
    var count = 0;
 
    // Insert all the elements in a set
    for (var i = 0; i < n; i++)
        missing.add(arr[i]);
 
    // Find the maximum and minimum element
    var maxm = arr.reduce((a,b)=>Math.max(a,b));
    var minm = arr.reduce((a,b)=>Math.min(a,b));
 
    // Traverse from the minimum to maximum element
    for (var i = minm + 1; i < maxm; i++) {
        // Check if "i" is missing
        if (!missing.has(i))
            count++;
 
        // Check if it is kth missing
        if (count == k)
            return i;
    }
 
    // If no kth element is missing
    return -1;
}
 
// Driver code
var arr = [ 2, 10, 9, 4 ];
var n = arr.length;
var k = 5;
document.write( findKth(arr, n, k));
 
// This code is contributed by noob2000.
</script>

Output:

Time complexity: O(n) where n is size of input array

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!