With two pointers, we've cut the number of operations in half. It's much faster now! However, similar to the brute force, the time complexity is still O(n)
.

Why Is This?
Well, if n
is the length of the string, we'll end up making n/2
swaps. But remember, Big O Notation
isn't about the raw number of operations required for an algorithm-- it's about how the number scales with the input.
So despite requiring half the number operations-- a 4
-character string would require 2
swaps with the two-pointer method. But an 8
-character string would require 4
swaps. The input doubled, and so did the number of operations.
If you haven't by now, try to do the problem before moving on.