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.
func reverseString(_ s: inout [Character]) {
        
    // Call our recursive helper function
    swapCharacters(
        atLeftPointer: 0,
        andRightPointer: s.count - 1,
        in: &s
    )
}
    
func swapCharacters(atLeftPointer left: Int, 
                    andRightPointer right: Int, 
                    in array: inout [Character]) {

    /**
    Exist condition.
    Once the pointers cross we know
    we have exhausted all options.
    */
    guard left < right else {
        return 
    }

    // Swap in place
    array.swapAt(left, right)

    // Call recursively while moving the pointers along
    swapCharacters(
        atLeftPointer: left + 1, 
        andRightPointer: right - 1, 
        in: &array
    )
}

Using Array.reverse()

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.

func reverseString(_ s: inout [Character]) {
    s.reverse()
}

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.

Using Array.reversed()

The difference between reverse() and reversed() is that the first one is in place while the second one returns a new Array.

func reverseString(_ s: inout [Character]) {
    s = s.reversed()
}

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.