Jobs

Interviews

Discussions

Kth Missing Positive Number

Easy

Apple

1 view

Topics:

ArraysBinary Search

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k, return the k-th 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

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

Kth Missing Positive Number

Easy

Apple

1 view

Topics:

ArraysBinary Search

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k, return the k-th 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

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `arr` and the maximum value of `k`?
Can the input array `arr` contain duplicate values?
Is the input array guaranteed to be strictly sorted in ascending order, or could it be non-decreasing?
If `k` is larger than the number of missing positive integers within the range of values present in `arr`, what should I return?
Is `k` guaranteed to be a positive integer?

Brute Force Solution

Approach

The brute force way to find the missing positive number involves checking each positive integer one by one. We start with 1, then 2, then 3, and so on, and see if it is present in the provided set of numbers. We keep going until we've found the 'k'th missing number.

Here's how the algorithm would work step-by-step:

Begin with the number 1.
Check if 1 is present in the given set of numbers.
If 1 is present, move on to the number 2.
If 1 is not present, mark it as a missing number and remember we've found one missing number.
Repeat this process for 2, 3, 4, and so on, checking if each number is in the given set.
Each time you find a number is missing, increment the count of missing numbers we have found.
Keep going until you've found 'k' missing numbers.
The last missing number you found is the answer.

Code Implementation

def find_kth_missing_positive(numbers, k):
    missing_numbers_found = 0
    current_integer = 1

    while missing_numbers_found < k:
        # Check if the current integer is in the array
        if current_integer not in numbers:
            # If it's not present, increment the missing numbers found
            missing_numbers_found += 1

            # This is the Kth missing number
            if missing_numbers_found == k:
                return current_integer

        current_integer += 1

    return current_integer - 1 # Return the kth missing positive number

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates, checking positive integers starting from 1. For each integer, it needs to determine if it is present in the input array. In the worst case, checking if each integer is present in the array could take O(n) time, where n is the size of the input array. We repeat this process until we find 'k' missing positive numbers. Therefore, the overall time complexity is O(n*k).

Space Complexity

O(1) – The provided solution iteratively checks positive integers starting from 1. It does not create any auxiliary data structures like arrays, hash maps, or sets to store information about the input array or the missing numbers. The only extra memory used is for a few integer variables like the current number being checked and the count of missing numbers found. Therefore, the space complexity is constant and does not depend on the input array size.

Optimal Solution

Approach

The goal is to find the k-th positive number missing from a given list. We avoid checking every single number by cleverly using binary search to quickly narrow down the possibilities to find where the missing numbers are located and jump right to the answer.

Here's how the algorithm would work step-by-step:

Recognize that the missing positive numbers will increase as you go through the list.
Use a binary search-like approach to find a spot in the list where the number of missing positive numbers is just below what we're looking for.
Once you've found that spot, you know you are very close to the answer.
Figure out how many missing numbers are before that spot and determine how much further you need to go to find the k-th missing number.
Add that difference to the number right before that spot to get the final answer.

Code Implementation

def findKthPositive(array_of_integers, k_value):
    left_index = 0
    right_index = len(array_of_integers)

    while left_index < right_index:
        pivot_index = left_index + (right_index - left_index) // 2
        # Count missing numbers up to the current index.
        missing_numbers = array_of_integers[pivot_index] - (pivot_index + 1)

        if missing_numbers < k_value:
            left_index = pivot_index + 1
        else:
            right_index = pivot_index

    # We need to calculate the kth missing number.
    # The kth missing number is k plus the number just before left_index.
    if left_index == 0:
        return k_value
    else:
        return array_of_integers[left_index - 1] + (k_value - (array_of_integers[left_index - 1] - left_index))

Big(O) Analysis

Time Complexity

O(log n) – The dominant operation in this algorithm is the binary search performed on the input array of size n. Binary search repeatedly divides the search interval in half. Therefore, the number of iterations required to find the desired spot grows logarithmically with the size of the input array. The operations outside the binary search, such as calculating the number of missing elements and adding the difference to find the k-th missing number, take constant time. Hence, the overall time complexity is determined by the binary search, which is O(log n).

Space Complexity

