What is the time complexity of Kth Missing Positive Number?

The optimal solution has a time complexity of O(n + k).

What data structures are used to solve Kth Missing Positive Number?

This problem uses Array, Binary Search. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Kth Missing Positive Number?

The array is sorted, allowing us to efficiently check for missing numbers. We can use a two-pointer approach (one for the array and one for the expected positive integer) to iterate and count missing numbers.

Which companies ask LeetCode 1539. Kth Missing Positive Number in interviews?

This problem is frequently asked at Arista Networks, Morgan Stanley.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Kth Missing Positive Number - LeetCode 1539 Solution

Q: How to solve Kth Missing Positive Number?

The solution uses a linear scan approach. It maintains two pointers: one iterates through the input array (`i`), and another keeps track of the expected positive integer (`expected`). The algorithm iteratively compares the current element in the array with the expected integer. If they match, it means that integer is present, and we move to the next expected integer. If they don't match, it indicates a missing integer; we increment a `missing` counter and the `expected` integer. This process continues until `missing` reaches `k`, at which point `expected` holds the kth missing positive integer.

Kth Missing Positive Number - Complete Solution Guide

Kth Missing Positive Number is LeetCode problem 1539, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array arr of positive integers sorted in a strictly increasing order , and an integer k . Return the k th positive integer that is missing from this array. Example 1: Input: arr = [2,3,4,7,11], k = 5 Output: 9 Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5 th missing positive integer is 9. Example 2: Input: arr = [1,2,3,4], k = 2 Output: 6 Explanation: The missing positive integers are [5,6,7,...]. The 2 nd missing positive integer is 6. Constraints: 1 <=

Detailed Explanation

The problem asks you to find the kth positive integer that is missing from a sorted array of positive integers. The input is an array `arr` containing strictly increasing positive integers and an integer `k`. The output is the kth positive integer that's missing from the array. For example, if `arr` is [2, 3, 4, 7, 11] and `k` is 5, the missing positive integers are [1, 5, 6, 8, 9, 10, 12, 13...], and the 5th missing positive integer is 9.

Solution Approach

The solution uses a linear scan approach. It maintains two pointers: one iterates through the input array (`i`), and another keeps track of the expected positive integer (`expected`). The algorithm iteratively compares the current element in the array with the expected integer. If they match, it means that integer is present, and we move to the next expected integer. If they don't match, it indicates a missing integer; we increment a `missing` counter and the `expected` integer. This process continues until `missing` reaches `k`, at which point `expected` holds the kth missing positive integer.

Step-by-Step Algorithm

Initialize `missing` to 0, `expected` to 1, and `i` to 0 (index for the array).
Iterate while `missing` is less than `k`:
If `i` is within the array bounds and `arr[i]` equals `expected`, increment `i` (the expected number is present).
Otherwise, increment `missing` (a number is missing).
In either case, if `missing` is still less than `k`, increment `expected` (move to the next expected number).
After the loop, `expected` will hold the kth missing positive integer.

Key Insights

The array is sorted, allowing us to efficiently check for missing numbers.
We can use a two-pointer approach (one for the array and one for the expected positive integer) to iterate and count missing numbers.
No complex data structures are needed; we can solve this problem using only a few integer variables.

Complexity Analysis

Time Complexity: O(n + k)

Space Complexity: O(1)

Topics

This problem involves: Array, Binary Search.

Companies

Asked at: Arista Networks, Morgan Stanley.

Kth Missing Positive Number | LeetCode 1539

Easy

Array Binary Search

Time: O(n + k)Space: O(1)

Solution Code

Available in:

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int missing = 0;
        int expected = 1;
        int i = 0;
        while (missing < k) {
            if (i < arr.length && arr[i] == expected) {
                i++;
            } else {
                missing++;
            }
            if (missing < k) {
                expected++;
            }
        }
        return expected;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1539: Kth Missing Positive Number - Detailed explanation and solution approaches.

Topics

Array Binary Search

Companies

Arista NetworksMorgan Stanley

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:1539

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Initialize `missing` to 0, `expected` to 1, and `i` to 0 (index for the array).
2
Iterate while `missing` is less than `k`:
3
If `i` is within the array bounds and `arr[i]` equals `expected`, increment `i` (the expected number is present).
4
Otherwise, increment `missing` (a number is missing).
5
In either case, if `missing` is still less than `k`, increment `expected` (move to the next expected number).
6
After the loop, `expected` will hold the kth missing positive integer.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n + k)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The while loop iterates at most `n + k` times in the worst case (where `n` is the length of the array and `k` is the target missing number index). In the worst case, we might iterate through the entire array and then further iterate until `missing` reaches `k`. The solution uses only a few integer variables, so the space complexity is constant.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Binary Search

Since the array is sorted, we can use binary search to find the range of numbers present and then calculate the kth missing number from that.

Time: O(log n)Space: O(1)

Trade-offs: Binary search is more efficient than the linear scan when n is large, achieving logarithmic time complexity. However, the linear scan approach is simpler to understand and implement.

✨

Key Insights

1The array is sorted, allowing us to efficiently check for missing numbers.
2We can use a two-pointer approach (one for the array and one for the expected positive integer) to iterate and count missing numbers.
3No complex data structures are needed; we can solve this problem using only a few integer variables.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Empty array: The code handles this correctly; the loop will not execute if the array is empty, and `expected` will remain 1.
k larger than the number of missing integers: The loop will continue until `missing` reaches `k`. The algorithm finds the correct value even if `k` is larger than the count of missing numbers before exceeding the range of integers in the input array

⚠️

Common Mistakes to Avoid

✗Incorrectly handling the case where k is larger than the number of missing integers. The code must correctly handle this case and calculate the expected number instead of just looping indefinitely.

✗Off-by-one errors in incrementing counters or index variables. Carefully check the loop conditions and incrementing logic to avoid these errors.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Data cleaning and imputation: Identifying missing values in datasets and filling them with appropriate values.

🏦Network and system diagnostics: Identifying missing packets or sequence numbers in network traffic.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Can binary search be applied to non-sorted arrays?

Binary search requires a monotonic property, not necessarily sorted data. It can be applied to any search space where you can determine if the answer is in the left or right half. Examples include searching rotated arrays or finding minimum in optimization problems.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Kth Missing Positive Number"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?