educative.io

Educative

https://www.educative.io/courses/algorithms-coding-interviews-java/R889pO8W1Ez#Solution-#1:-Sorting

In the solution #1 the Arrays.sort() function is being called n - 1 times making the overall time complexity n-squared log n O(n2log(n)). It is enough to sort the array once before the for loop. no need to sort the array for every iteration.


Type your question above this line.

Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/6332832517455872

Thank you @Yerramsetty_Ganesh_D for the question and let me explain how your proposed solution might fail. Consider the array:

int[ ] pipes = {4, 1, 3, 5, 2, 6 }

In this example if we do not sort for every iteration, the result will be incorrect. Let’s see the solution for the above method you proposed. This turns out to be 55, which is incorrect. But according to our solution the optimal result is 51.

@Azeem_Ashraf ,okay but then why is the time complexity O(nlogn)?, if we are sorting every iteration, worst case could be O(n2logn), right?

Hi @Yerramsetty_Ganesh_D !
Yes, you are right time complexity is 0(n^2logn). we have fixed this issue. Thank you for your keen observation and for letting us know about this mistake.

Thanks once again.

1 Like