Reversing Strings: A Two-Pointer Approach in JavaScript

Introduction

Welcome to my Dev.to blog post! In this article, we'll explore a solution for the classic "Reverse String" problem using an in-place approach. The solution is implemented in JavaScript and can be found in my GitHub repository EssentialAlgos. If you're looking to hire or connect with me, you can find my LinkedIn profile here and my GitHub profile here.

Problem Statement

The problem we're addressing is the Reverse String problem on LeetCode. Given an array of characters, we need to reverse the order of its elements in-place using O(1) extra memory.

Solution Overview

We're going to take a two-pointer approach to solve this problem. The reverse_string.js file contains the implementation of the solution:

// reverse_string.js

const reverseString = function(arrayOfStrings) {
    // Create pointers
    let startIndex = 0;
    let endIndex = arrayOfStrings.length - 1;

    // Iterate through the string
    while (startIndex < endIndex) {
        // Swap characters at indexes
        let temporaryChar = arrayOfStrings[startIndex];
        arrayOfStrings[startIndex] = arrayOfStrings[endIndex];
        arrayOfStrings[endIndex] = temporaryChar;

        startIndex++;
        endIndex--;
    }
};

module.exports = reverseString;

Code Walkthrough

1. We define the reverseString function that takes an array of characters as its parameter.

2. Two pointers, startIndex and endIndex, are initialized. The startIndex points to the beginning of the array, and the endIndex points to the end of the array.

3. We enter a loop that continues until the startIndex is less than the endIndex. This loop ensures that we only swap elements until we've reached the middle of the array.

4. Within the loop, we use a temporary variable to store the character at startIndex. We then swap the characters at startIndex and endIndex.

5. After swapping, we increment the startIndex and decrement the endIndex to move towards the center of the array.

6. The loop continues until the startIndex is no longer less than the endIndex.

7. The array has now been reversed in-place!

Unit Testing

I've also included unit tests in the reverse_string.test.js file to ensure the correctness of our solution. Here's a snippet of the test cases:

const reverseString = require("./reverse_string");

test('Reverses an empty array', () => {
    let arrayOfStrings = [];
    reverseString(arrayOfStrings);
    expect(arrayOfStrings).toStrictEqual([]);
});

test('Reverse a longer array of strings', () => {
    let arrayOfStrings = ["h","e","l","l","o"];

    reverseString(arrayOfStrings);
    expect(arrayOfStrings).toStrictEqual(["o","l","l","e","h"]);
});

Runtime Complexity

The runtime complexity of this solution is O(n), where n is the number of elements in the array. This is because we iterate through the array once, and for each iteration, we perform constant-time operations (swapping elements).

Conclusion

In this article, we explored an in-place solution to the "Reverse String" problem using a two-pointer approach. The solution is efficient and meets the requirement of using only O(1) extra memory. If you're interested in the code implementation and want to explore more algorithms, check out my GitHub repository EssentialAlgos.

Feel free to reach out to me on LinkedIn or GitHub if you have any questions or if you're interested in discussing algorithms, coding, or potential opportunities. Happy coding!

Connect with me:

• LinkedIn
• GitHub