algoadvance

Leetcode 1539. Kth Missing Positive Number

Problem Statement

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

Clarifying Questions

  1. What is the maximum length of the array arr?
  2. What are the constraints on the elements of arr? (e.g., if they can have duplicates, etc.)
  3. What is the range of the integer k?

Strategy

  1. Initialization:
    • Start with a counter, missing_count, to keep track of the number of missing integers.
    • Initialize a pointer, index, to traverse the array.
  2. Iteration:
    • Iterate through numbers starting from 1.
    • Check if the current number is present in the array.
    • If it is not present, increase the missing_count.
    • Stop if missing_count equals k.
  3. Return:
    • Return the current number as it represents the kth missing positive integer.

Time Complexity

Code

public class Solution {
    public int findKthPositive(int[] arr, int k) {
        int missing_count = 0;
        int current_number = 1;
        int index = 0;

        while (missing_count < k) {
            // Check if current_number is missing in the array
            if (index < arr.length && arr[index] == current_number) {
                index++;
            } else {
                missing_count++;
            }

            // Check if the current number is the kth missing number
            if (missing_count == k) {
                return current_number;
            }

            current_number++;
        }

        // As a safety return, although theoretically we should never reach here
        return -1;
    }
}

This code takes into account the given array and checks every integer starting from 1 to find the kth missing positive integer efficiently. If the logic proceeds logically, it ensures that k missing elements are calculated and returned.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI