Skip to main content

1539. Kth Missing Positive Number

easy

Given a sorted array of distinct positives, find the kth missing positive integer. The linear scan is obvious — the O(log n) trick rewards careful predicate design.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • arr[i] < arr[j] for 1 <= i < j <= arr.length

Examples

Example 1

Input
arr = [2,3,4,7,11], k = 5
Output
9

Explanation: The missing positives are [1,5,6,8,9,10,12,...]. The 5th missing is 9.

Example 2

Input
arr = [1,2,3,4], k = 2
Output
6

Explanation: The missing positives are [5,6,7,...]. The 2nd missing is 6.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Linear scan: walk the array, count how many integers are missing before each arr[i]. Stop when the count reaches k. O(n).

Hint 2

Key observation: at index i, the number of missing positives before arr[i] is arr[i] - (i + 1).

Hint 3

That count is monotonically non-decreasing in i — that is the cue to binary-search on the answer.

Hint 4

Find the smallest index i where arr[i] - (i + 1) >= k. The kth missing is k + i (when found) or k + n (when k exceeds all gaps).

Solution approach

Reveal approach

Let missing(i) = arr[i] - (i + 1) — the count of missing positives strictly before arr[i]. This function is monotonically non-decreasing because each step either keeps the gap the same (arr increases by 1) or widens it. Binary-search the leftmost index where missing(i) >= k: lo = 0, hi = n. While lo < hi, mid = lo + (hi - lo) / 2; if arr[mid] - (mid + 1) >= k, hi = mid; else lo = mid + 1. After the loop, the answer is lo + k. Intuition: if lo == n, all gaps were too small and the kth missing lies past the end (k + n). Otherwise, arr[lo] is the first element with enough missing before it, and lo + k correctly slots in. O(log n) time, O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • binary-search-on-answer

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google
  • Bloomberg

More Binary Search practice problems

See all Binary Search problems →