LeetCode 344 - Reverse String

LeetCode Problem 344

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem asks us to reverse a string that is represented as an array of characters. Instead of returning a new reversed string, we must modify the original array directly. This requirement is important because the problem explicitly states that the solution must work in-place and use only O(1) extra memory.

The input is an array s, where each element is a single character. For example:

["h","e","l","l","o"]

represents the string "hello".

After reversing, the array should become:

["o","l","l","e","h"]

The function does not return anything because the input array itself is modified.

The constraints tell us several useful things about the problem:

• The array length can be as large as 10^5, which means the algorithm must be efficient.
• Every element is a printable ASCII character, so we do not need to worry about Unicode encoding issues or multi-byte characters.
• Because the input can be very large, repeatedly creating copies of the array would be inefficient.

The most important requirement is the in-place constraint with O(1) extra memory. This immediately rules out solutions that create another array of size n.

Several edge cases are worth identifying early:

• A single-character array such as ["a"] should remain unchanged.
• Arrays with an even number of characters and arrays with an odd number of characters behave slightly differently around the middle.
• Repeated characters such as ["a","a","a"] should still be handled correctly.
• The algorithm must avoid overwriting values before they are swapped.

Approaches

Brute Force Approach

A straightforward solution is to create a new array that stores the characters in reverse order. We could iterate through the original array from the end to the beginning and append each character into a new array.

For example:

Original: ["h","e","l","l","o"]
New:      ["o","l","l","e","h"]

After constructing the reversed array, we could copy the values back into the original array.

This approach is correct because every character from position i is moved to position n - 1 - i, which is exactly the definition of reversing a string.

However, this solution uses an additional array of size n, which violates the problem requirement of O(1) extra memory. Although the time complexity is still linear, the extra space makes it suboptimal.

Optimal Approach

The key observation is that reversing a string only requires swapping pairs of characters.

The first character should swap with the last character, the second with the second-last, and so on. This naturally suggests using two pointers:

• One pointer starts at the beginning of the array.
• Another pointer starts at the end of the array.

At each step:

• Swap the characters at the two pointers.
• Move the left pointer one step right.
• Move the right pointer one step left.

The process continues until the pointers meet or cross.

Because swaps happen directly inside the original array, no extra array is needed. This satisfies the in-place requirement and uses only constant extra memory.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Creates a separate reversed copy
Optimal	O(n)	O(1)	Uses two pointers and swaps in-place

Algorithm Walkthrough

1. Initialize two pointers.

Set left to the beginning of the array at index 0. Set right to the last index, which is len(s) - 1.

These pointers represent the pair of characters that should be swapped next. 2. Compare the pointer positions.

Continue processing while left < right.

Once the pointers meet or cross, every necessary swap has already been completed. 3. Swap the characters.

Exchange the values at s[left] and s[right].

This places the correct character at both ends of the array simultaneously. 4. Move both pointers inward.

Increment left by 1 and decrement right by 1.

This moves the pointers toward the center so the next pair can be swapped. 5. Repeat until finished.

Continue swapping and moving inward until all pairs are processed.

Why it works

The algorithm maintains the invariant that all characters outside the current pointer range are already in their correct reversed positions.

At every iteration:

• The character at the left side is moved to its correct mirrored position on the right.
• The character at the right side is moved to its correct mirrored position on the left.

Since every position is processed exactly once, and swaps are performed symmetrically, the entire array becomes reversed when the pointers meet.

Python Solution

from typing import List

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        
        left = 0
        right = len(s) - 1

        while left < right:
            s[left], s[right] = s[right], s[left]

            left += 1
            right -= 1

The implementation begins by creating two pointers, left and right, which point to the beginning and end of the array.

The while loop continues as long as the pointers have not crossed. Inside the loop, Python tuple unpacking is used to swap the two characters in a single statement:

s[left], s[right] = s[right], s[left]

After the swap, the pointers move inward. This process continues until the entire array has been reversed.

The solution modifies the array directly, which satisfies the in-place requirement. No additional data structures proportional to the input size are created.

Go Solution

func reverseString(s []byte) {
	left := 0
	right := len(s) - 1

	for left < right {
		s[left], s[right] = s[right], s[left]

		left++
		right--
	}
}

The Go implementation follows exactly the same logic as the Python version.

One small language-specific difference is that the input type is []byte instead of []string. In Go, strings are often manipulated as byte slices for efficiency.

Go also supports simultaneous assignment during swaps:

