Codingbat maxMirror challenge

Question

I request you to provide insightful suggestions to improve the following code as well as an alternative algorithm to solve it.

Problem Specification:

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.

maxMirror({1, 2, 3, 8, 9, 3, 2, 1}) → 3

maxMirror({1, 2, 1, 4}) → 3

maxMirror({7, 1, 2, 9, 7, 2, 1}) → 2

Solution:

public class MaxMirror {
    public static void main(String[] args) {
        MaxMirror max = new MaxMirror();
        int[] nums = { 1, 2, 1, 4 };
        System.out.println("The maximum length of the mirror is "
                + max.maxMirror(nums));
    }

    public int maxMirror(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // Reverse order of the array
        int[] revNums = new int[nums.length];
        for (int numIndex = nums.length - 1, revIndex = 0; numIndex >= 0; numIndex--, revIndex++) {
            revNums[revIndex] = nums[numIndex];
        }
        // Hope the sub array of maximum length is the array itself
        int subArraysToBeChecked = 1;
        for (int len = nums.length; len > 1; len--) {
            if (mirrorOfLengthLenExists(nums, revNums, len,
                    subArraysToBeChecked)) {
                return len;
            }
            // Increase the number of sub-arrays to be checked
            subArraysToBeChecked++;
        }
        // In the worst case return 1
        return 1;
    }

    // Choose start and end i.e. sub-arrays to be checked
    public boolean mirrorOfLengthLenExists(int[] nums, int[] revNums, int len,
            int subArraysToBeChecked) {
        int start = 0;
        int end = len - 1;
        for (int i = len; i <= nums.length; i++) {
            if (mirrorExistsFromStartToEnd(nums, revNums, start, end,
                    subArraysToBeChecked)) {
                return true;
            }
            start++;
            end++;
        }
        return false;
    }

    // Check from start to end whether mirrored in the revNums
    public boolean mirrorExistsFromStartToEnd(int[] nums, int[] revNums,
            int start, int end, int subArraysToBeChecked) {
        int revStart = 0;
        for (int subArraysChecked = 1; subArraysChecked <= subArraysToBeChecked; subArraysChecked++) {
            int noOfElementsEqual = 0;
            for (int numIndex = start, revIndex = revStart; numIndex <= end; numIndex++, revIndex++) {
                if (revNums[revIndex] != nums[numIndex]) {
                    break;
                } else {
                    ++noOfElementsEqual;
                }
            }
            if (noOfElementsEqual == (end - start + 1)) {
                return true;
            }
            revStart++;
        }
        return false;
    }
}

Answer 1

There are a few things you should consider changing in your code. Most of them are trivial, but there's also an alternative algorithm you should consider too.

The easy stuff first:

• Your method starts with:

  if (nums.length == 0) {
      return 0;
  }
  

  this could easily be:

  if (nums.length <= 1) {
      return nums.length;
  }
  

  which would eliminate a small amount of work for conditions which are 'obvious'.

• You have a code-pattern which I consider to be an 'anti-pattern' - loops with multiple co-dependent indices that are not incremented together. Let me explain... you have:

  // Hope the sub array of maximum length is the array itself
  int subArraysToBeChecked = 1;
  for (int len = nums.length; len > 1; len--) {
      ....
      // Increase the number of sub-arrays to be checked
      subArraysToBeChecked++;
  }
  

  In this case, both len and subArraysToBeChecked are co-dependent. You should either make that co-dependency obvious, or you should make the loop-dependence obvious:

  for (int len = nums.length; len > 1; len--) {
      // make co-dependency obvious
      int subArraysToBeChecked = nums.length - len + 1;
      ....
  }
  

  or

  for (int len = nums.length, subArraysToBeChecked = 1; len > 1; len--, subArraysToBeChecked++) {
      ....
  }
  

  This anti-pattern is apparent in all your methods. In maxMirror it is with subArraysToBeChecked, in mirrorOfLengthLenExists it is with both start and end, and in mirrorExistsFromStartToEnd it is with revStart.

  In most of these cases the variables are not needed at all. For example, inside mirrorExistsFromStartToEnd you can easily calculate the value as int subArraysToBeChecked = nums.length - len + 1

• Your variable names are very descriptive, but I am almost hesitant to say some of them are too long?

OK, on to the algorithm.

• It may seem to you that having two arrays, one forward, and the other reversed, will make things easier. This is not always true. In this case, I think the second array is a distraction. You should get your head in the 'backward' space as much as in the 'forward' space. Think of it like being right-handed or left-handed. The best solution is to be ambidextrous. What you are doing is converting everything so you can treat it in a right-handed way, when what you should be doing is training yourself to be just as good in both orientations. You are slowing yourself down by having to convert your problem-space in to a structured form of your thinking, instead of thinking in the structure of your problem. OK, pep-talk done.... ;-)

• On the other hand, what I like about what you are doing is that you are starting optimistically with your algorithm ... you are searching for large mirror-values, and then working smaller and smaller until you find one. This is a good thing. It means that you can exit-early from your search. If you start small, and work up, you have to keep searching until you have exhausted the entire problem-space. Also, the bigger mirror values are faster to check than the smaller ones (there are many more smaller ones than larger ones).

