\n1) We can check for all values of K<\/code> from 0<\/code> to maximum value of 1st<\/sup> array, also for every value we check the score from both arrays and find the maximum difference. If found we store the scores in two variables.
\n2) After the whole array is iterated, we print the final scores.
\n3) This approach takes total O(N * M * maxValueofArray1)<\/code> where N<\/code> and M<\/code> are sizes of first and second array respectively. As we can see above approach is very inefficient, and can’t produce answers in the given time, so we move to a new efficient approach.<\/p>\n<\/blockquote>\nEfficient Approach<\/strong>:
\nUpper Bound of K:<\/em><\/strong> Upper Bound of K<\/code> in an array is an index at which element is greater than K<\/code> and element previous to it is smaller than K<\/code>.<\/p>\n\n1) If we sort both arrays, and the current element is set to K<\/code>, all values before it will get score 2 each, current elements and values after each will score 3 each. So sorting makes it easier to calculate the score in constant time.
\n2) After sorting, we calculate scores for both arrays for every element in the first array, where the value of K<\/code> becomes the current element. Afterward, we print the least difference from all these scores.
\n3) For calculating score at any element we set the value of K<\/code> to the current element, first array’s sum would be 2 points for each element before the current element, and 3 points for each element after it and the current element.
\n4) For sum of Second Array, we calculate Upper<\/code> Bound<\/code> of K<\/code> in the second array, below which all elements will score 2 points each and elements from upper bound will carry 3 points each.
\n5) We calculate the difference for both arrays and update values if the difference is more than the current difference.<\/p>\n<\/blockquote>\nExample<\/h3>\nLet first array be [8,9,7,6,10]\nand second array be [11,4,2,3,7],\n\nWe sort the arrays, where arrays becomes,\nfirst array = [6,7,8,9,10]\nsecond array = [2,3,4,7,11]\n\nLet the current index is 2, so the element and value of the current element is 8.\n\nSo the sum of First Array will be,\nsumFirst = 2*(currentIndex) + 3*(sizeFirst-currentIndex)\n\nHence, \nsumFirst = 2*(2)+3*(3)\nsumFirst = 13\nSo the sum of First Array will be,\nsumFirst = 2*(currentIndex) + 3*(sizeFirst-currentIndex)\n\nso,\nsumFirst = 2*(2)+3*(3)\nsumFirst = 13\nHence, for the sum of Second Array, we calculate the upper Bound of K( K is 8) in the Second Array.\nupperBoundK = 4, which means the next greater element to K exists at index 4 in the Second Array.\n\nHence we have find the upper bound,\nsum of Second Array will be,\nsumSecond = 2*(upperBoundK)+3*(sizeSecond-upperBoundK)\nsumSecond = 2*(4)+3*(1)\nsumSecond = 11\n\nhence, we can compare their difference and can update values.<\/code><\/pre>\nSolutions<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645096092583-Article_264.png\")
<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1646391000734-Ball-firing-game-01.png\")
<\/p>\n