Response to an answer: Solution to maxMirror problem

Question

Garrett Openshaw had an okay answer to Codingbat maxMirror challenge

But there were a couple of issues with the code he gave, so I decided to review it and make it a little bit better.

I don't have access to Java here at work so I instead changed the code in C# which wasn't too much trouble.

I added a List<int[]> to keep track of all the test cases and added an extra loop to the outside of the the rest of the code.

I moved some variables as I mentioned in my comment to Garret's answer, and also moved some variables to the correct scope. It seems like there should be more I can do to simplify this answer.

There was indentation and bracketing issues that made it difficult to read that I also changed.

List<int[]> sequences = new List<int[]> { 
     new int[] {1, 2, 1, 2, 1},
     new int[] {1, 2, 3, 8, 9, 3, 2, 1},
     new int[] {1, 2, 1, 4},
     new int[] {7, 1, 2, 9, 7, 2, 1}
 };

foreach (var sequence in sequences)
{
    int maxLength = 1;
    int endIndex = sequence.Length - 1;
    for (int frontIndex = 0; frontIndex < endIndex; frontIndex++)
    {
        for (int i = endIndex; i > frontIndex; i--)
        {
           if (sequence[frontIndex] == sequence[i])
            {
                var currentLength = 0;
                while (frontIndex + currentLength < sequence.Length && i - currentLength >= 0)
                {
                    if (sequence[frontIndex + currentLength] == sequence[i - currentLength])
                    {
                        currentLength++;
                    }
                    else break;
                }
                if (currentLength > maxLength) 
                { 
                    maxLength = currentLength; 
                }                            
            }
        }
    }
    Console.WriteLine("Max length is " + maxLength);
    Console.ReadLine();
}

Answer 1

This is looking very good.

First thing I would do is split out a method, GetMaxMirror, and rename maxLength to maxMirror. Then I would put braces around the break, maybe invert the condition if (sequence[frontIndex] == sequence[i]) to reduce nesting, and call it a day.

Ah, whoops, this fails on an empty array by returning the answer 1. Fix, add a unit test, and now we're really done.

Until... I notice that the complexity looks like it's \$O(n^3)\$. Let's increment a counter in the inner while:

while (frontIndex + currentLength < sequence.Length && i - currentLength >= 0)
{
    steps++;
    ...

And run it on our test cases:

GetMaxMirror took 15 steps.
Max length is 5
GetMaxMirror took 9 steps.
Max length is 3
GetMaxMirror took 3 steps.
Max length is 3
GetMaxMirror took 7 steps.
Max length is 2

Not bad!

And after a bit of playing around, we find that it runs badly on this input

private static int[] GetBadInput(int length)
{
    var result = new int[length];
    result[length / 2 - 1] = 1;
    return result;
}

Now let's run it again:

sequences.Add(GetBadInput(1000));
sequences.Add(GetBadInput(2000));
sequences.Add(GetBadInput(3000));

GetMaxMirror took 104664252 steps.
Max length is 999
GetMaxMirror took 835328502 steps.
Max length is 1999
GetMaxMirror took -1477974544 steps.
Max length is 2999

Ahhhh... integer overflow in our counter? Not good.

So what can we do? Let's look at the problem statement again.

We'll say that a "mirror" section in an array is a group of contiguous elements such that somewhere in the array, the same group appears in reverse order. For example, the largest mirror section in {1, 2, 3, 8, 9, 3, 2, 1} is length 3 (the {1, 2, 3} part). Return the size of the largest mirror section found in the given array.

So we're looking for the longest contiguous sequence that appears in the input, and its reversal. This sounds like another problem, longest common substring (LCS).

In particular,

$$ maxMirror(S) = LCS(S, T) $$

where \$T\$ is \$S\$ reversed. If we can solve LCS, then we have a solution to maxMirror. Using dynamic programming, we can solve LCS in \$O(n^2)\$ time, with \$O(n)\$ space.

The pseudocode in that article is pretty good, so let's translate that to C#:

private static int GetMaxMirrorLcs(int[] sequence)
{
    var length = sequence.Length;
    var prevRow = new int[length];

    var maxMirror = 0;
    for (var i = 0; i < length; i++)
    {
        var row = new int[length];
        for (var j = 0; j < length; j++)
        {
            if (sequence[i] != sequence[length - j - 1])
            {
                continue;
            }

            row[j] = (i == 0 || j == 0)
                ? 1
                : prevRow[j - 1] + 1;
            maxMirror = Math.Max(maxMirror, row[j]);
        }

        prevRow = row;
    }

    return maxMirror;
}

Since we split out our method before, it's easy to test that these give the same results:

foreach (var sequence in sequences)
{
    int maxMirror = GetMaxMirror(sequence);
    int maxMirrorLcs = GetMaxMirrorLcs(sequence);
    if (maxMirror != maxMirrorLcs)
    {
        Console.WriteLine("Answers don't match!");
        Console.WriteLine("Input: [{0}].", string.Join(", ", sequence));
        Console.WriteLine("GetMaxMirror: {0}. GetMaxMirrorLcs: {1}.", maxMirror, maxMirrorLcs);
    }
}