LeetCode with C#-Reverse A String

LeetCode Logo

Welcome to my series on LeetCode and solving problems with C#. The goal of this series is to help those who are trying to solve LeetCode problems without directly giving them a copy paste answer. To help you direct your brain on how to think about the given problem.

With that let’s get into it. Today’s problem is Reversing a string.

If you just want the solution and skip all the fun, just scroll down to the bottom.

Problem

Write a function that reverses a 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.

You may assume all the characters consist of printable ascii characters.

What does this mean?

We are given an array of characters called s. It is of type char array. We need to reverse this array without allocating additional arrays to hold the data. We need to preform operations on this array and this array alone. The big O notation says that we should solve this with a constant linear time complexity.

If you’d like additional resources on how to solve this problem you can look here.

Linq Solution

public class Solution {
    public void ReverseString(char[] s) {
        Array.Reverse( s );
    }
}

Thoughts on the Linq Solution

Linq provided a very simple and readable way to solve this. You can simply call the Reverse method on your array. Under the hood this is doing something interesting though. From my research the Linq version is allocating a new array and iterating over the source and returning the new array. So this method is cheating; but LeetCode accepts it.

Iterative Solution (Two Pointer Technique)

public void ReverseString(char[] s) 
    {
       int b = 0;
       int e = s.Length - 1;
       char t;
       while (b <= e)
       {
         t = s[b];
         s[b] = s[e];
         s[e] = t;
         b++;
         e--;
       }        
    }

Thoughts on the Two Pointer Technique

The basics of what is going on here is that we have two pointers in the array. One at the beginning (b = 0) and one at the end (e = s.Length -1). We then loop through the array while our starting pointer does not equal our ending pointer.

During this loop we set a variable for our current looking at location to the start of the array (t = s[b];). We then set the first element in the array = to the last, the last equal to the first. Increment our starting index. Decrement our ending index. Then swap it all again until we meet in the middle and break the while loop.

Why does one solution matter over the other?

In short performance. As you can see here in both solutions the Linq solve and the two pointer technique allocate the same amount of memory but the two pointer technique is 60ms faster.

Linq Solution

Two Pointer Technique Solution

60ms isn’t much to really worry about in an application where timing is not critical.

Here over a longer set of data you can see the performance gains are different as well. Using 60 characters in an array we get the following results in processing time, roughly:

Linq: 420ms.

Two Pointer: 308ms.