Reverse String

📋

Problem

Imagine you have a secret message written backwards, and you want to read it correctly by reversing the letters in place.

Given an array of characters s, reverse the array in place. You must do this by modifying the input array directly with O(1) extra memory.

1 ≤ n ≤ 10^5s[i] is a printable ASCII character

Edge cases: Single character array → same arrayArray with all identical characters → same arrayEmpty array → no change

</>

IDE

def reverseString(s: list) -> None:public void reverseString(char[] s)void reverseString(vector<char>& s)function reverseString(s)

def reverseString(s):
    # Write your solution here
    pass

class Solution {
    public void reverseString(char[] s) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void reverseString(vector<char>& s) {
    // Write your solution here
}

function reverseString(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: helloNo reversal performed; forgot to swap characters in place.✅ Implement two-pointer swapping: swap s[left] and s[right], then increment left and decrement right.

Wrong: olleoSwapped incorrectly or only partially reversed; last character not swapped properly.✅ Ensure loop runs while left < right and swaps all pairs until pointers meet or cross.

Wrong: ollehhArray length miscalculated or out-of-bounds access causing extra characters.✅ Use correct array length and swap only within valid indices.

Wrong: Code crashes or returns empty due to missing base case for empty input.✅ Add check for empty array before swapping.

Wrong: Solution times out due to inefficient approach (e.g., recursion or nested loops).✅ Use iterative two-pointer approach with O(n) time complexity.

✓

Test Cases

Try testing your code on empty and single-element arrays to handle base cases.

Check your loop boundaries and pointer updates carefully for off-by-one errors.

Focus on optimizing your solution to linear time with constant space.

t1_01basic

Input{"s":["h","e","l","l","o"]}

Expectednull

⏱ Performance - must finish in 2000ms

Swapping characters from opposite ends until the middle reverses the string.

💡 Use two pointers starting at opposite ends of the array.

💡 Swap characters at these pointers and move them towards the center.

💡 Continue swapping until the pointers meet or cross.

Why it failed: Output incorrect - likely forgot to swap characters in place or swapped incorrectly. Fix by swapping s[left] and s[right] and moving pointers inward.

✓ Correctly reversed the string in place using two pointers.

t1_02basic

Input{"s":["a","b","c","d"]}

Expectednull

⏱ Performance - must finish in 2000ms

Even length array reversed by swapping opposite ends until center.

💡 Check how swapping works for even length arrays.

💡 Ensure pointers move correctly after each swap.

💡 Stop swapping when left pointer is no longer less than right pointer.

Why it failed: Incorrect output - possibly off-by-one error in pointer movement or loop condition. Fix by using while left < right and updating pointers correctly.

✓ Successfully reversed even length array in place.

t2_01edge

Input{"s":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Empty array remains unchanged after reversal.

💡 Consider what happens when the array is empty.

💡 Your code should handle n=0 without errors.

💡 No swaps needed if array length is zero.

Why it failed: Code crashes or modifies empty array - missing base case for empty input. Fix by checking if array length is zero before swapping.

✓ Handled empty array correctly without errors.

t2_02edge

Input{"s":["x"]}

Expectednull

⏱ Performance - must finish in 2000ms

Single character array remains the same after reversal.

💡 Check behavior when array length is one.

💡 No swaps needed if left and right pointers are the same.

💡 Ensure loop condition prevents unnecessary swaps.

Why it failed: Incorrectly modifies single element array - loop condition allows swapping same index. Fix by using while left < right, not <=.

✓ Single element array remains unchanged as expected.

t2_03edge

Input{"s":["z","z","z","z"]}

Expectednull

⏱ Performance - must finish in 2000ms

Array with all identical characters remains the same after reversal.

💡 Swapping identical characters should not change the array.

💡 Verify your swap logic does not alter values incorrectly.

💡 Check that swapping is done correctly even if characters are the same.

Why it failed: Output differs from input - swap logic corrupts identical characters. Fix by swapping using a temporary variable or tuple unpacking correctly.

✓ Correctly handled array with identical characters.

t3_01corner

Input{"s":["a","b"]}

Expectednull

⏱ Performance - must finish in 2000ms

Two character array reversed by swapping the two elements.

💡 Test minimal even length array behavior.

💡 Ensure pointers swap correctly and loop terminates after one swap.

💡 Check that no extra swaps occur after pointers cross.

Why it failed: Output same as input - likely forgot to swap or loop condition incorrect. Fix by swapping s[left] and s[right] once and stopping.

✓ Two character array reversed correctly.

t3_02corner

Input{"s":["a","b","c"]}

Expectednull

⏱ Performance - must finish in 2000ms

Odd length array reversed with middle element unchanged.

💡 Check that middle element remains in place for odd length arrays.

💡 Pointers should stop when they meet at the middle index.

💡 Verify loop condition uses strict inequality.

Why it failed: Middle element changed or swapped incorrectly - off-by-one error. Fix by using while left < right, not <=.

✓ Odd length array reversed correctly with middle element intact.

t3_03corner

Input{"s":["a","b","c","d","e","f"]}

Expectednull

⏱ Performance - must finish in 2000ms

Longer even length array reversed correctly.

💡 Check that all pairs are swapped correctly from opposite ends.

💡 Verify loop runs exactly n/2 times for even length.

💡 Ensure no index out of bounds errors.

Why it failed: Partial reversal or index errors - loop boundary incorrect. Fix by iterating while left < right and updating pointers properly.

✓ Longer even length array reversed correctly.

t4_01performance

Input{"s":["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) time complexity must complete within 2 seconds.

💡 Use two pointers to swap characters in place in O(n) time.

💡 Avoid extra space to meet memory constraints.

💡 Do not use recursive or brute force approaches that exceed O(n).

Why it failed: TLE due to O(n^2) or recursive approach. Fix by implementing iterative two-pointer swap in O(n).

✓ Efficient O(n) two-pointer solution confirmed.

Practice

1. You are given an array representing heights of vertical lines on the x-axis. You want to find two lines that together with the x-axis form a container, such that the container holds the maximum amount of water. Which algorithmic approach guarantees finding the optimal solution in O(n) time?

easy

A. Two pointers starting at opposite ends, moving the pointer at the shorter line inward.

B. Brute force by checking all pairs of lines and calculating their container area.

C. Dynamic programming to store maximum areas for subproblems of line pairs.

D. Greedy approach moving the pointer at the taller line inward to maximize area.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding two lines that maximize the container area, which depends on the minimum height and the distance between lines.

2. Step 2: Analyze algorithmic approaches

   Brute force (checking all pairs) is O(n²), dynamic programming is unnecessary and inefficient here, and moving the pointer at the taller line can miss optimal solutions. The two-pointer approach moving the pointer at the shorter line inward guarantees checking all promising pairs efficiently in O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach with shorter line pointer movement -> O(n) optimal [OK]

Hint: Two pointers move inward from ends, shorter line pointer moves [OK]

Common Mistakes:

• Moving pointer at taller line instead of shorter line
• Using DP unnecessarily
• Assuming greedy on taller line pointer works

2. Given the following code and input height = [1, 3, 2], what is the final returned value of maxArea(height)?

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Initialize pointers and max_area

   left=0, right=2, max_area = (2 - 0) * min(1, 2) = 2 * 1 = 2

2. Step 2: First iteration of while loop

   height[left]=1 < height[right]=2, so left moves to 1. width=2-1=1, current_height=min(3,2)=2, area=1*2=2. max_area remains 2.

3. Step 3: Second iteration

   left=1, right=2, height[left]=3 >= height[right]=2, so right moves to 1. width=1-1=0 ≤ 0, loop breaks.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Max area found is 2, but initial max_area was 2, no larger area found -> 2 [OK]

Hint: Trace pointer moves and area updates carefully [OK]

Common Mistakes:

• Off-by-one in width calculation
• Using max height instead of min height
• Not updating max_area correctly

3. You are given a sorted array and need to remove duplicates such that each element appears at most twice, modifying the array in-place. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Using a nested loop to count duplicates and shift elements accordingly

B. Using two pointers where the write pointer only advances if the current element differs from the element two positions before

C. Using a hash map to count occurrences and then reconstruct the array

D. Using dynamic programming to track the maximum allowed duplicates

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, and duplicates are allowed at most twice, so we can leverage order.

2. Step 2: Identify the approach that uses two pointers and index offset check

   This approach compares the current element with the element two positions before the write pointer to decide if it should be written, ensuring O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers with index offset check is the known optimal approach [OK]

Hint: Two pointers with offset check is optimal [OK]

Common Mistakes:

• Using nested loops causes O(n²) time
• Hash maps use extra space
• DP is unnecessary here

4. What is the time complexity of the optimal one-pass Dutch National Flag algorithm for sorting colors, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because it involves multiple swaps and pointer movements

B. O(n) but with O(n) extra space for auxiliary arrays

C. O(n^2) because swapping elements can cause repeated scanning

D. O(n) because each element is visited at most once with constant-time swaps

Solution

1. Step 1: Analyze loop iterations

   The algorithm uses three pointers and processes each element at most once, moving mid pointer forward or swapping with high pointer.

2. Step 2: Understand why complexity is O(n)

   Each swap or pointer move is O(1), and total operations are proportional to n, so time complexity is O(n). Candidates may confuse swaps causing repeated scans, but high pointer moves backward, ensuring no element is processed twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Algorithm is linear time with constant space [OK]

Hint: Each element processed once, swaps don't repeat work [OK]

Common Mistakes:

• Thinking swaps cause O(n^2)
• Confusing with quicksort complexity
• Assuming extra space needed

5. Consider the following buggy code for trapping rain water using two pointers. Which line contains the subtle bug causing incorrect trapped water calculation?

medium

A. Line updating right_max with 'if height[right] >= right_max:'

B. Line updating left_max with 'if height[left] > left_max:'

C. Line adding water with 'water += left_max - height[left]'

D. Line incrementing left pointer with 'left += 1'

Solution

1. Step 1: Compare left_max update condition

   The original correct code uses '>=' to update left_max, but here it uses '>' which skips updating when equal.

2. Step 2: Understand impact

   Not updating left_max when height[left] equals left_max causes undercounting trapped water in some cases.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Changing '>' to '>=' fixes subtle undercount bug [OK]

Hint: Check boundary conditions in max updates carefully [OK]

Common Mistakes:

• Using '>' instead of '>=' for max updates
• Incorrect pointer increments
• Misplaced water addition lines