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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Kth Missing Positive Number and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →