LeetCode's challenge of June 4, 2020 (#344) asks us to reverse a String. This task can be achieved with 1 line of code, yet it's worth exploring the different options. Interviewers will want you to show that you can explain different approaches.
Two Pointer Approach
Interviewers very often ask about two pointer approaches, and it's very likely that you may be asked not to rely on built in functions, which make this solution viable.
The advantage of this approach is that the work is logically cut in half. You have a pointer on the left and a pointer on the right. You then swap the characters and you move the pointers along until they cross and the work is done.
Remember to always have an exit condition when doing work recursively or you might end up with a stack overflow (endless loop).
This solution has a runtime of O(n / 2) and is expressed as O(n).
Remember to always drop constants from Big O notations.
The given Array is declared
inout, which means it's mutable. Swift's Array library has the function
reverse() that reverses the Array in place.
The catch: According to Apple's documentation, this function has a linear runtime. Technically, it has the same runtime, but the (rather unreliable) benchmarks on LeetCode prove that this solution takes longer than the Two Pointer Approach.
The difference between
reversed() is that the first one is in place while the second one returns a new Array.
We're assigning the reversed Array to the mutable Array
s and according to Apple's documentation,
reversed has a constant runtime 🎉.
On LeetCode, this approach beats 100% of all submissions in time and space and is the most optimized solution.