Find Maximum Index Product
Find Maximum Index Product
+ 0 comments This is a variation of NGL + NGL problem and I acheived it in 0(n). Two test cases were failing for me. It was because the output value is more than MAX_VALUE of integer. So, I changed the already added code to use long instead. Just wanted to know, isnt it incorrect to collect the output in "int" when the value can be greater than MAX_VALUE of Integer in java? Any thoughts?
+ 0 comments a good classical problem to practice a "monotonous stack" technique. The fact that the return type in the template is not consistent with the constraints makes the problem weird feels more like a template bug
+ 0 comments My solution in Javascript, it passed all test cases..
function solve(arr) { let max = 0; for (let i = 1; i < arr.length - 1; i++) { // check if 2 adjacent numbers are the same and terminate current iteration if so if(arr[i] === arr[i - 1]) { continue; } // check closest index on left side which value is more than the current value let x = i - 1, leftI = 0; while(x >= 0) { if(arr[i] < arr[x]) { leftI = x + 1; break; } x--; } // check closest index on right side which value is more than the current value let y = i + 1, rightI = 0; while(y < arr.length) { if(arr[i] < arr[y]) { rightI = y + 1; break; } y++; } // multiply the indexes and find the max result let indexProduct = leftI * rightI; if(indexProduct > max) { max = indexProduct; } } return max }
+ 0 comments Key strategy: a) long long int b) use of stack in a dynamic programming style c) round trip traversal
+ 0 comments Simples Java solution
public static long solve(List<Integer> arr) { int maxInArray = arr.get(0); long max = 0; for (int i=0; i<arr.size(); i++) { if (arr.get(i) > maxInArray) { maxInArray = arr.get(i); } int num = arr.get(i); if (num == maxInArray){ continue; } long left = 0; for (int j=i-1;j>=0;j--) { if (arr.get(j) > num) { left = j+1; break; } } if (left == 0) { continue; } long right = 0; for (int j=i+1; j<arr.size();j++){ if (arr.get(j) > num) { right = j+1; break; } } if (right == 0) { continue; } if (left*right > max) { max = left * right; } } return max; }
Sort 109 Discussions, By:
Please Login in order to post a comment