Finding the largest mirror image of a subset/set of integers present in an array of integers

Question

The problem I am talking about is this:

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

Conditions for solving:

1. No other helper methods.
2. Do not use Java.util.Arrays.copyOf or any other utility under Arrays
3. Do not use collections.

The solution I got was a little messy, and any cleaner solutions are welcome.

public int maxMirror(int[] nums) {
 final int len=nums.length;
 if(len==0)
 return 0;
 int maxCount=1;
 boolean flag=false;
 for(int i=0;i<len;i++)
 {
 int tempCount=1;
 int count=i;
 flag=false;
 for(int j=len-1;j>=0&&(count<len);j--)
 {
 if((nums[count]==nums[j])&&!(flag))
 {
 flag=true;
 count++;
 continue;
 }
 if((nums[count]==nums[j])&&(flag))
 {
 tempCount++;
 count++;
 maxCount=(tempCount>maxCount)?tempCount:maxCount;
 continue;
 }
 if(!(nums[i]==nums[j])&&(flag))
 {
 flag=false;
 count=i;
 tempCount=1;
 continue;
 }
 if((j==count)||(j-count)==1)
 {
 flag=false;
 break;
 }
 }
 } 
 return maxCount; 
}

• mjolka: As your code has already been reviewed, I would just like to propose another solution: to find the longest common "substring" of the array and its reversal. Finding this by dynamic programming can be done in \$O(n^2)\$ time and \$O(n)\$ space.
• Anirudh: dynamic programming?
• mjolka: geeksforgeeks.org/longest-common-substring
• rolfl: @Anirudh - in case you were wondering, I have deleted my answer. My original mis-reading of the specification meant I made assumptions which were unnecessary, and lead to code that scaled worse than necessary.
• Emily L.: @mjolka OP's answer performs in \$\mathcal{O}(n^2)\$ time and \$\mathcal{O}(1)\$ space (ignoring the space needed for the problem input). DP is overkill here.

Answer 1

Readibility

Whitespaces are free and make things easier to read. Also, you do not need that many parenthesis.

Also, indentation seems a bit weird. After fixing this, here is what I have :

public class MaxMirror {
 public static int maxMirror(int[] nums) {
 final int len = nums.length;
 if (len == 0)
 return 0;
 int maxCount = 1;
 boolean flag = false;
 for (int i = 0; i<len; i++)
 {
 int tempCount = 1;
 int count = i;
 for (int j = len-1; j>= 0 && (count<len); j--)
 {
 if (nums[count] == nums[j] && !flag)
 {
 flag = true;
 count++;
 continue;
 }
 if (nums[count] == nums[j] && flag)
 {
 tempCount++;
 count++;
 maxCount = (tempCount>maxCount)?tempCount:maxCount;
 continue;
 }
 if (nums[i] != nums[j] && flag)
 {
 flag = false;
 count = i;
 tempCount = 1;
 continue;
 }
 if (j == count || (j-count)==1)
 {
 flag = false;
 break;
 }
 }
 } 
 return maxCount; 
 }
 public static void main(String[] args) {
 System.out.println("Hello, world!");
 int[] num = {1, 2, 3, 8, 9, 3, 2, 1};
 System.out.println(maxMirror(num));
 int[] num2 = {1, 2, 1, 4};
 System.out.println(maxMirror(num2));
 int[] num3 = {7, 1, 2, 9, 7, 2, 1};
 System.out.println(maxMirror(num3));
 }
}

Re-writting the logic

Instead of using continue, you could just use else between your conditions.

Also, if you have to consider A && B and then A && !B, you should probably consider A and then, as a subcase, the validity of B.

Then, you can remove common code from the then block and the else block.

You can use max instead of checking which value is bigger.

You could move your check count < len to the only place where count could become bigger than len.

You can rewrite (j-count)==1 to make it look like the previous expression : j == (count+1) seems slightly better.

This being done, your code looks like :

