Caveman42 Caveman42 - 7 months ago 30
Java Question

Comparing an array to its mirror

Okay so I have a method that needs to take in an array full of

ints
, then check it against it's mirror to see what the largest mirror is that it matches to. So for example I have array
[7, 1, 2, 9, 7, 2, 1]
, the largest array that it can match is 2, being matched at
[1, 2]
.

Right now I have it broken into 3 methods. One that accepts the array, another that reverses the array and returns it (
mirrorArray
). and the 3rd being counting the size of the array that matches(
groupCount
). Here is what I have so far:

public int maxMirror(int[] nums) {
int[] revArray = mirrorArray(nums);

return groupCount(nums, revArray);
}

private int[] mirrorArray(int[] nums) {
int[] newArray = new int[nums.length];

for (int i = nums.length-1, j = 0; i >= 0; i--, j++) {
newArray[j] = nums[i];
}

return newArray;
}

private int groupCount(int[] aFor, int[] bRev) {
int maxCount = 0;
int groupSize = 1;

//get aFor value
for (int i = 0; i < aFor.length; i++) {
int[] tempA = Arrays.copyOfRange(aFor, 0, groupSize);

//loop through bRev and check for matches
for (int j = 0; j < bRev.length; j++) {
int[] tempB = Arrays.copyOfRange(bRev, j, j+groupSize);

if (Arrays.equals(tempA, tempB)) {
maxCount = tempA.length;
}
}

groupSize++;
}
return maxCount;
}


It is failing in the 3rd method somewhere (returning a 1 instead of a 2) and I'm stumped why the loops I have arnt returning what I want. Any help would be greatly appreciated.

NG. NG.
Answer

Alright I was curious...

Here's the problem:

int[] tempA = Arrays.copyOfRange(aFor, 0, groupSize);

You are always comparing tempB to the first subArray of length groupSize of aFor. Change that line to

int[] tempA = Arrays.copyOfRange(aFor, i, i + groupSize);

and it should work.

EDIT Keep the failure cases coming.. Seems an issue with the increment location of groupSize

   while (groupSize < aFor.length) {
      //get aFor value
      for (int i = 0; i < aFor.length; i++) {
        int[] tempA = Arrays.copyOfRange(aFor, i, i + groupSize);

        //loop through bRev and check for matches
        for (int j = 0; j < bRev.length; j++) {
          int[] tempB = Arrays.copyOfRange(bRev, j, j+groupSize);

          if (Arrays.equals(tempA, tempB)) {
            maxCount = groupSize;
          }
        }
      }
      groupSize++;
  }

This is not the most efficient, and it might be a fun exercise to optimize. One starting approach would be to start groupSize at aFor.length and decrement. As soon as maxCount is assigned, you can early return.

Edit 2

 int groupSize = aFor.length;
 while (groupSize >= 0) {
      //get aFor value
      for (int i = 0; i <= aFor.length - groupSize; i++) { // note this change
        int[] tempA = Arrays.copyOfRange(aFor, i, i + groupSize);

        //loop through bRev and check for matches
        for (int j = 0; j <= bRev.length - groupSize; j++) { // note this change
          int[] tempB = Arrays.copyOfRange(bRev, j, j+groupSize);

          if (Arrays.equals(tempA, tempB)) {
            return groupSize;
          }
        }
      }
      groupSize--;
  }
  return 1;
}

What was happening is that Arrays.copyOfRange was filling out of bounds numbers with zeroes. I also added the early exit opt I mentioned earlier. There are probably more optimizations that can be done