leetcode

Reverse String solution using TypeScript

This post outlines my TypeScript solution to the "Reverse String" question on LeetCode using an iterative approach.

Algorithm: The solution places two pointers at each end of the inputted array. Each pointer iterates over the array by moving towards the center. On each iteration, swap the characters at the pointers. When the pointers arrive at the center of the array, the inputted array has been reversed.

Time Complexity: Because the array will be iterated n/2 times, the time complexity is O(n) where n represents the number of elements in the inputted array,

Space Complexity: Because the solution will use a constant amount of space, the space complexity is O(1).

/**
 * Reverse String
 * The input string is given as an array of characters char[].
 * Do not allocate extra space for another array, you must do 
 * this by modifying the input array in-place with O(1) extra memory.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * reverseString(["h","e","l","l","o"]) // ["o","l","l","e","h"]
 * reverseString(["H","a","h"]) // ["h","a","H"]
 */
function reverseString(s: string[]): void {
    // create two pointers on each end of the array
    let left = 0;
    let right = s.length - 1;
    
    // nothing to reverse
    if (s.length < 2) {
        return;
    }

    /*
     * reverse by moving each pointer towards the center,
     * swapping left and right values along the way
     */
    while (right > left) {
        // swap the values at the left and right pointers
        const temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        // move the pointers
        left += 1;
        right -= 1;
    }
}

more LeetCode posts