Creating a super-efficient Inverted String algorithm in C#

#algorithms #computerscience #csharp #performance

Invert an string is one of most common DSA problem required in interviews. But beyond working, it needs to be efficient, and efficient here means:

Modifying the input array in-place with O(1) extra memory.
O(n) time
O(1) Space

O(n) is a notation used to describe the time complexity of an algorithm. It indicates that the execution time of the code grows linearly with respect to the size of the input (n). If you have an array with n elements, an O(n) algorithm will have to perform a number of operations that is proportional to n.

For example, if the array has 10 items, the computer performs (approximately) 10 operations. If the array has 1.000 items, the computer performs (approximately) 1.000 operations. If you double the size of the input, the execution time will also double.

O(1) Space (or Constant Space) means that the amount of extra memory you use doesn't change, regardless of whether the array has 5 characters or 5 trillion characters. If you solve the problem using only the data you've already received, you are using constant space.

✨ Hands on

To do that, let's first imagine the easiest way:

Define an index l starting in 0.
Define an index r with the array length - 1.
While the index l is less than index r:
- Trade the characters in the positions l and r.
- Increase index l.
- Decrease index r.

🛠️ C# Implementing

public void ReverseString(char[] s) {

       if(s == null || s.Length <= 1)
            return;

        // Creating the pointers
        var l = 0;
        var r = s.Length - 1;

        while (l < r)
        {
            // Manual swap to ensure 0(1) space
            var temp = s[l];
            s[l] = s[r];
            s[r] = temp;

            // Moving the pointers to the center
            l++;
            r--;
        }
    }

✅ Why does this meet the requirements?

O(n) time: We traverse the array only once (actually, only half of it, n/2), which simplifies to linear complexity.
O(1) space: We do not allocate memory proportional to the input size. We only use three integer/char variables(l, r, temp), regardless whether the array has 10 or 10 million elements.

Using tuples (C# 7.0+)

It's possible to use another approach with tuples. Instead of managing two independent pointers (l++ and r--), we can use mathematics to derive the index r from l:

void ModernReverseString(char[] s) {
    // The loop ends naturally when it reaches the middle (s.Length / 2)
    for(int l = 0; l < s.Length / 2; l++)
    {
        int r = s.Length - 1 - l;

        (s[l], s[r]) = (s[r], s[l]);
    }
}

When l = 0, then r = length - 1 (the last one).
When l = 1, then r = length - 2 (the second to last one).
The formula s.Length - 1 - l is an elegant way to find the "pair" of the current element on the other side of the array.

The syntax:

(s[l], s[r]) = (s[r], s[l]);

This is what we call Tuple Deconstruction Assignment. It's the most modern and "clean" way to perform a swap in C#. Under the hood, the compiler generates very efficient code, similar to using the temp variable, keeping the space in O(1).