How do you approach Reverse String?

Use two pointers, one at the start and one at the end.

What is the time complexity of Reverse String?

Time complexity: O(n) - traverse half the array. Space complexity: O(1) - in-place modification.

What are common mistakes on Reverse String?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

Sitelet https://gitgood.dev/coding/reverse-string

gitGood.dev

← Back to problems

Reverse String

EasyAlgorithms

Description

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1

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

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

Example 2

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

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

Constraints

- 1 <= s.length <= 10^5 - s[i] is a printable ASCII character.

Reverse String: approach, complexity and pitfalls

An easy two pointers problem, graded against 5 test cases (3 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Use two pointers, one at the start and one at the end.
Swap the characters at the two pointers and move them towards each other.
Stop when the pointers meet in the middle.

The optimal approach

Show the approach: Two Pointers

Use two pointers starting from both ends, swap characters, and move towards the center.

Time: O(n) - traverse half the array
Space: O(1) - in-place modification

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.