Make Array Consecutive

Question

Ratiorg got statues of different sizes as a present from CodeMaster for his birthday, each statue having an non-negative integer size. Since he likes to make things perfect, he wants to arrange them from smallest to largest so that each statue will be bigger than the previous one exactly by 1. He may need some additional statues to be able to accomplish that. Help him figure out the minimum number of additional statues needed.

Example

For statues = [6, 2, 3, 8], the output should be makeArrayConsecutive2(statues) = 3.

Ratiorg needs statues of sizes 4, 5 and 7.

Input/Output

[execution time limit] 3 seconds (java)

[input] array.integer statues

An array of distinct non-negative integers.

Guaranteed constraints: 1 ≤ statues.length ≤ 10, 0 ≤ statues[i] ≤ 20.

[output] integer

The minimal number of statues that need to be added to existing statues such that it contains every integer size from an interval [L, R] (for some L, R) and no other sizes.

Code:

int makeArrayConsecutive2(int[] statues) {
 int count =0;
 Arrays.sort(statues);
 for(int i=1;i<statues.length;i++){
 count+=statues[i]-statues[i-1]-1;
 }
 return count;
}

• dariosicily: Welcome back to Code Review, please add the link to the programming challenge in your question.
• Raushan Kumar: It will not visible for an anonymous user

Answer 1

Indentation

You indentation is inconsistent. int count =0; is not indented the same amount as the following line, despite being logically at the same level.

Your indentation amount is not consistent. You should use the same increment for each additional level. Assuming your first indentation was 2 spaces (instead of both 1 & 2), your next indentation should be an additional 2 spaces (total of 4 spaces).

White space

Use spaces to increase the readability of your code.

int count =0; should have a space after the equals sign.

for(int i=1;i<statues.length;i++){ should at least have spaces after each semicolon.

count+=statues[i]-statues[i-1]-1; should have spaces around +=, as well as the outermost subtraction operators.

This is more readable:

int makeArrayConsecutive2(int[] statues) {
 int count = 0;
 Arrays.sort(statues);
 for(int i=1; i<statues.length; i++) {
 count += statues[i] - statues[i-1] - 1;
 }
 return count;
}

Names

count is a very generic variable name. Count of what? Looking at the code, it isn’t clear.

(statues is pretty vague, too. I’d prefer statue_heights. makeArrayConsecutive2 is just awful. However, both those names get a pass, because they were given to you.)

Instead of count, using statues_to_add really helps improve the readers comprehension. alternately, count_of_missing_heights would really increase understandability.

Algorithm

The sort(statues) makes the algorithm \$O(n \log n)\$. With at most 10 statues, the sorting won’t take a lot of time, but it is doing more work than is needed.

There is an \$O(n)\$ algorithm, which only requires finding the largest and smallest statue heights. (削除) Left to student. (削除ここまで)

Since dariosicily has provided the solution, instead of allowing you to discover it, I’ll provide a shorter stream-based solution.

int makeArrayConsecutive2(int[] statues) {
 return Arrays.stream(statues).max().getAsInt()
 - Arrays.stream(statues).min().getAsInt()
 + 1 - statues.length;
}

• Raushan Kumar: thanks, just a question here we are creating stream objects twice, so maybe it will increase space complexity and I am not aware of Stream max time complexity
• AJNeufeld: A stream is a glorified for-loop. It has a time complexity of \$O(n)\$ and a space complexity of \$O(1)\$ ... unless intermediate operations (.sorted(), .distinct(), ...) themselves have non-trivial requirements. You can avoid creating a second stream and gather the min/max values with just one stream using .summaryStatistics(), but you'd be hard pressed to solve the problem in only one statement ;-)
• AJNeufeld: Challenge revoked; it actually wasn't that hard to solve the problem with only one stream in only one statement. return Arrays.stream(statues).boxed().collect(Collectors.collectingAndThen(Collectors.summarizingInt(i -> i), s -> s.getMax() - s.getMin() + 1 - s.getCount())); Definitely not more efficient due to the need for .boxed() integers.

Answer 2

Your algorithm is correct, but the performance can be improved to O(n) avoiding the sorting of the n elements array with O(n log n) cost. The final result is equal to max + 1 - min - n where min and max are respectively the minimum and the maximum element in the array, so your method can be rewritten like below :

private static int makeArrayConsecutive2(int[] statues) {
 int length = statues.length;
 if (length < 2) { return 0; }
 int min = Math.min(statues[0], statues[1]);
 int max = Math.max(statues[0], statues[1]);
 
 for (int i = 2; i < length; ++i) {
 min = Math.min(min, statues[i]);
 max = Math.max(max, statues[i]);
 }
 
 return max + 1 - min - length;
}

For arrays containing one or zero elements the answer is zero because there are no elements in an interval of one or zero numbers; the fact that the array always contains distinct numbers guarantees that Math#max and Math#min always return distinct results.