Reverse String - Leetcode Solution

Problem Link

Step-by-Step Thought Process

Brute Force

Understand the problem: Reverse a character array s in-place.
Get the length n of the array s.
Create an auxiliary array T to store the reversed characters.
Iterate from i = n-1 down to 0, appending each s[i] to T.
Copy the elements of T back to s by iterating from i = 0 to n-1 and setting s[i] = T[i].

Code Solution (Brute Force)

# Brute Force Solution
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        T = []
        for i in range(n-1, -1, -1):
            T.append(s[i])
        
        for i in range(n):
            s[i] = T[i]
        
        # Time: O(n)
        # Space: O(n)

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        vector<char> T;
        for (int i = n - 1; i >= 0; --i) {
            T.push_back(s[i]);
        }
        for (int i = 0; i < n; ++i) {
            s[i] = T[i];
        }
    }
};
// Time: O(n)
// Space: O(n)

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        char[] T = new char[n];
        for (int i = n - 1; i >= 0; i--) {
            T[n - 1 - i] = s[i];
        }
        for (int i = 0; i < n; i++) {
            s[i] = T[i];
        }
    }
}
// Time: O(n)
// Space: O(n)

var reverseString = function(s) {
    const n = s.length;
    const T = [];
    for (let i = n - 1; i >= 0; i--) {
        T.push(s[i]);
    }
    for (let i = 0; i < n; i++) {
        s[i] = T[i];
    }
};
// Time: O(n)
// Space: O(n)

Why the Brute-Force Solution is Inefficient

The brute-force solution uses extra space to store the reversed array, leading to:

Time Complexity: O(n), where n is the length of the array, as it requires two passes (one to build T and one to copy back to s).
Space Complexity: O(n), due to the auxiliary array T storing a copy of the input array.
Performance Issue: The additional space usage is unnecessary since the problem requires an in-place solution, making this approach less efficient in terms of space.

Optimal Solution

The optimal solution uses two pointers to reverse the array in-place with O(1) space complexity:

Get the length n of the array s.
Initialize two pointers: l at index 0 and r at index n-1.
While l is less than r:
- Swap the characters at s[l] and s[r].
- Increment l and decrement r to move the pointers inward.

Code Solution (Optimal)

# Two Pointers (Optimal) Solution
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        l = 0
        r = n - 1

        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

# Time Complexity: O(n)
# Space Complexity: O(1)

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0;
        int r = s.size() - 1;

        while (l < r) {
            swap(s[l], s[r]);
            l++;
            r--;
        }
    }
};

public class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;

        while (l < r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

function reverseString(s) {
    let l = 0;
    let r = s.length - 1;

    while (l < r) {
        [s[l], s[r]] = [s[r], s[l]];
        l++;
        r--;
    }
}

Detailed Explanation

Understanding the Problem: Reverse String

The “Reverse String” problem asks you to reverse a character array s in-place. That means you must reverse the order of characters without using additional memory for another array.

For example:

Input: ["h", "e", "l", "l", "o"]
Output: ["o", "l", "l", "e", "h"]

Why This Problem Matters

Reversing a string in-place is a fundamental operation in computer science. It’s often used in more complex problems like string manipulation, palindrome checking, and memory-efficient algorithms. Mastering this builds confidence in using pointers and understanding array indexing.

Brute-Force Approach: Use an Auxiliary Array

A naive approach is to use a temporary array to store the reversed characters and then copy them back into the original array.

Steps:

Create a new array T to store the characters in reverse order.
Loop from the end of s to the beginning, appending each character to T.
Copy the contents of T back to s to complete the reversal.

While this works, it violates the in-place constraint by using extra memory and involves two separate passes through the array.

Optimal Solution: Two-Pointer Swap

The optimal way to reverse a string in-place is by using the two-pointer technique. This method swaps characters from both ends of the array while moving inward, and it requires only constant extra space.

Steps:

Initialize two pointers:
- l = 0 (left side)
- r = s.length - 1 (right side)
While l < r:
- Swap s[l] and s[r].
- Increment l and decrement r.
Return the modified array s.

Example Walkthrough

Input: ["h", "e", "l", "l", "o"]
Iteration steps:

Swap 'h' and 'o' → ["o", "e", "l", "l", "h"]
Swap 'e' and 'l' → ["o", "l", "l", "e", "h"]
Middle element reached → done

Final output: ["o", "l", "l", "e", "h"]

Time and Space Complexity

Time Complexity: O(n), where n is the number of characters. Each character is visited once.
Space Complexity: O(1), since the reversal is done in-place without using any additional data structures.

Edge Cases to Consider

Empty array → no action needed
Single character → already reversed
Even and odd length arrays → both handled naturally by the pointer logic

Conclusion

The “Reverse String” problem is a textbook example of applying the two-pointer technique to modify arrays efficiently. It’s simple, elegant, and a fundamental operation in both interview questions and real-world systems. Learning how to perform in-place reversal builds a solid foundation for more advanced string and array problems.

Get Personalized Support at AlgoMap Bootcamp 💡