344. Reverse String

EasyTwo PointersString
Leetcode Link

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:

  1. It starts with two pointers, i and j. Pointer i is positioned at the start of the array (index 0), and j is positioned at the end of the array (index len(s) - 1).

  2. While i is less than j, the while loop continues to run.

  3. Inside the loop, the characters at index i and index j 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.

  4. After the swap, the i index is incremented, and the j index is decremented. This moves the pointers closer to the center of the array.

  5. The loop stops once i is no longer less than j, 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

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:

  1. Initialization of Pointers: Two pointers are initialized: i starts at index 0 (the beginning of the s array), and j starts at len(s) - 1 (the end of the s array).

  2. 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.

  3. 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.

  4. Moving Pointers: After the swap, we need to move the pointers. The i pointer is moved one step forward (toward the middle) by doing i += 1, and the j pointer is moved one step back (away from the end) by doing j -= 1.

  5. Termination of Loop: The loop finishes when i >= j, meaning the pointers have met or crossed, and the entire array s 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example 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:

  1. Initialization of Pointers: Start with two indices, i = 0 and j = len(s) - 1 which is j = 4. So i points to 'h' and j points to 'o'.

  2. Loop Until Pointers Meet: The condition i < j is True because 0 < 4. Therefore, we go into the loop.

  3. Swapping Elements: We perform the swap: s[i], s[j] becomes s[j], s[i]. After swapping, the array looks like this: s = ['o', 'e', 'l', 'l', 'h'].

  4. Moving Pointers: We increment i by 1 and decrement j by 1. Now i = 1 and j = 3. The pointer i now points to 'e' and j points to the second 'l'.

  5. Are Pointers Meeting?: Yes, i < j still holds true (since 1 < 3), so we repeat the swap.

  6. 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 to 2 and j is decremented to 2.

  7. Termination of Loop: Now i is equal to j (2 = 2), so the loop condition i < 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
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