educative.io

Educative

Solution without using extra set

import java.util.*;

class FirstKMissingPositive {
public static List<Integer> findNumbers(int[] nums, int k) {
    List<Integer> missingNumbers = new ArrayList<>();
    // TODO: Write your code here
    int i = 0, max = 0;
    while (i < nums.length) {
        max = Math.max(max, nums[i]);
        if (nums[i] > 0 && nums.length >= nums[i] && nums[i] != nums[nums[i] - 1]) {
            swap(nums, nums[i] - 1, i);
        } else {
            i++;
        }
    }
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            missingNumbers.add(i + 1);
        }
        if (missingNumbers.size() == k) break;
    }
    int idx = max + 1;
    while (missingNumbers.size() < k) {
        missingNumbers.add(idx++);
    }
    return missingNumbers;
}
  private static void swap(int[] nums, int l, int r) {
    int tmp = nums[l];
    nums[l] = nums[r];
    nums[r] = tmp;
  }
}

I don’t think it’s correct. Given [1, 2, -1] for example, for k = 2 your output would be [3, 3] instead of [3, 4].