Interview puzzle: array size-n contains numbers from [i, i + n)

Question

Given an unsorted array of numbers, write a function that returns true if array consists of consecutive numbers.

Examples:

1. If array is {5, 2, 3, 1, 4}, then the function should return true because the array has consecutive numbers from 1 to 5.

2. If array is {83, 78, 80, 81, 79, 82}, then the function should return true because the array has consecutive numbers from 78 to 83.

3. If the array is {34, 23, 52, 12, 3 }, then the function should return false because the elements are not consecutive.

4. If the array is {7, 6, 5, 5, 3, 4}, then the function should return false because 5 and 5 are not consecutive.

I came up with the following algo:

1. find the max and min of the array

2. max-min+1 should be the size of array

3. check for duplicates

4. check for all consecutive numbers in between

How can I achieve the 4th path? (The complexity should be O(n))

Other suggestions are most welcome.

Answer 1

If the input array is A:

1. Find the minimum and maximum values of A, return False if the array is of the wrong size.

2. Create a new array, B, of the same size, initially with all zeroes

3. For each index i, let B[A[i] - min] = 1.

4. Check to see if B still contains any zeroes.

Each step takes O(n) time.