344. Reverse String
Problem Description
The problem asks for a function that takes an array of characters s
and reverses it. It's important to note that the reversal must be done in-place, which means the original array must be modified without using any extra space for another array. The challenge specifically requires that the solution adhere to O(1)
extra memory usage, which means you cannot allocate additional memory that scales with the input size.
Intuition
The intuition behind the solution involves the realization that to reverse an array, you can swap elements from the beginning and the end moving inward. Picture the string as a line of people standing shoulder to shoulder, and you want them to face the other way. Instead of asking everyone to turn around, which would be like creating a new reversed array, you decide to have the person on one end swap places with the person on the other end, and so on, until you reach the middle.
That is exactly what the given solution does:
-
It starts with two pointers,
i
andj
. Pointeri
is positioned at the start of the array (index 0), andj
is positioned at the end of the array (indexlen(s) - 1
). -
While
i
is less thanj
, the while loop continues to run. -
Inside the loop, the characters at index
i
and indexj
are swapped. This can be thought of as two people in the line stepping out, passing by each other, and then stepping back in at each other's original positions. -
After the swap, the
i
index is incremented, and thej
index is decremented. This moves the pointers closer to the center of the array. -
The loop stops once
i
is no longer less thanj
, which means the pointers have met in the middle or passed each other, indicating that the entire array has been reversed.
By only using the existing array to store the characters, the solution uses O(1)
extra space, since the memory used does not depend on the size of the input array but only on a fixed number of index variables.
Learn more about Two Pointers patterns.
Solution Approach
The implementation of the provided solution employs a two-pointer technique as the core algorithm. This approach doesn't need any additional data structures, hence it sticks to the O(1)
extra memory constraint. Here's the step-by-step walk-through:
-
Initialization of Pointers: Two pointers are initialized:
i
starts at index0
(the beginning of thes
array), andj
starts atlen(s) - 1
(the end of thes
array). -
Loop Until Pointers Meet: We enter a loop that keeps running while
i < j
. The<
condition ensures that we don't swap elements that have already been swapped or try to swap the middle element with itself in an odd-length array. -
Swapping Elements: Inside the loop, we perform the swap.
s[i], s[j] = s[j], s[i]
is a Pythonic way to swap the values at two indices in a list. -
Moving Pointers: After the swap, we need to move the pointers. The
i
pointer is moved one step forward (toward the middle) by doingi += 1
, and thej
pointer is moved one step back (away from the end) by doingj -= 1
. -
Termination of Loop: The loop finishes when
i >= j
, meaning the pointers have met or crossed, and the entire arrays
has been reversed.
In terms of data structures, the input and output are the same array s
. We're not using any auxiliary data structures. This is purely an in-place transformation, an efficient pattern for situations where minimizing memory usage is crucial.
The pattern is simple and elegant, often used for reversing arrays or strings, and is a staple in a programmer's toolbox. It is also a good example of how to manipulate elements within a single data structure without additional memory overhead.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, consider a simple array of characters s = ['h', 'e', 'l', 'l', 'o']
. The goal is to reverse this array in place, resulting in s = ['o', 'l', 'l', 'e', 'h']
.
Here's how the algorithm works on this small example:
-
Initialization of Pointers: Start with two indices,
i = 0
andj = len(s) - 1
which isj = 4
. Soi
points to'h'
andj
points to'o'
. -
Loop Until Pointers Meet: The condition
i < j
isTrue
because0 < 4
. Therefore, we go into the loop. -
Swapping Elements: We perform the swap:
s[i], s[j]
becomess[j], s[i]
. After swapping, the array looks like this:s = ['o', 'e', 'l', 'l', 'h']
. -
Moving Pointers: We increment
i
by 1 and decrementj
by 1. Nowi = 1
andj = 3
. The pointeri
now points to'e'
andj
points to the second'l'
. -
Are Pointers Meeting?: Yes,
i < j
still holds true (since1 < 3
), so we repeat the swap. -
Second Swapping and Pointer Update: Swap the characters at index 1 and 3. The array now looks like this:
s = ['o', 'l', 'l', 'e', 'h']
. Then,i
is incremented to2
andj
is decremented to2
. -
Termination of Loop: Now
i
is equal toj
(2 = 2
), so the loop conditioni < j
is no longer satisfied. The loop stops.
At this point, we have completed the reversal of the array. The array began with the order ['h', 'e', 'l', 'l', 'o']
and after the process, it has been reversed in place to ['o', 'l', 'l', 'e', 'h']
. Using this two-pointer approach, the reversal was done in-place without requiring extra space.
Solution Implementation
1from typing import List
2
3class Solution:
4 def reverseString(self, string_list: List[str]) -> None:
5 """
6 Reverses the order of characters in the input string list in-place.
7
8 :param string_list: List of characters representing the string to be reversed.
9 :return: None, modifies the list in-place.
10 """
11
12 # Initialize two pointers.
13 left_pointer = 0
14 right_pointer = len(string_list) - 1
15
16 # Loop until the two pointers meet in the middle.
17 while left_pointer < right_pointer:
18 # Swap the characters at the left and right pointers.
19 string_list[left_pointer], string_list[right_pointer] = string_list[right_pointer], string_list[left_pointer]
20
21 # Move the pointers closer to the center.
22 left_pointer += 1
23 right_pointer -= 1
24
1class Solution {
2 // Method to reverse a string represented as a character array.
3 public void reverseString(char[] str) {
4 // Initialize two pointers. One starting from the beginning (left) and
5 // the other from the end of the array (right).
6 int left = 0, right = str.length - 1;
7
8 // Loop until the two pointers meet in the middle.
9 while (left < right) {
10 // Swap the characters at the left and right pointers.
11 char temp = str[left];
12 str[left] = str[right];
13 str[right] = temp;
14
15 // Move the pointers towards each other.
16 left++;
17 right--;
18 }
19 // After the loop, the string is fully reversed in place.
20 }
21}
22
1#include <vector> // Include the header needed for std::vector
2#include <algorithm> // Include the header for the std::swap function
3
4// Solution class containing the method to reverse a string
5class Solution {
6public:
7 // Function to reverse the characters in the vector 'str'
8 void reverseString(vector<char>& str) {
9 int leftIndex = 0; // Start index for the left side
10 int rightIndex = str.size() - 1; // Start index for the right side
11
12 // Continue swapping elements until the middle of the string is reached
13 while (leftIndex < rightIndex) {
14 // Swap elements at leftIndex and rightIndex
15 std::swap(str[leftIndex], str[rightIndex]);
16
17 // Move indices towards the middle
18 ++leftIndex;
19 --rightIndex;
20 }
21 }
22};
23
1/**
2 * Reverses an array of strings in place.
3 * @param {string[]} strArray - The array of strings to be reversed.
4 */
5function reverseString(strArray: string[]): void {
6 // Initialize two pointers, one at the start and one at the end of the array.
7 let startIdx = 0;
8 let endIdx = strArray.length - 1;
9
10 // Continue swapping elements until the start index is greater or equal to the end index.
11 while (startIdx < endIdx) {
12 // Destructuring assignment to swap elements at startIdx and endIdx.
13 [strArray[startIdx], strArray[endIdx]] = [strArray[endIdx], strArray[startIdx]];
14
15 // Move the start index forward and the end index backward.
16 startIdx++;
17 endIdx--;
18 }
19 // The strArray is modified in place, so no return statement is necessary.
20}
21
Time and Space Complexity
The time complexity of the provided code is O(n)
, where n
is the length of the string s
. This is because the code uses a while loop that iterates over each element of the string once to swap the characters.
The space complexity of the code is O(1)
as the reversal is done in place, and no additional space is used that grows with the input. Only two pointers i
and j
are utilized to make the swaps.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!