#344

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse String

Reverse a character array in-place using a two-pointer scanning technique, ensuring minimal memory and correct index swaps.

two pointers string

Problem Statement

Write a function that takes an array of characters and reverses it in-place. The input must be modified directly without allocating additional arrays.

For example, given s = ["h","e","l","l","o"], after reversing the array should become ["o","l","l","e","h"]. Ensure your solution maintains O(1) extra memory and works efficiently for arrays up to length 105.

Examples

Example 1

Input: s = ["h","e","l","l","o"]

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

Example details omitted.

Example 2

Input: s = ["H","a","n","n","a","h"]

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

Example details omitted.

Constraints

1 <= s.length <= 105
s[i] is a printable ascii character.

Solution Approach

Two-Pointer Initialization

Start with two pointers, one at the beginning and one at the end of the array. This sets up the invariant that elements outside the pointers are already in correct reversed positions.

In-Place Swapping

Swap the elements at the two pointers, then move the start pointer forward and the end pointer backward. Repeat until pointers meet or cross, ensuring the array is reversed in-place without extra memory.

Handling Edge Cases

Check for empty arrays or single-element arrays before starting. These cases require no swaps, but the invariant still holds, avoiding unnecessary pointer movement or errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is visited once in a single pass. Space complexity is O(1) since all swaps are in-place and no additional arrays are created.

What Interviewers Usually Probe

Looks for correct two-pointer initialization and proper index tracking.
Checks that swaps are performed in-place without auxiliary storage.
Tests edge cases like empty arrays or arrays with one character.

Common Pitfalls or Variants

Common pitfalls

Forgetting to move both pointers after a swap, causing infinite loops.
Using extra arrays instead of in-place modification.
Mismanaging indices, leading to off-by-one errors or partial reversal.

Follow-up variants

Reverse a linked list using two-pointer or recursive swapping.
Reverse only a substring or a section of the array in-place.
Reverse words in a sentence while maintaining character order within words.

FAQ

What is the best pattern to reverse a string in-place?

Using two-pointer scanning with invariant tracking is optimal for reversing a string array in-place with minimal memory.

Can I use extra memory to simplify reversing a string?

No, the problem explicitly requires O(1) extra memory, so all swaps must be performed in-place.

How do I handle a string array of length 1 or 0?

These arrays are already reversed by definition, so no swaps are needed but pointer logic should still handle them safely.

What is the time complexity of this two-pointer approach?

The approach runs in O(n) time since each character is visited exactly once during swaps.

Why is two-pointer scanning preferred for the Reverse String problem?

It guarantees in-place reversal with O(1) extra memory and avoids common pitfalls like off-by-one errors or unnecessary array copying.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$, initially pointing to the start and end of the array respectively. Each time, we swap the elements at $i$ and $j$, then move $i$ forward and $j$ backward, until $i$ and $j$ meet.

1

2

3

4

5

6

class Solution:
    def reverseString(self, s: List[str]) -> None:
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i, j = i + 1, j - 1

Continue Practicing

#345 reverse vowels of a string #392 is subsequence #443 string compression