s[left], s[right] = s[right], s[left]

This avoids needing a temporary variable.

No special handling for empty or nil slices is required because the constraints guarantee at least one character in the input.

Worked Examples

Example 1

Input:

["h","e","l","l","o"]

Initial state:

Step	left	right	Array
Start	0	4	["h","e","l","l","o"]

Swap s[0] and s[4]:

Step	left	right	Array
After Swap	1	3	["o","e","l","l","h"]

Swap s[1] and s[3]:

Step	left	right	Array
After Swap	2	2	["o","l","l","e","h"]

Now left == right, so the loop stops.

Final output:

["o","l","l","e","h"]

Example 2

Input:

["H","a","n","n","a","h"]

Initial state:

Step	left	right	Array
Start	0	5	["H","a","n","n","a","h"]

Swap s[0] and s[5]:

Step	left	right	Array
After Swap	1	4	["h","a","n","n","a","H"]

Swap s[1] and s[4]:

Step	left	right	Array
After Swap	2	3	["h","a","n","n","a","H"]

Swap s[2] and s[3]:

Step	left	right	Array
After Swap	3	2	["h","a","n","n","a","H"]

Now left > right, so the loop stops.

Final output:

["h","a","n","n","a","H"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most once
Space	O(1)	Only two pointer variables are used

The algorithm processes the array from both ends toward the center. Each iteration performs a constant amount of work, and the number of iterations is approximately n / 2. Since constants are ignored in Big O notation, the total time complexity is O(n).

The solution uses only two integer variables for the pointers and does not allocate additional memory proportional to the input size, so the space complexity is O(1).

Test Cases

from typing import List

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left = 0
        right = len(s) - 1

        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

solver = Solution()

# Example 1
arr = ["h", "e", "l", "l", "o"]
solver.reverseString(arr)
assert arr == ["o", "l", "l", "e", "h"]  # standard odd-length case

# Example 2
arr = ["H", "a", "n", "n", "a", "h"]
solver.reverseString(arr)
assert arr == ["h", "a", "n", "n", "a", "H"]  # standard even-length case

# Single character
arr = ["a"]
solver.reverseString(arr)
assert arr == ["a"]  # minimum size input

# Two characters
arr = ["a", "b"]
solver.reverseString(arr)
assert arr == ["b", "a"]  # smallest non-trivial reversal

# Repeated characters
arr = ["x", "x", "x"]
solver.reverseString(arr)
assert arr == ["x", "x", "x"]  # identical values

# Palindrome
arr = ["r", "a", "c", "e", "c", "a", "r"]
solver.reverseString(arr)
assert arr == ["r", "a", "c", "e", "c", "a", "r"]  # palindrome remains same

# Even-length string
arr = ["1", "2", "3", "4"]
solver.reverseString(arr)
assert arr == ["4", "3", "2", "1"]  # even number of elements

# Special characters
arr = ["!", "@", "#", "$"]
solver.reverseString(arr)
assert arr == ["$", "#", "@", "!"]  # printable ASCII symbols

Test	Why
["h","e","l","l","o"]	Validates normal odd-length reversal
["H","a","n","n","a","h"]	Validates normal even-length reversal
["a"]	Tests minimum input size
["a","b"]	Tests smallest meaningful swap
["x","x","x"]	Ensures repeated values work correctly
["r","a","c","e","c","a","r"]	Tests palindrome behavior
["1","2","3","4"]	Verifies even-length processing
["!","@","#","$"]	Confirms special ASCII characters are handled

Edge Cases

A single-character array is the smallest valid input. This case is important because the two pointers start at the same position immediately. A buggy implementation might accidentally perform unnecessary operations or move pointers incorrectly. In this implementation, the condition left < right prevents any swaps from happening, so the array remains unchanged as expected.

Arrays with an odd number of characters are another important case. In such inputs, there is a middle character that should stay in the same position after reversal. For example:

["a","b","c","b","a"]

The algorithm handles this naturally because the loop stops when the pointers meet. The middle character is never swapped, which is correct behavior.

Arrays containing repeated characters can sometimes hide indexing mistakes because swapping identical values produces no visible change. For example:

["x","x","x"]

Even though the output appears identical to the input, the algorithm still processes indices correctly and terminates properly.

Even-length arrays are also important because the pointers cross without ever landing on the same index. This tests whether the stopping condition is correct. Using left < right ensures that every required pair is swapped exactly once without undoing previous swaps.