• But... ;-), what you should consider is doing things optimistically from both sides of the problem. In other words, start big, and work down, but, you should also remember the longest matches you have found so far on the things you have already tested. This will mean that you can exit even earlier if it is convenient, and you never need to test things twice.

So, keeping all of that in mind, here is a routine that remembers the longest match it has found, while still looking optimistically. When it gets to smaller searches, it checks to see whether it has already found a match with that overlap, and it exits early.

There is one tricky part here, and that is the logic that makes it only check each position once. The logic goes like this.... Consider the array {1,2,3,8,2,1}. We think optimistically, and check if the entire array is one mirror. We start at 0, and check to see whether it has a 6-sized match if we check backwards from 5. We find that the longest match is {1,2} which is length 2, and there is no six-sized match. We remember this longest match. Now we look for matches of size 5, and, since we have already checked for six-sized from position 0 and 5, we check for positions 0 and 1 against position 4, and position 1 against positions 4 and 5. These checks only hit a size of 1, so it's not better than 2. Note how we only needed to check the stuff that has not yet been checked?

OK, here's the code that can do this:

/**
 * This method will return the length of the largest mirrored data value sequence.
 * Data values are mirrored when a sequence of values also appears in reverse-order in the data. 
 * @param data the data to search for sequences.
 * @return the length of the longest mirrored sequence
 */
public static final int maxMirror(final int[] data) {
    int maxlen = 0;
    for (int trylen = data.length; trylen > 1; trylen--) {
        if (maxlen >= trylen) {
            // a previous longer attempt found this match already.
            return maxlen;
        }
        int foundlen = findMirror(data, trylen);
        if (foundlen > maxlen) {
            maxlen = foundlen;
        }
    }
    return data.length;
}

private static final int findMirror(final int[] data, final int trylen) {
    int longest = 0;

    // margin is how far from the left-right edges we need to be limited to.
    // the values at each margin have never been checked against anything else.
    final int leftmargin = data.length - trylen;
    // what is the index on the margin on the right?
    final int rightmargin = data.length - leftmargin - 1;

    // check the value at the left-margin against all unchecked possibilities on the right-side.
    // start with the longest possible match (trylen) and then try smaller attempts.
    for (int right = data.length - 1; right >= rightmargin; right--) {
        int match = compare(data, leftmargin, right, trylen);
        if (match == trylen) {
            return match;
        }
        if (match > longest) {
            longest = match;
        }
    }
    // check the value at the right-margin with never-before-checked left-side values.
    // note we start left at 0 because that will produce the longest possible match.
    // also, we do not check left == leftmargin because that has already been tested in previous loop.
    for (int left = 0; left < leftmargin; left++) {
        int match = compare(data, left, rightmargin, trylen);
        if (match == trylen) {
            return match;
        }
        if (match > longest) {
            longest = match;
        }
    }
    return longest;
}

private static int compare(int[] data, int left, int right, int trylen) {
    // simple function that returns the longest 'overlap' of mirror values of a given length and position. 
    for (int i = 0; i < trylen; i++) {
        if (data[left + i] != data[right - i]) {
            // difference when checking the i'th position
            return i;
        }
    }
    // exact match for this length.
    return trylen;
}

Answer 2

My approach is to have two indexes. The i index starts at the left and the j index starts at the right of the array. For a length of 4, we would do these comparisons in this order. (0, 3), (0, 2), (0, 1), then (1, 3), (1, 2), then, (2, 3) This is basically a pairwise comparison. (Note the initialization part of the for loop is empty)

int frontIndex = 0;
int endIndex = sequence.length - 1;
for( ; frontIndex < endIndex; frontIndex++)
{
    for(int i = endIndex ; i > frontIndex; i--)
    {
    //stuff here
    }
}

Once a match is found, we start counting the max length, with one index moving to the left and one to the right. The while condition makes sure we don't go out of bounds. Once we break out of that loop, we may update the max length.

while(frontIndex + currentLength < sequence.length && i - currentLength >= 0)
{
    if(sequence[frontIndex + currentLength] == sequence[i - currentLength]) 
    {
        currentLength++;
    }
    else break;
}
if (currentLength > maxLength) maxLength = currentLength;
currentLength = 0;

This is the entire class

public class Mirrors 
{
    public static void main(String[] args)
    {
        int maxLength = 1;
        int currentLength = 0;
        int[] sequence = {1, 2, 1, 2, 1};
        int frontIndex = 0;
        int endIndex = sequence.length - 1;
        for( ; frontIndex < endIndex; frontIndex++)
        {
            for(int i = endIndex; i > frontIndex; i--)
            {
                if(sequence[frontIndex] == sequence[i])
                {
                    currentLength++;
                    while(frontIndex + currentLength < sequence.length && i - currentLength >= 0)
                    {
                        if(sequence[frontIndex + currentLength] == sequence[i - currentLength]) 
                        {
                            currentLength++;
                        }
                        else break;
                    }
                    if (currentLength > maxLength) maxLength = currentLength;
                    currentLength = 0;
                }
            }
        }
        System.out.print("Max length is " + maxLength);
    }
}