1539 || Kth Missing Positive Number || Leetcode Daily Problem

Problem Link :- leetcode-1539

Problem statement

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Return the kth positive integer that is missing from this array.

Easiest Explanation

Hey there! So you have an array of numbers that are sorted in order. But some numbers are missing in between, and you need to find the kth missing number.

Let me explain how we can do that. We can start by looking at the first number in the array and comparing it to 1. If it's not equal to 1, then 1 is the first missing number.

Next, we can go through the array one by one and check the difference between the current number and the previous number. If the difference is greater than 1, then we know that some numbers are missing in between. We can count the number of missing numbers and keep adding them up.

Finally, we can compare the total count of missing numbers with the given value of k. If the count of missing numbers is less than k, we can continue looking for more missing numbers. But if the count of missing numbers is greater than or equal to k, we have found the kth missing number.

So we just need to add the value of k to the first missing number we found and subtract the total count of missing numbers from it. This will give us the kth missing number.

I hope that explanation helps! If you find any difficulty in solving, feel free to comment with your doubts.

Python Code :

class Solution(object):
        def findKthPositive(self, arr, k):
            missing_count = 0
            prev_num = 0

            for num in arr:
                missing_count += num - prev_num - 1
                if missing_count >= k:
                    return num - (missing_count - k + 1)
                prev_num = num

            # If we reach here, it means kth missing number is after the last number
            return arr[-1] + (k - missing_count)

CPP Code

 class Solution {
    public:
        int findKthPositive(vector<int>& arr, int k) {
            vector mp(2001,0);
            for(auto i:arr){
                mp[i]++;
            }
            for(int i=1;i<=2001;i++){
                    if(mp[i]==0) k--;
                    if(k==0) return i;
            }
            return -1;
        }
};
    

Here's how the function works:

This code is a function that takes in a vector of integers "arr" and an integer "k" as parameters. The function finds the kth positive integer that is not present in the "arr" vector.Here's a step-by-step breakdown of what the code does:

1. The function creates a new vector "mp" of size 2001, and initializes all the elements to zero. This vector will be used to keep track of how many times each integer appears in the "arr" vector.

2. The function loops through each element "i" in the "arr" vector, and increments the corresponding element in the "mp" vector. This is done using the "auto" keyword, which automatically deduces the type of "i".

3. The function then loops through all integers from 1 to 2001 using a for loop. For each integer "i" in this range, the function checks if it appears in the "arr" vector. If it does not appear, then the function decrements the value of "k" by 1. This is because we are looking for the kth positive integer that is not present in the "arr" vector.

4. If the value of "k" reaches 0, then the function has found the kth positive integer that is not present in the "arr" vector. The function returns this integer.

5. If the function has looped through all integers from 1 to 2001 and still has not found the kth positive integer that is not present in the "arr" vector, then the function returns -1, which indicates that such an integer does not exist.

Overall, the function uses a vector to keep track of how many times each integer appears in the input array, and then loops through all integers from 1 to 2001 to find the kth positive integer that is not present in the array.

More Than Code: What I Discovered by Solving Problems

The journey of solving the "Kth Missing Positive Integer" problem unveils valuable insights and learnings that extend beyond the realms of coding. As we unravel the intricacies of this challenge, several key takeaways emerge, contributing to the growth and refinement of problem-solving skills.

• Array Manipulation Proficiency : This problem serves as a crucible for honing array manipulation skills. The process of creating a frequency map and traversing through a sorted array necessitates a deep understanding of how to efficiently navigate and manipulate arrays in a programmatic context.
• Algorithmic Thinking : The two-step approach employed in this solution reflects the essence of algorithmic thinking. Breaking down the problem into smaller, manageable tasks and strategizing an efficient solution showcases the ability to think algorithmically—a crucial skill in tackling complex coding challenges.
• Frequency Mapping as a Strategy : The use of a frequency map introduces a powerful strategy for dealing with problems involving counting and tracking occurrences. This technique is not only applicable to this specific problem but can be a valuable tool in various scenarios where understanding the frequency of elements is essential.
• Counter-Based Approach : The implementation of a counter-based approach to identify missing integers is a concept that transcends this particular problem. Understanding how to use counters effectively in algorithms is a skill that proves beneficial in diverse programming scenarios.
• Critical Thinking and Debugging : As with any coding challenge, the process of solving this problem involves critical thinking and debugging. Identifying edge cases, ensuring the correctness of the algorithm, and iteratively refining the solution contribute to the development of a robust problem-solving mindset.
• Application of Data Structures : While the problem itself may not explicitly involve complex data structures, the use of a simple vector as a frequency map exemplifies the practical application of data structures to enhance the efficiency and clarity of the solution.
• Optimization Opportunities : Solving this problem opens the door to optimization discussions. The algorithm, while functional, may be refined or optimized further. This encourages the exploration of alternative strategies and fosters a mindset of continuous improvement.

Conclusion

To wrap it up, figuring out the "Kth Missing Positive Integer" problem is like going on an adventure in the coding world. But it's not just about typing code; it teaches us useful stuff.

Think of it as getting really good at organizing lists of numbers. We learn a cool trick of making a checklist to keep track of which numbers are there and which ones are missing. This trick isn't just for this puzzle; it's like a secret weapon we can use in other coding challenges.

The way we solve the problem also shows us how to break big problems into smaller, easier parts. It's like taking apart a big puzzle and solving each piece one by one. And counting the missing numbers helps us become experts at using counters, which is handy in lots of coding situations.

But here's the cool part: this isn't just about coding on the computer. It's like practicing for real-life situations where things are organized, but you need to find something missing. So, by working on this coding puzzle, we're not just becoming better at coding; we're becoming awesome problem-solvers in the real world of programming. It's like leveling up in a game, but the game is coding!

Stay up-to-date with our latest content by subscribing to our channel! Don't miss out on our next video - make sure to subscribe today.