Sorting The Array

When you receive an unsorted array and decide to sort it before applying the two-pointer technique, the overall time complexity is dominated by the sorting step.

Thus, the overall time complexity becomes:
O(n log n) + O(n) = O(n log n)

 

If the array is already sorted, then you only pay the O(n) cost for the two-pointer traversal, without the additional O(n log n) sorting cost.


Revision #2
Created 28 December 2024 22:18:19 by victor
Updated 10 February 2025 00:29:42 by victor