educative.io

Why not just leverage the maximum value in the array?

Courses
,
#1

I thought I could add the missing out-of-array numbers starting from the max value seen in the array. Looks simpler to me, what do you think?

public static List<Integer> findNumbers(int[] nums, int k) {
List<Integer> missingNumbers = new ArrayList<>();

int i = 0;
while (i < nums.length) {
  if (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i]-1]) {
    int temp = nums[nums[i]-1];
    nums[nums[i]-1] = nums[i];
    nums[i] = temp;
  } else {
    i++;
  }
}

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

if (k > 0) {
  for(int q=max+1; q < max+1+k; q++) {
    missingNumbers.add(q);
  }
}

return missingNumbers;
}
#2

Hi, there are multiple ways to solve this problem and your approach is also correct.

1 Like
#3

Hi, I believe your solution would not work when two numbers are larger than the array’s length.

If the input is { 6, 4, 3 }, 4, your solution would show [1, 2, 7, 8] instead of [1, 2, 5, 7]. I believe that is because your max value overwrites the first out-of-length value with the second one.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Solution Review: Problem Challenge 3 - Grokking the Coding Interview: Patterns for Coding Questions