We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse String

Number: 344

Difficulty: Easy

Paid? No

Companies: Amazon, Apple, Microsoft, Google, Bloomberg, Meta, Infosys, EPAM Systems, Adobe, Goldman Sachs, Deutsche Bank

Problem Description

Given an array of characters representing a string, reverse the array in-place without using extra space for another array. The reversal should be achieved using O(1) extra memory.

Key Insights

  • Use the two-pointer technique, with one pointer starting at the beginning and the other at the end of the array.
  • Swap the elements at these pointers and move them towards the center.
  • Stop when the pointers cross (or meet in the middle).

Space and Time Complexity

Time Complexity: O(n), where n is the number of characters in the array.
Space Complexity: O(1) since only a constant amount of extra memory is used.

Solution

The solution uses the two-pointer approach to reverse the string in-place. By initializing one pointer at the start and one at the end of the array, we repeatedly swap the characters at these positions and then move them towards the center. This continues until the pointers meet or cross, ensuring the string is completely reversed without using additional space.

Code Solutions

def reverseString(s):
    # Initialize two pointers: one at the beginning (left) and one at the end (right)
    left, right = 0, len(s) - 1
    # Swap characters until the two pointers meet or cross
    while left < right:
        s[left], s[right] = s[right], s[left]  # Swap the characters at the left and right positions
        left += 1  # Move the left pointer to the right
        right -= 1  # Move the right pointer to the left
← Back to All Questions