Missing Positive Integers (Q71)

[sudosf]

Problem

Given array arr of size n, find the kth smallest positive integer not present in the array. Duplicates do not affect what is missing.

Source

Nedbank VAS HackerRank Assessment - Q71
Tags: Easy, Arrays, Sorting, Binary Search

References

• Related pattern: Pattern: Binary Search #19

Constraints

• 1 <= n <= 2 * 10^5
• 1 <= arr[i] <= 10^9
• 1 <= k <= 10^12

Example

n=5, arr=[1,4,7,3,4], k=5
Missing: [2,5,6,8,9]
Output: 9

Approach Hints

• Brute force won't work for k up to 10^12
• Given a sorted distinct array, how many positive integers <= v are missing?
• Binary search on the answer using that count as a predicate

Complexity Target

• Time: O(n log n) sort + O(log n) binary search
• Space: O(n) for the distinct set

Notes

Language: Java
k can exceed int range - use long throughout.

[sudosf]

leetcode: https://leetcode.com/problems/kth-missing-positive-number/