Home /
Expert Answers /
Computer Science /
you-are-given-an-unsorted-array-of-n-integers-where-each-integer-is-between-1-and-n-inclusive-th-pa218

You are given an unsorted array of n integers, where each integer is between 1 and n (inclusive). The array contains some duplicates, but not all integers are necessarily present. Design an algorithm to find all the missing integers in the array, with a worst-case runtime of O(n)

Implement and test your function in python using lists, $[1,3,7,3,6,5,8,3], [1,5,5,1,15,12,12,12,12,1,4,6,13,12,4,10,2]$

We can solve the problem by using the array itself as a hash table. For each element in the array, mark the corresponding index (i.e., the element min