Home/

...

/

Problem Challenge 3

Problem Challenge 3

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Problem Challenge 3 lesson:

Press + to interact
Python 3.5
def find_first_k_missing_positive(nums, k):
  n = len(nums)
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1
  missingNumbers = []
  extraNumbers = set()
  for i in range(n):
    if len(missingNumbers) < k:
      if nums[i] != i + 1:
        missingNumbers.append(i + 1)
        extraNumbers.add(nums[i])
  # add the remaining missing numbers
  i = 1
  while len(missingNumbers) < k:
    candidateNumber = i + n
    # ignore if the array contains the candidate number
    if candidateNumber not in extraNumbers:
      missingNumbers.append(candidateNumber)
    i += 1
  return missingNumbers
def main():
  print(find_first_k_missing_positive([3, -1, 4, 5, 5], 3))
  print(find_first_k_missing_positive([2, 3, 4], 3))
  print(find_first_k_missing_positive([-2, -3, 4], 2))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

nums: [3, -1, 4, 5, 2]
k: 4

Iteration No.

Line No.

nums

i+1

missingNumbers

extraNumbers

candidateNumber

-

12

[-1, 2, 3, 4, 5]

-

-

-

-

1

16-18

[-1,2,3,4,5]

1

[1]

{-1}

-

2

16-18

[-1,2,3,4,5]

2

[1]

{-1}

-

3

16-18

[-1,2,3,4,5]

3

[1]

{-1}

-

4

16-18

[-1,2,3,4,5]

4

[1]

{-1}

-

5

16-18

[-1,2,3,4,5]

5

[1]

{-1}

-

1

23

[-1,2,3,4,5]

-

[1]

{-1}

6

1

25-26

[-1,2,3,4,5]

-

[1,6]

{-1}

6

2

23

[-1,2,3,4,5]

-

[1,6]

{-1}

7

2

25-26

[-1,2,3,4,5]

-

[1,6,7]

{-1}

7

3

23

[-1,2,3,4,5]

-

[1,6,7]

{-1}

8

4

25-26

[-1,2,3,4,5]

-

[1,6,7,8]

{-1}

8

Sample Input #2

Encourage the students to complete the table below for the following input:

nums: [-1,-2,-3]
k:4

Iteration No.

Line No.

nums

i+1

missingNumbers

extraNumbers

candidateNumber

-

12

[-1, -2, -3]

-

-

-

-

1

16-18

[-1, -2, -3]

1

[1]

{-1}

-

2

16-18

[-1,-2,-3]

2

[1,2]

{-1,-2}

-

3

16-18

[-1,-2,-3]

3

[1,2,3]

{-3,-1,-2}

-

1

23

[-1,-2,-3]

-

[1,2,3]

{-3,-1,-2}

4

1

25-26

[-1,-2,-3]

-

[1,2,3,4]

{-3,-1,-2}

4

...

...

...

...

...

...

...

Step-by-step solution construction

Step1: Let’s first perform cyclic sort on the nums array as done before in Introduction and Find all Duplicate Numbers (easy) lessons (lines 5-23). The only difference is that we are ignoring negative numbers from the sort (line 14).

Press + to interact
Python 3.5
def find_first_k_missing_positive(nums, k):
  n = len(nums)
  i = 0
  print("\tPerforming cyclic sort on",nums,sep=" ")
  while i < len(nums):
    j = nums[i] - 1
    print("\ti:",i, end="")
    print("\t\tnums[", i, "]: ", nums[i], sep="")
    print("\tj:",j, end="")
    if(nums[i] > 0 and j < len(nums)): 
      print("\t\tnums[", j, "]: ", nums[j], sep="")
    else:
      print("\t\tnums[", j, "]: ", "out of bound", sep="")
    if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
      print("\tElement not in its place. --> Swapping " + str(nums[i]) + " and " + str(nums[j]))
      nums[i], nums[j] = nums[j], nums[i]  # swap
      print("\tnums after swap: " + str(nums))
    else:
      if(nums[i] > 0 and nums[i] <= n):
        print("\tSame values, no need to swap.")
      else:
        print("\tSkipping negative number")
      i += 1
  print("\tnums after the cyclic sort",nums,sep=":")
  missingNumbers = []
  return missingNumbers
def main():
  
  nums_arr = [[3, -1, 4, 5, 2],[2, 3, -1],[-2, -3, 1], [6, 2, 3, -1]]
  k_arr = [4,3,3,6]
  for i in range(len(nums_arr)):
    print("Finding",k_arr[i],"missing numbers in ",nums_arr[i],sep=" ")
    result = find_first_k_missing_positive(nums_arr[i], k_arr[i])
    print("Result: ",k_arr[i],"missing numbers in",nums_arr[i],"are",result,sep=" ")
    print(("-"*100)+"\n")
main()

Step 2: Once the nums is sorted cyclically, the following property will be true for each of its index i

nums[i] = i+1, otherwise, i+1 is a missing number.

Now, scan nums from left to right and add i+1 to the missingNumbers whenever nums[i] != i+1 (line 28-33).

