Hi, Welcome to tech-maze, today's article is going to be slick, we are going to explore a unique programming question which has been asked in MAANG companies, initially it looks quite straight forward but there are few scenarios which makes this question difficult to understand, i have tried my best to reduce the complexity as much as possible.
Lets have a look into the question and later will solve it
Question :-
find the kth missing element in a given array, to obtained the kth missing element there is no boundary in the array, search can go beyond the size of array.
above question is quite vague and doesn't actually explain much, so i am going to break this down to understand what actually it refers to
As per the question we have to consider following scenarios
if the value of k lands within the range of array
scenario 1 : if an array has values [1,3,4,5,6] and k is 1 then the 1st missing element would be 2
scenario 2 : if an array has values [1,3,4,5,7] and k is 2 then the 2nd missing element would be 6
scenario 3 : if an array has values [1,3,4,5,7] and k is 1 then the 1st missing element would be 2
if the value of k goes beyond the range of array, lets see what this actually implies to
scenario 4 : if an array has values [1,3,4,5,6,7] and k is 2 then the 2nd missing element would be 8, the reason being, because array contains values up to 7 and there is only one number missing then we have to go beyond the range of array, after 7, array doesn't contain any element hence rest all element will be considered as missing, hence 2nd missing element would be 8.
scenario 5 : if an array has values [1,2,3,4,5,6,7] and k is 3, then the missing element would be 10, the reason being, because there is no missing element in the given array hence missing element starts after 7 so 8 would be 1st missing element, 9 would be 2nd missing element and 10 would be 3rd missing element, hence the 3rd missing element would be 10.
Now lets see how we can derive all these scenarios in a program.
public static int missingElement(int[] arr, int k){
if(arr.length<1 || k<1)
return -1;
Stack<Integer> stk = new Stack<>();
int count = 1;
for(int i=0; i<arr.length; i++){
if(count == arr[i]){
count++;
}else{
stk.push(count);
count = arr[i];
i = i-1;
}
if(stk.size() == k){
return stk.pop();
}
}
while(stk.size()<k) {
stk.push(count);
count++;
}
return stk.pop();
}
Lets quickly go through the logic----
Step 1 : check for the input parameter to avoid exceptions, this is very important step
as MAANG companies look for how few negative scenarios has been handled
Step 2 : declare stack data structure, variable (count), initialize it with 1 and start
iterating through the array.
Step 3 : here first we have to check if count is equal to 1st element of array
if yes --> increment the count
if no --> push count in stack, assign array index value to count and reduce
variable i by 1, now question arise why we are doing this and the
reason being, because we want to point count to current element and reduce the variable i by 1 to make sure that when next iteration starts count and i (increment by 1 via loop ) both points to same variable/index
then we check if the size of stack is equal to value of k
if yes --> return the value from stack,
else --> continue iterating through the loop.
this process runs till loop reaches the end of the array
this logic takes care of bounded array scenarios when value of k doesn't go beyond the size of array.
Step 4 : In this step, we will take care of unbounded array scenarios, where value of k goes beyond the size of array. Here we start a while loop where
we compare the size of stack with k, and this process runs till stack size is less than value of k, during the process we add count in the stack
Step 5 : once loop ends return the element from the stack, and this will
be our kth missing element.
Here this article ends.
Please let me know what you guys think about the solution, feel free to share this article and share your suggestion/thoughts/solutions in comment section.
for complete code please have a look in the below GitHub project
Git location : https://github.com/rohitmodi07/Programs
File Name : FindKthMissingElement
That's all folks in this article, keep visiting tech-maze for more of Data Structure and System Design related topics
A Big thank you for checking out my article, this really encourage me to come up with more topics.