#344 Reverse String

Easysolve on LeetCode ↗

frequently reported atTCS Bloomberg Amazon Microsoft Google Apple

the problem

In plain words

Reverse a character array in place, using O(1) extra memory.

in s = ["h","e","l","l","o"]

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

in s = ["H","a","n","n","a","h"]

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

1 ≤ s.length ≤ 10⁵
Printable ASCII characters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (opposite ends)Recursion on a smaller input

Reversing = swap the two ends, then reverse the middle. The middle is a smaller copy of the same problem — or just a loop with two pointers.

solutions

From brute force to optimal

Fill a new array from the back, then copy it over the original.

copy[i] = s[n − 1 − i].
Copy everything back into s.

timeO(n)

Two linear passes.

spaceO(n)

The extra array — breaks the O(1) memory rule.

java

1class Solution {2    public void reverseString(char[] s) {3        char[] copy = new char[s.length];4        for (int i = 0; i < s.length; i++) copy[i] = s[s.length - 1 - i];5        System.arraycopy(copy, 0, s, 0, s.length);   // extra O(n) array → not "in place"6    }7}

Swap s[left] and s[right], then recurse on left + 1, right − 1.

Base case: left ≥ right (0 or 1 characters left).
Swap the ends.
Recurse on the inner range.

timeO(n)

n / 2 calls, each doing one swap.

spaceO(n)

n / 2 stack frames — still not O(1) memory, even though no array is allocated.

java

1class Solution {2    public void reverseString(char[] s) {3        reverse(s, 0, s.length - 1);4    }5 6    private void reverse(char[] s, int left, int right) {7        if (left >= right) return;            // 0 or 1 chars left: nothing to swap8        char tmp = s[left];9        s[left] = s[right];10        s[right] = tmp;11        reverse(s, left + 1, right - 1);      // the inner part is a smaller copy of the problem12    }13}

The same swaps, but driven by a while loop instead of the call stack.

left = 0, right = n − 1.
While left < right: swap, left++, right--.

timeO(n)

n / 2 swaps.

spaceO(1)

Two indices and one temp char.

java

1class Solution {2    public void reverseString(char[] s) {3        int left = 0, right = s.length - 1;4        while (left < right) {5            char tmp = s[left];6            s[left++] = s[right];7            s[right--] = tmp;8        }9    }10}

in the room

How to say it in the interview

talk track

Show the recursive version if the interviewer is testing recursion, then point out its hidden O(n) stack space.
Convert it to the loop to meet the O(1) memory requirement.

traps

Claiming the recursive version is O(1) space — the call stack counts.
Base case left == right alone misses even lengths; use left >= right.

what they ask next

Follow-ups

Reverse only the vowels (LC 345)?

Same two pointers, but each pointer skips non-vowels before swapping.

before you submit

Edge cases to test

One character: nothing changes.
Odd length: the middle character stays where it is.
10⁵ characters: a recursive version is 50,000 calls deep — on a small stack that's a StackOverflowError, which is why the loop is the optimal answer.

practise next