Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 3: Find the First K Missing Positive Numbers

Problem Statement

Given an unsorted array containing numbers and a number ‘k’, find the first ‘k’ missing positive numbers in the array.

Example 1:

Input: [3, -1, 4, 5, 5], k=3
Output: [1, 2, 6]
Explanation: The smallest missing positive numbers are 1, 2 and 6.

Example 2:

Input: [2, 3, 4], k=3
Output: [1, 5, 6]
Explanation: The smallest missing positive numbers are 1, 5 and 6.

Example 3:

Input: [-2, -3, 4], k=2
Output: [1, 2]
Explanation: The smallest missing positive numbers are 1 and 2.

Constraints:

  • 1 <= nums.length <= 1000

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Russell Rogers

· 4 years ago

I think the space complexity is O(n) not O(k) because at most you would store n extra numbers in the situation where everything inside the array is either n.

Show 2 replies
S

SeungJin Kim

· 4 years ago

Is there a leetcode question equivalent of this?

D

Duc

· 4 years ago

The first for-loop where you first iterate through the elements in the array to insert to missingNumbers and extraNumbers lacks a condition I think. First, a Set does not tolerate duplicate, you can totally add a nums[i] if nums[i] != i + 1, that's true and I agree. However, what if 'i + 1' is equivalent to an element in the Set? For example, consider nums = [5, 6, 7, 8, 9] and k = 9. At i = 4, if I follow the solution's logic, missingNumbers will contain [1, 2, 3, 4, 5]. That 5 is a killer. I managed to fix this by adding a condition to only add i + 1 if extraNumbers has not contained it, and it works so far. Definitely fix me if I'm wrong tho.

S

Shane

· 3 years ago

  1. place all numbers at the correct index
  2. store the wrongly indexed numbers in an object while reducing k
  3. if k is greater than 0 add the remaining numbers to the missing array. to do this, you need to ensure its not in the store object which has all the numbers that already exist in the initial array that were wrongly indexed.
class Solution {
  findNumbers(nums, k) {
    let missingNumbers = [];
    let n = nums.length;
    let store = {}
    for (let i = 0; i < n; i++) {
      if (nums[i] > 0 && nums[i] <= n  && nums[i] !== nums[nums[i] - 1]) {
        [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
      i--
      }
    }
    
    for (let i = 0; i < n; i++) {
      if (nums[i] !== i + 1 && k != 0){
          store[nums[i]] = 1 
          missingNumbe
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findNumbers(self, nums, k):
    missing_numbers = []

    # swapping function
    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]

    # if number not in position and number is not outside the array boundary and number does not point to number that is correctly positioned  
    for i in range(len(nums)):
      while nums[i] > 0 and nums[i] != i + 1 and nums[i] - 1 < len(nums) and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    # find the missing numbers 
    wrong_numbers = set()
    for i in range(len(nums)):
      if nums[i] != i + 1:
        missing_numbers.append(i + 1)
        # add the miss-placed number to the set 
        wrong_numbers.add(nums[i])
        # if we have found all the missing k numbers just return
P

Pete Stenger

· 2 years ago

  • nums[i] < nums[j] for 1 <= i < j <= nums.length

Is not true if the array is unsorted.

Show 2 replies
P

Pete Stenger

· 2 years ago

It takes O(k) time to test if an element exists in an array, not O(1). So the time complexity of this solution is O(n + k^2).

Show 1 reply
E

Eric C

· a year ago

In the Python solution, it uses the extraNumbers set to keep track of additional numbers that are already part of the array. However, instead of the check:

if candidateNumber not in extraNumbers

can't we just check:

if candidateNumber not in nums ?

Show 1 reply