Prepping for DSAs: Make Array Consecutive

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 be O(n log n). The next iteration starting on line 2 would take O(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 is O(n log n) since we only care about the dominant term from O( 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 of O(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 numbers x,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 the minus 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 still O(n log n).

To illustrate:

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