Problem:
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 int maxMirror(int[] nums) {
int len = nums.length;
int count= 0;
int max = 0;
for (int i = 0; i < len; i++){
count=0;
for (int j = len-1; i + count < len && j > -1; j--){
if(nums[i+count] == nums[j]){
count++;
}
else{
if (count > 0){
max = Math.max(count,max);
count = 0;
}
}
}
max = Math.max(count,max);
}
return max;
}
While this solves all of the examples provided by CodingBat, it actually isn't correct. Consider the array: {1, 4, 5, 6, 6, 5, 4, 1, 5, 4, 1}. Your code will result in 7, when the correct answer is 8, as it doesn't count the "1" that reaches the else statement. Here's how to correct it:
ReplyDeletepublic int maxMirror(int[] nums) {
int max = 0;
for (int i=0; i=0 && i+count < nums.length; j--) {
if (nums[i+count] == nums[j]) {
count++;
}
else if (count > max) {
max = count;
j++;
count = 0;
}
}
if (count > max) max = count;
}
return max;
}
There is no way this code solves the problem, because this code doesn't even compile.
Deletejust needed j++ in else statement;
Deleteto consider the same element as an initial element, when it comes from backword 1,4,5 then '1' which with forward 4th element is not the same, so loop goes to else statement, count becomes 0; and j is 6 already it's starting from element next to 1, not considering that '1' again; nums[j] should start again from '1' the last element that doesn't matched(so just putting j++ in else statement fixes that).
Consider the array { 8, 8, 9, 10, 9, 8, 8, 8 }. The correct answer have to be length 7. But even the fix with j++ isn't a correct fix for this special array { 8, 8, 9, 10, 9, 8, 8, 8 }. The correct answer must be j = j + count or the short form j += count. Than you realy goes step by step with j to left, independent of the count of the already found reverse elements.
DeleteHere is the same version of the full coding of the solution above, only with the fix j += count in else statement:
Deletepublic static int maxMirror(int[] nums) {
int maxReverse = 0;
int countReverse = 0;
for (int i = 0; i < nums.length; i++) {
countReverse = 0;
for (int j = nums.length - 1; i + countReverse < nums.length && j >= 0; j--) {
if (nums[i + countReverse] == nums[j]) {
countReverse++;
} else {
if (countReverse > 0) {
maxReverse = Math.max(maxReverse, countReverse);
j += countReverse;
countReverse = 0;
}
}
}
maxReverse = Math.max(maxReverse, countReverse);
}
return maxReverse;
}
This code is also correct and shorter(original post won't work for {1, 4, 5, 6, 6, 5, 4, 1, 5, 4, 1}, this one will:
ReplyDeletepublic int maxMirror(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; ++i)
for (int j = max + 1; j < nums.length - i + 1; ++j)
for (int k = i; k < nums.length - j + 1; ++k)
{ Boolean mir = true;
for (int m = 0; mir && m < j; ++m)
mir = nums[i + m] == nums[k + j - m - 1];
if (mir) max = j;
}
return max;
}
maybe it's better with 2 loops then 4 loops.
Deletepublic int maxMirror(int[] nums) {
ReplyDeleteint count = 0;
for(int i = nums.length;i>0;i--){
for(int j = 0; j<nums.length-i+1;j++){
int[] tmp1 = newTest(i,j,nums);
for(int k=0;k<nums.length-i+1;k++){
int[] tmp2 = newTestRev(i,k,nums);
if(arrEquals(tmp1,tmp2)){
return i;
}
}
}
}
return 0;
}
public boolean arrEquals(int[] a, int[] b){
if(a.length!=b.length) return false;
for(int i = 0;i<a.length;i++){
if(a[i]!=b[i]){
return false;
}
}
return true;
}
public int[] newTest(int i, int j, int[] nums){
int[] ans = new int[i];
for (int k = 0; k<i;k++){
ans[k] = nums[j+k];
}
return ans;
}
public int[] newTestRev(int i, int k, int[] nums){
int[] ans = new int[i];
for (int j=0; j<i; j++){
ans[j] = nums[i+k-j-1];
}
return ans;
}
This code will always work even for the exception test case showed in the comments.
ReplyDeletepublic int maxMirror(int[] nums) {
int max = 0;
int tc;
int ti;
int l = nums.length;
for(int i=0;i=i;j--){
if(nums[i+tc]==nums[j]){
tc++;
if(tc>max){
max=tc;
}
}
else{
tc=0;
if(nums[ti]==nums[j]){
tc++;
}
}
}
}
return max;
}
This code doesn't use any library function but three loops....
ReplyDeletepublic int maxMirror(int[] nums) {
int initial = 0;
int len = 0;
int max = 0;
boolean flag = true;
for (int i = 0; i < nums.length; i++) {
initial = i;
if(nums.length == 1)
{
max = 1;
break;
}
for (int j = nums.length - 1; j > 0; j--) {
if (nums[i] == nums[j]) {
if (j == 0 || i == nums.length - 1 || j == i) {
break;
}
flag = true;
len = 1;
while (flag) {
if (j == 0 || i == nums.length - 1) {
break;
}
if (nums[i + 1] == nums[j - 1]) {
len++;
++i;
--j;
if (max < len)
max = len;
} else {
flag = false;
i = initial;
}
}
}
}
}
return max;
}
public int maxMirror(int[] nums) {
ReplyDeleteif (nums.length == 0) {
return 0;
}
ArrayList lengths = new ArrayList();
int[] test;
for (int i = 1; i <= nums.length; i++) {
for (int j = 0; j < nums.length+1-i; j++) {
test = split(0+j, i+j, nums);
for (int x = 0; x <= nums.length-test.length; x++) {
if (match(test, split(x, (x+test.length), nums))) {
lengths.add((Integer) test.length);
}
}
}
}
Integer max = lengths.get(0);
for (int i = 0; i < lengths.size(); i++) {
if ((lengths.get(i)).compareTo(max) > 0) {
max = lengths.get(i);
}
}
return (int) max;
}
public int[] split(int start, int end, int[] arr) {
int[] output = new int[end-start];
int count = 0;
for (int i = start; i < end; i++) {
output[count] = arr[i];
count++;
}
return output;
}
public boolean match(int[] arr1, int[] arr2) {
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[arr1.length-1-i]) {
return false;
}
}
return true;
}
This code should return the right answer for all cases
who ever provided the code (solution) is a very smart guy, this is a very elegant solution to a tricky/lengthy problem, job very well done !
ReplyDeletepublic int maxMirror(int[] nums) {
ReplyDeleteint[] mirArr=new int[nums.length];
for(int i=0, j=nums.length-1; j>=0; i++,j--){
mirArr[i]=nums[j];
}
int max=0;
int count=0;
for(int k=0;kmax)max=count;
}
}
return max;
public int maxMirror(int[] nums) {
ReplyDeleteint max = 0;
for (int i = 0; i < nums.length; i++) {
int leftNum = nums[i];
int temp = 0;
for(int j = nums.length - 1; j >= 0; j--) {
int rightNum = nums[j];
if (leftNum == rightNum) {
temp = findMaxMirrorForPositions(nums, i, j);
max = temp > max ? temp : max;
}
}
}
return max;
}
private int findMaxMirrorForPositions(int[] nums, int leftPos, int rightPos) {
int temp = 0;
int j = rightPos;
for (int i = leftPos; i < nums.length; i++) {
if (nums[i] == nums[j])
temp++;
if (nums[i] != nums[j] || --j < 0)
break;
}
return temp;
}
int lastCount=0, maxCount=0;
ReplyDeleteboolean mirror=false;
for(int i=nums.length-1;i>=0;i--){
for(int j=0;j=0&&jkmaxCount) maxCount=lastCount;
lastCount=0;
}
}
return maxCount;
This comment has been removed by the author.
ReplyDeleteHere is the monstrosity that i came up with (works on example from comments):
ReplyDeletepublic int maxMirror(int[] nums) {
if(nums.length == 0) return 0;
int maxLength = 1;
int[] mirroredNums = new int[nums.length];
//создаем зеркальный массив
for(int i = 0; i < nums.length; i++) {
mirroredNums[i] = nums[nums.length-1-i];
}
for(int i = 0; i < nums.length; i++){
for(int y = i+1; y <= nums.length; y++){
boolean isEqual = false;
//берем ряд
int[] row = Arrays.copyOfRange(nums, i, y);
//ищем этот ряд в зеркальном массиве
for(int z = 0; z < mirroredNums.length; z++){
isEqual = Arrays.equals(row, Arrays.copyOfRange(mirroredNums,z,z+row.length));
if(isEqual){
int length = row.length;
if(length > maxLength) maxLength = length;
}
}
}
}
return maxLength;
}
I made it like this, I know the new mirror array is not necessary but it just simplified it for me.
ReplyDeletepublic int maxMirror(int[] nums) {
int[] nums2 = new int[nums.length]; // Make a new array nums2
int len = nums.length;
for(int i=0, j=len-1; i<len;i++,j--){ // Make nums2 mirror image of nums
nums2[j]=nums[i];
}
int result = 0; // result holds the final max value
int max = 0; // max holds the temporary max value
for(int i=0;i<len;i++){ // loop through nums
for(int j=0;j<len;j++){ // loop through nums2
if(nums[i]==nums2[j]){ // if you find a match, loop both arrays simultaneously
for(int k=i, l=j; k<len && l<len; k++, l++){ // k is now current index of nums and l is now current index of nums2
if(nums[k]==nums2[l]){ // if match is found increase max
max++;
}
else break; // if match is not found break the loop
}
}
if(result<=max){ // if new max value is bigger than previous max value
result = max; // save max value to result
}
max = 0; // make temporary max value 0
}
}
return result;
}
public int maxMirror(int[] nums) {
ReplyDeleteString str = Arrays.toString(nums).replaceAll("\\[|\\]|,","");
int rev[] = new int[nums.length];
int max = 0;
for(int i = nums.length-1,t = 0;i>=0;i--,t++)rev[t] = nums[i];
for(int a = 0,b = 1;b<=nums.length;b++){
String tmp = Arrays.toString(Arrays.copyOfRange(rev,a,b)).replaceAll("\\[|\\]|,","");
int arrln = Arrays.copyOfRange(rev,a,b).length;
if(str.contains(tmp)&&arrln>max)max = arrln;
if(!str.contains(tmp)){a++;b = a;}
}
return max;
}
public int maxMirror(int[] nums) {
ReplyDeleteint len = nums.length;
int max = 0;
if(len==0) return max;
for(int i=0; i=0; j--) {
if(nums[i+count]==nums[j]) {
count++;
}else if(count > 0){
max = Math.max(count,max);
count = 0;
}
}
max = Math.max(count, max);
}
if(max==1) max = 1;
return max;
}
public int maxMirror(int[] nums) {
ReplyDeleteint count = 0;
int max = 0;
for (int i = 0; i < nums.length; i++)
{
int pos = i;
for (int j = nums.length - 1; j >= 0; j--)
{
while (pos < nums.length && j >= 0 && nums[pos] == nums[j])
{
pos++;
j--;
count++;
}
max = Math.max(count, max);
count = 0;
}
}
return max;
}