Kth Missing Positive Number

Kth Missing Positive Number is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.

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.

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 5th 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 2nd missing positive integer is 6.

Constraints:

- 1 <= arr.length <= 1000

- 1 <= arr[i] <= 1000

- 1 <= k <= 1000

- arr[i] < arr[j] for 1 <= i < j <= arr.length

Follow up:

Could you solve this problem in less than O(n) complexity?

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Facebook, Amazon, Microsoft, Apple.

How to practise Kth Missing Positive Number on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Kth Missing Positive Number in the code editor, or read the Kth Missing Positive Number editorial for a worked solution with its approach and complexity analysis.

Where Kth Missing Positive Number sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Sorted Array/List subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Kth Missing Positive Number

Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:

• Binary Search — Easy, same subpattern
• First Bad Version — Easy, same subpattern
• Guess Number Higher or Lower — Easy, same subpattern
• Search a 2D Matrix — Medium, same subpattern
• Search Insert Position — Easy, same subpattern
• Single Element in a Sorted Array — Medium, same subpattern