Reverse String

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reverse String is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers swapping inward), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy backwards) up.

Problem

You are given a word as an array of characters s. Reverse the order of the characters in place: change s itself instead of returning a new array.

Use only O(1) extra memory. Nothing needs to be returned.

Examples

Example 1

Input
s = ["c", "o", "d", "e", "r"]
Output
["r", "e", "d", "o", "c"]
Why
The first and last letters swap, then the second and fourth; the middle letter stays.

Example 2

Input
s = ["Z", "z", "9", "!"]
Output
["!", "9", "z", "Z"]
Why
Any printable character can appear; with an even length every character moves.

Constraints

  • 1 <= s.length <= 10^5
  • Each s[i] is a printable ASCII character.
  • Modify s in place using O(1) extra memory.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (copy backwards)O(n)O(n)
Optimal (two pointers swapping inward)O(n)O(1)

1Brute force (copy backwards)

TimeO(n)Two passes over the n characters.
SpaceO(n)The temporary copy holds all n characters.

Build a reversed copy in a second array, then write it back into s. Simple, but it uses O(n) extra memory, which the problem forbids.

  1. Create an array copy of the same length.
  2. For every i, set copy[i] = s[n - 1 - i].
  3. Copy every character of copy back into s.
class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        char[] copy = new char[n];
        for (int i = 0; i < n; i++) {
            copy[i] = s[n - 1 - i];
        }
        for (int i = 0; i < n; i++) {
            s[i] = copy[i];
        }
    }
}

2Optimal (two pointers swapping inward)

TimeO(n)Each character is touched by exactly one swap: n / 2 swaps in total.
SpaceO(1)Only two indices and one temporary character.

Put one pointer at each end. Swap the two characters, then move the pointers toward each other. When they meet or cross, every character has reached its mirrored position.

  1. Set left = 0 and right = n - 1.
  2. While left < right: swap s[left] and s[right].
  3. Increase left and decrease right.
class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

Edge cases to test

  • A single character (nothing changes)
  • Two characters (one swap)
  • Odd length, where the middle character stays put
  • A palindrome like ["a", "b", "a"] (the result equals the input)

Hints

Hint 1

Which character ends up at index 0, and which one at index n - 1?

Hint 2

Swap the two ends, then move both ends one step inward. When do you stop?

FAQ

What is the best time complexity for Reverse String?

Optimal (two pointers swapping inward) runs in O(n) time and O(1) extra space. Each character is touched by exactly one swap: n / 2 swaps in total.

Which pattern does Reverse String use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Reverse String?

Yes. Brute force (copy backwards) takes O(n) time and O(n) space. Build a reversed copy in a second array, then write it back into s.

Which edge cases should I test for Reverse String?

A single character (nothing changes); Two characters (one swap); Odd length, where the middle character stays put; A palindrome like ["a", "b", "a"] (the result equals the input).