PROBLEM

BRUTE FORCE

While I was thinking of a brute force algorithm, one idea that came into my mind was:

Having that algorithm in mind, I wanted to check the efficiency of my algorithm. I can implement my own Quicksort algorithm, however for this problem, I intend to practice the DRY principle. Sorting an array in Java (line 1) is guaranteed to beO(n log n). The next iteration starting on line 2 would takeO(n) since we are iterating each element in the array. I believe the other lines are constant. As a whole, the running time of our brute force algorithm isO(n log n) since we only care about the dominant term fromO( n + n log n).

The question now is, "Is this enough?" At this rate, there is no other way that I know of that can lessen the running time. The "best" sorting algorithm suitable for this problem is ofO(n log n).

I can make it more concise.

Final Solution

How did I arrive here?

Motivation: We can count the length of the range between two numbersx,y where x is the minimum and y is the maximum. With out array sorted out in increasing order:

statues[statues.length - 1] is the maximum element which happens to be the last element of the array since it is sorted in increasing order. Since arrays are zero-indexed, hence comes theminus 1 from the total length.statues[0] is the minimum element. The difference of max and min is the length of the range between those numbers.

We added 1 to the difference of max and min since, again, arrays are zero-indexed.((statues[statues.length - 1] - statues[0]) + 1) indicates the supposed length of the range given the min and max.

The- statues.length at the end of the formula is how we get the missing numbers in our range to satisfy the requirement of getting the missing numbers of elements in our array which the element should be exactly 1 greater that its previous(keep in mind that this is sorted in increasing order).

The running time of this algorithm is stillO(n log n).

To illustrate:

PS: I would appreciate comments in improving the algorithm that I have.