public static int maxMirror(int[] nums) {
 final int len = nums.length;
 if (len == 0)
 return 0;
 int maxCount = 1;
 boolean flag = false;
 for (int i = 0; i<len; i++)
 {
 int tempCount = 1;
 int count = i;
 for (int j = len-1; j>= 0; j--)
 {
 if (nums[count] == nums[j])
 {
 if (flag)
 {
 tempCount++;
 maxCount = Math.max(tempCount, maxCount);
 }
 flag = true;
 count++;
 if (count>=len)
 break;
 }
 else if (nums[i] != nums[j] && flag)
 {
 flag = false;
 count = i;
 tempCount = 1;
 }
 else if (j == count || j == (count+1))
 {
 flag = false;
 break;
 }
 }
 } 
 return maxCount; 
}

Algorithm

Your algorithm seems to be working. However, I find it hard to understand. I guess a bit of documentation would be useful.

Edit : bug found ?

On int[] num5 = {7, 7, 7, 7, 6, 7, 7};, the function returns 6 and I do not see why.

Edit 2

I originally posted this as a different answer because it is not related to the beginning of this message in any way but this doesn't seem to be much appreciated. As it can be relevant to you, I'm posting this here.

As your code doesn't really work and I got quite interested by this problem : I took mjolka's precious comments into account.

Re-adapting code from the link in his comment, here what I got :

public class MirrorString {
 /* Returns length of longest common substring of X and Y */
 public static int LCSubStr(int[] X /* WAS , int[] Y*/)
 {
 int m = X.length;
 int n = m; // WAS int n = Y.length;
 // Create a table to store lengths of longest common suffixes of
 // substrings. Notethat LCSuff[i][j] contains length of longest
 // common suffix of X and Y. The first row and
 // first column entries have no logical meaning, they are used only
 // for simplicity of program
 int[][] LCSuff = new int[m+1][n+1];
 int result = 0; // To store length of the longest common substring
 /* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */
 for (int i=0; i<=m; i++)
 {
 for (int j=0; j<=n; j++)
 {
 if (i == 0 || j == 0)
 LCSuff[i][j] = 0;
 else if (X[i-1] == X[n-j]) // WAS else if (X[i-1] == Y[j-1])
 {
 LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
 result = Math.max(result, LCSuff[i][j]);
 }
 else LCSuff[i][j] = 0;
 }
 }
 return result;
 }
 public static void main(String[] args) {
 System.out.println("Hello, world!");
 System.out.println(LCSubStr(new int[] {7, 7, 7, 5, 6, 7, 7})); // 3
 System.out.println(LCSubStr(new int[] {7, 7, 7, 7, 6, 7, 7})); // 5
 System.out.println(LCSubStr(new int[] {})); // 0
 System.out.println(LCSubStr(new int[] {1})); // 1
 System.out.println(LCSubStr(new int[] {1, 1})); // 2
 System.out.println(LCSubStr(new int[] {1, 1, 1})); // 3
 System.out.println(LCSubStr(new int[] {1, 2, 3, 2, 1})); // 5
 System.out.println(LCSubStr(new int[] {1, 2, 3, 8, 9, 3, 2, 1})); // 3
 System.out.println(LCSubStr(new int[] {1, 2, 1, 4})); // 3
 System.out.println(LCSubStr(new int[] {7, 1, 2, 9, 7, 2, 1})); // 2
 }
}

I have adapted the code a bit. Then, the only places where the algorithm has been changed are marked with WAS :

• only one argument is required now
• instead of accessing the j-1th element from J, we access the n-jth element from X (simulating a backward traversal).

Please note that things could be done in an even more efficient way using a different data structure as per the wikipedia page about Longest Common Substring problem.

• Anirudh: Thanks for such a nice review, btw is using 'continue' performance wise bad as compared to if else?
• SylvainD: Not quite sure. It should be roughly the same (the generated bytecode might be exactly the same after compilation). In any case, for that kind of problem, you should go for algorithm optimisation and not micro-optimisation. Readibility matters too.
• Anirudh: Yeah in the case you mentioned it should return 4 I think.
• David Z: Actually 5? For 7,7,6,7,7
• Anirudh: yes..5 should be the max length of mirror