O(1) – The described algorithm uses a binary search-like approach, primarily involving comparisons and adjustments of indices within the input array. It doesn't create any auxiliary data structures like temporary lists, hash maps, or recursion stack frames. The only extra space is for a few integer variables to track the indices and missing number count, which remains constant regardless of the input array's size, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	If the input array is empty, the first k positive integers are missing, so return k.
k is smaller than the first missing positive integer	If k is smaller than arr[0], then k is the kth missing positive integer, so return k.
k is larger than the number of missing positive integers before the end of the array	Calculate the number of missing integers and determine the kth missing positive number by adding the difference to the last element.
Array contains very large positive integers	The algorithm should be able to handle large integers within the language's integer limits; check for integer overflow if necessary.
k is very large	The algorithm's performance might degrade with large k, consider using binary search or other optimization techniques to improve efficiency.
All numbers from 1 to n are present in the array	If all numbers from 1 to n (where n is the length of the array) are present, then the kth missing positive number is n + k.
Array contains duplicate numbers	Duplicates do not affect the count of missing positive integers, the algorithm still finds the kth missing positive integer correctly.
Large input array size	Binary search approach provides logarithmic time complexity, addressing scaling issues with large input arrays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `arr` and the maximum value of `k`?
Can the input array `arr` contain duplicate values?
Is the input array guaranteed to be strictly sorted in ascending order, or could it be non-decreasing?
If `k` is larger than the number of missing positive integers within the range of values present in `arr`, what should I return?
Is `k` guaranteed to be a positive integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with the number 1.
Check if 1 is present in the given set of numbers.
If 1 is present, move on to the number 2.
If 1 is not present, mark it as a missing number and remember we've found one missing number.
Repeat this process for 2, 3, 4, and so on, checking if each number is in the given set.
Each time you find a number is missing, increment the count of missing numbers we have found.
Keep going until you've found 'k' missing numbers.
The last missing number you found is the answer.

Code Implementation

def find_kth_missing_positive(numbers, k):
    missing_numbers_found = 0
    current_integer = 1

    while missing_numbers_found < k:
        # Check if the current integer is in the array
        if current_integer not in numbers:
            # If it's not present, increment the missing numbers found
            missing_numbers_found += 1

            # This is the Kth missing number
            if missing_numbers_found == k:
                return current_integer

        current_integer += 1

    return current_integer - 1 # Return the kth missing positive number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that the missing positive numbers will increase as you go through the list.
Use a binary search-like approach to find a spot in the list where the number of missing positive numbers is just below what we're looking for.
Once you've found that spot, you know you are very close to the answer.
Figure out how many missing numbers are before that spot and determine how much further you need to go to find the k-th missing number.
Add that difference to the number right before that spot to get the final answer.

Code Implementation

def findKthPositive(array_of_integers, k_value):
    left_index = 0
    right_index = len(array_of_integers)

    while left_index < right_index:
        pivot_index = left_index + (right_index - left_index) // 2
        # Count missing numbers up to the current index.
        missing_numbers = array_of_integers[pivot_index] - (pivot_index + 1)

        if missing_numbers < k_value:
            left_index = pivot_index + 1
        else:
            right_index = pivot_index

    # We need to calculate the kth missing number.
    # The kth missing number is k plus the number just before left_index.
    if left_index == 0:
        return k_value
    else:
        return array_of_integers[left_index - 1] + (k_value - (array_of_integers[left_index - 1] - left_index))

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	If the input array is empty, the first k positive integers are missing, so return k.
k is smaller than the first missing positive integer	If k is smaller than arr[0], then k is the kth missing positive integer, so return k.
k is larger than the number of missing positive integers before the end of the array	Calculate the number of missing integers and determine the kth missing positive number by adding the difference to the last element.
Array contains very large positive integers	The algorithm should be able to handle large integers within the language's integer limits; check for integer overflow if necessary.
k is very large	The algorithm's performance might degrade with large k, consider using binary search or other optimization techniques to improve efficiency.
All numbers from 1 to n are present in the array	If all numbers from 1 to n (where n is the length of the array) are present, then the kth missing positive number is n + k.
Array contains duplicate numbers	Duplicates do not affect the count of missing positive integers, the algorithm still finds the kth missing positive integer correctly.
Large input array size	Binary search approach provides logarithmic time complexity, addressing scaling issues with large input arrays.