{"id":40,"date":"2020-05-09T13:47:00","date_gmt":"2020-05-09T13:47:00","guid":{"rendered":"https:\/\/danwritescode.com\/?p=40"},"modified":"2020-06-22T14:39:22","modified_gmt":"2020-06-22T14:39:22","slug":"codility-max-product-of-three-100-on-solution-lesson-6","status":"publish","type":"post","link":"https:\/\/danwritescode.com\/codility-max-product-of-three-100-on-solution-lesson-6\/","title":{"rendered":"Codility Max Product Of Three 100% O(n) Solution"},"content":{"rendered":"\n
\"codility-max-product-of-three-100%\"<\/figure>\n\n\n\n

Below you can find my 100% solution to one of the Codility Lesson 6 practice challenges. The complexity of my solution is O(n) and passed all scores with 100%.<\/p>\n\n\n\n

The challenge – find the max product of three elements of an array.<\/h2>\n\n\n\n
Task description\nA non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 \u2264 P < Q < R < N).\n\nFor example, array A such that:\n\n  A[0] = -3\n  A[1] = 1\n  A[2] = 2\n  A[3] = -2\n  A[4] = 5\n  A[5] = 6\ncontains the following example triplets:\n\n(0, 1, 2), product is \u22123 * 1 * 2 = \u22126\n(1, 2, 4), product is 1 * 2 * 5 = 10\n(2, 4, 5), product is 2 * 5 * 6 = 60\nYour goal is to find the maximal product of any triplet.\n\nWrite a function:\n\nfunction solution(A);\n\nthat, given a non-empty array A, returns the value of the maximal product of any triplet.\n\nFor example, given array A such that:\n\n  A[0] = -3\n  A[1] = 1\n  A[2] = 2\n  A[3] = -2\n  A[4] = 5\n  A[5] = 6\nthe function should return 60, as the product of triplet (2, 4, 5) is maximal.\n\nWrite an efficient algorithm for the following assumptions:\n\nN is an integer within the range [3..100,000];\neach element of array A is an integer within the range [\u22121,000..1,000].<\/code><\/pre>\n\n\n\n
My O(n) complexity solution<\/h2>\n\n\n\n
The problem can be solved in O(n) without sorting the array. All you need to do is find the three maximums and the two minimums of the array and that requires only one pass.<\/p>\n\n\n\n
The logic behind the solution is:<\/p>\n\n\n\n
  • If the three maximums are all positives, their product will be the maximum.<\/li>
  • If the two minimums are negatives, their product will be a large positive.<\/li>
  • If between these 5 values there are three negatives or all of them are negatives, the maximum product will be the one between the two minimums and the maximum value of all the array.<\/li><\/ul>\n\n\n\n
    Below, the final code:<\/p>\n\n\n\n
    function solution(A) {\n\n    if (A.length === 3) {\n        return A[0] * A[1] * A[2]\n    }\n    \n    let min1, min2,max1, max2, max3\n    min1 = min2 = 1001\n    max1 = max2 = max3 = -1001\n    \n    for (let i = 0; i < A.length; i++){\n        if (A[i] > max1){\n            max3 = max2\n            max2 = max1\n            max1 = A[i]\n        } else if (A[i] > max2) {\n            max3 = max2\n            max2 = A[i]\n        } else if (A[i] > max3) {\n            max3 = A[i]\n        }\n    \n        if ( A[i] < min1) {\n            min2 = min1\n            min1 = A[i]\n        } else if (A[i] < min2){\n            min2 = A[i]\n        }\n    }\n\n    prod1 = max1 * max2 * max3\n    prod2 = max1 * min1 * min2\n\n    if (prod1 > prod2) {\n        return prod1\n    } else {\n        return prod2\n    }\n} <\/code><\/pre>\n\n\n\n
    Do you have another solution? Perhaps more efficient? Share it in the comments below!<\/p>\n","protected":false},"excerpt":{"rendered":"
    Below you can find my 100% solution to one of the Codility Lesson 6 practice challenges. The complexity of my solution is O(n) and passed all scores with 100%. The challenge – find the max product of three elements of an array. My O(n) complexity solution The problem can be solved in O(n) without sorting the array. All you need to do is find the three maximums and the two minimums of the array and that requires only one pass. The logic behind the solution is: If the three maximums are all positives, their product will be the maximum. If <\/p>\n","protected":false},"author":1,"featured_media":48,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,6],"tags":[],"_links":{"self":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/posts\/40"}],"collection":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/comments?post=40"}],"version-history":[{"count":0,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/posts\/40\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/media\/48"}],"wp:attachment":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/media?parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/categories?post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/tags?post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}