MaxProductOfThree 100% Solution in Javascript
Question
My Solution I (O(NlogN))
function solution(A) { A.sort((a, b)=>(a - b)); // 2 types (--+) or (+++) let type1 = A[0]*A[1]*A[A.length-1]; let type2 = A[A.length-1]*A[A.length-2]*A[A.length-3]; return Math.max(type1, type2); }
My Solution II (O(N))
without sorting, finding max and min five times
function solution(A) { // 2 types (--+) (+++) // try to do without sorting let max = [-1001, -1001, -1001]; let index = [-1, -1, -1]; for (let i = 0; i < 3; i++) { for (let j = 0; j < A.length; j++) { if (A[j] > max[i] && j != index[(i+1)%3] && j != index[(i+2)%3]) { max[i] = A[j]; index[i] = j; } } } let min = [1001, 1001]; let index2 = [-1, -1]; for (let i = 0; i < 2; i++) { for (let j = 0; j < A.length; j++) { if (A[j] < min[i] && j != index2[(i+1)%2]) { min[i] = A[j]; index2[i] = j; } } } return Math.max(max[0]*max[1]*max[2], max[0]*min[0]*min[1]); }
My Solution III O(N)
without sorting, finding max and min five times The same concept of the above, but running 2N rather than 5N
function solution(A) { let max3 = [A[0], A[1], A[2]]; max3.sort((a, b)=>(a - b)); for (let i = 3; i < A.length; i++) { if (A[i] > max3[0]) { max3[0] = A[i]; max3.sort((a, b)=>(a - b)); } } // console.log(max3); let min2 = [A[0], A[1]]; min2.sort((a, b)=>(b - a)); // console.log(min2); for (let i = 2; i < A.length; i++) { if (A[i] < min2[0]) { min2[0] = A[i]; min2.sort((a, b)=>(b - a)); } } // console.log(min2); return Math.max(max3[0]*max3[1]*max3[2], min2[0]*min2[1]*max3[2]); }