educative.io

An alternative, slightly simpler solution

Courses
,
#1

Just add k out-of-range numbers to the array! This way, the first k missing positive numbers will for sure be within the range of the array and we won’t need the trick with the extra numbers.

Time and space complexities are the same.

Here’s the code:

def find_first_k_missing_positive(nums, k):
  nums += [-1]*k

  i = 0
  while i < len(nums):
    j = nums[i]-1
    if j >= 0 and j < len(nums) and nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

  missingNumbers = []
  for i in range(len(nums)):
    if i != nums[i]-1:
      missingNumbers.append(i+1)
      if len(missingNumbers) == k:
        break
  return missingNumbers
1 Like
#2

Nice. Exactly the same idea as me.

#3

I did the same thing, Stored any elements in the array that are > Len of array in a Set. And if we we need more missing elements, we just check for numbers from nums.length + 1 that are NOT in the set.

class FirstKMissingPositive {

  public static List<Integer> findNumbers(int[] nums, int k) {
    List<Integer> missingNumbers = new ArrayList<>();
    Set<Integer> greater = new HashSet<Integer>();
    for(int i = 0; i < nums.length; i++) {
      while(nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
        swap(nums, i, nums[i] - 1);
      }
      if(nums[i] > nums.length) {
        greater.add(nums[i]);
      }
    }

    for(int i = 0; i < nums.length && k > 0; i++) {
      if(nums[i] != i + 1) {
        missingNumbers.add(i + 1);
        k--;
      }
    }

    int start = nums.length + 1;
    while(k > 0) {
      if(!greater.contains(start)) {
        missingNumbers.add(start);
        k--;
      }
      start++;
    }

    return missingNumbers;
  }

  private static void swap(int[] nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
  }
}
#4

Did the exact same:

def find_first_k_missing_positive(nums, k):
  missingNumbers = []
  nums += [-1]*k
  i = 0
  while i < len(nums):
    index = nums[i] - 1
    if nums[i] <= len(nums) and nums[i] > 0 and nums[i] != nums[index] :
      nums[i], nums[index] = nums[index], nums[i]
    else:
      i += 1

  for j in range(len(nums)):
    if len(missingNumbers) == k:
      break
    if nums[j] != j + 1:
        missingNumbers.append(j+1)

  return missingNumbers