kth-missing-positive-number

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

Given an array <code>arr</code> of positive integers sorted in a strictly increasing order, and an integer <code>k</code>.

Return the <code>kth</code> positive integer that is missing from this array.

&nbsp;
Example 1:

<pre>
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&nbsp;missing positive integer is 9.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>arr[i] &lt; arr[j]</code> for <code>1 &lt;= i &lt; j &lt;= arr.length</code></li>
</ul>

&nbsp;
Follow up:

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