Press + to interact
Python 3.5
def find_first_k_missing_positive(nums, k):
  n = len(nums)
  i = 0
  print("\tPerforming cyclic sort on",nums,sep=" ")
  while i < len(nums):
    j = nums[i] - 1
    print("\ti:",i, end="")
    print("\t\tnums[", i, "]: ", nums[i], sep="")
    print("\tj:",j, end="")
    if(nums[i] > 0 and j < len(nums)): 
      print("\t\tnums[", j, "]: ", nums[j], sep="")
    else:
      print("\t\tnums[", j, "]: ", "out of bound", sep="")
    if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
      print("\tElement not in its place. --> Swapping " + str(nums[i]) + " and " + str(nums[j]))
      nums[i], nums[j] = nums[j], nums[i]  # swap
      print("\tnums after swap: " + str(nums))
    else:
      if(nums[i] > 0 and nums[i] <= n):
        print("\tSame values, no need to swap.")
      else:
        print("\tSkipping negative number")
      i += 1
  print("\tnums after the cyclic sort",nums,sep=":")
  missingNumbers = []
  extraNumbers = set()
  for i in range(n):
    print("\tComparing",nums[i],"to i+1:",i+1," ")
    if len(missingNumbers) < k:
      if nums[i] != i + 1:
        print("\t\tAdding",i+1,"to","missingNumbers")
        missingNumbers.append(i + 1)
  print("\tmissingNumbers: ",missingNumbers,sep=" ")
  
  return missingNumbers
def main():
  
  nums_arr = [[3, -1, 4, 5, 2],[2, 3, -1],[-2, -3, 1], [6, 2, 3, -1]]
  k_arr = [4,3,3,6]
  for i in range(len(nums_arr)):
    print("Finding",k_arr[i],"missing numbers in ",nums_arr[i],sep=" ")
    result = find_first_k_missing_positive(nums_arr[i], k_arr[i])
    print("Result: ",k_arr[i],"missing numbers in",nums_arr[i],"are",result,sep=" ")
    print(("-"*100)+"\n")
main()

Depending on the values in nums, the above code might give us missing numbers fewer than k missing numbers. The code below finds the remaining k - len(missingNumbers) missing numbers.

To keep track of numbers which exist in nums, yet they are not added to missingNumbers at Step 2, we introduce extraNumbers (line 34). To find the remaining k - len(missingNumbers) missing numbers, we start from n+1 and keep adding numbers to missingNumbers if n+1 does not exist in extraNumbers (line 42-54).

Press + to interact
Python 3.5
def find_first_k_missing_positive(nums, k):
  n = len(nums)
  i = 0
  print("\tStep 1: performing cyclic sort on",nums,sep=" ")
  while i < len(nums):
    j = nums[i] - 1
    print("\ti:",i, end="")
    print("\t\tnums[", i, "]: ", nums[i], sep="")
    print("\tj:",j, end="")
    if(nums[i] > 0 and j < len(nums)): 
      print("\t\tnums[", j, "]: ", nums[j], sep="")
    else:
      print("\t\tnums[", j, "]: ", "out of bound", sep="")
    if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
      print("\tElement not in its place. --> Swapping " + str(nums[i]) + " and " + str(nums[j]))
      nums[i], nums[j] = nums[j], nums[i]  # swap
      print("\tnums after swap: " + str(nums))
    else:
      if(nums[i] > 0 and nums[i] <= n):
        print("\tSame values, no need to swap.")
      else:
        print("\tSkipping negative number")
      i += 1
  print("\tnums after the cyclic sort",nums,sep=":")
  print("\tStep 2: Finding missing number from the sorted nums")
  missingNumbers = []
  extraNumbers = set()
  for i in range(n):
    print("\tComparing",nums[i],"to i+1:",i+1," ")
    if len(missingNumbers) < k:
      if nums[i] != i + 1:
        print("\t\tAdding",i+1,"to","missingNumbers")
        missingNumbers.append(i + 1)
        extraNumbers.add(nums[i])
        print("\t\tUpdated missingNumbers: ",missingNumbers)
        print("\t\tUpdated extraNumbers: ",extraNumbers)
        
  print("\tmissingNumbers: ",missingNumbers,sep=" ")
  # add the remaining missing numbers
  i = 1
  while len(missingNumbers) < k:
    if(i == 1):
      print("\tStep 3: Found",len(missingNumbers),"missing numbers in nums. Adding remaining",k-len(missingNumbers),"missing number(s) to the missingNumbers array",sep=" ")
    candidateNumber = i + n
    print("\tNext candidateNumber: ",candidateNumber)
    # ignore if the array contains the candidate number
    if candidateNumber not in extraNumbers:
      print("\t\tAdding",candidateNumber,"to",missingNumbers,sep=" ")
      missingNumbers.append(candidateNumber)
      print("\t\tupdated missingNumbers",missingNumbers,sep=":")
    else:
      print("\t\tSkipping",candidateNumber,"as it is already in the nums(",nums,")array.",sep=" ")
    i += 1
  return missingNumbers
def main():
  
  nums_arr = [[3, -1, 4, 5, 2],[2, 3, -1],[-2, -3, 1], [6, 2, 3, -1]]
  k_arr = [4,3,3,6]
  for i in range(len(nums_arr)):
    print("Finding",k_arr[i],"missing numbers in ",nums_arr[i],sep=" ")
    result = find_first_k_missing_positive(nums_arr[i], k_arr[i])
    print("Result: ",k_arr[i],"missing numbers in",nums_arr[i],"are",result,sep=" ")
    print(("-"*100)+"\n")
main()