How do you solve Kth Missing Positive Number on LeetCode?

Kth Missing Positive Number (LeetCode #1539) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: The problem can be solved by leveraging the sorted nature of the input array.

What is the brute force solution for Kth Missing Positive Number?

The brute force approach for Kth Missing Positive Number is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each positive integer starting from 1 to see if it is in the array. If it's not, we count it as missing until we reach the k-th missing number. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Kth Missing Positive Number?

Kth Missing Positive Number uses the following concepts: Array, Binary Search. The recommended patterns to study are: Binary Search, Array.

What are the interview tips for Kth Missing Positive Number?

Always clarify the constraints and edge cases before jumping into coding. Explain your thought process clearly while coding, as it helps the interviewer understand your approach. Practice both brute force and optimal solutions to get comfortable with different problem-solving techniques.

What are common mistakes when solving Kth Missing Positive Number?

Not considering edge cases where k is larger than the number of missing integers in the array. Failing to understand how to calculate the number of missing integers up to a certain point.

#1539

Kth Missing Positive Number

Easy

ArrayBinary SearchBinary SearchArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

The optimal solution uses a binary search-like approach to efficiently find the k-th missing number by leveraging the sorted nature of the array. We can calculate how many numbers are missing up to each point in the array.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, left and right, to 0 and the length of the array respectively.
2Step 2: While left is less than right, calculate the mid-point and determine how many numbers are missing up to that point.
3Step 3: If the number of missing integers is less than k, move the left pointer to mid + 1.
4Step 4: If the number of missing integers is greater than or equal to k, move the right pointer to mid.
5Step 5: After the loop, return the result based on the left pointer's position.

solution.py15 lines

1# Full working Python code
2
3def findKthPositive(arr, k):
4    left, right = 0, len(arr)
5    while left < right:
6        mid = (left + right) // 2
7        missing = arr[mid] - (mid + 1)
8        if missing < k:
9            left = mid + 1
10        else:
11            right = mid
12    return left + k
13
14# Example usage
15print(findKthPositive([2,3,4,7,11], 5))  # Output: 9

ℹ

Complexity note: This complexity is achieved because we are using a binary search approach, which reduces the number of checks we need to perform significantly compared to the brute force method.

1The problem can be solved by leveraging the sorted nature of the input array.
2Using a binary search approach allows us to find the k-th missing number efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.