Optimal Utilization

Question

I was doing Optimal Utilization code from leetcode

Question Link: https://leetcode.com/discuss/interview-question/373202

Question: Given 2 lists a and b. Each element is a pair of integers where the first integer represents the unique id and the second integer represents a value. Your task is to find an element from a and an element form b such that the sum of their values is less or equal to target and as close to target as possible. Return a list of ids of selected elements. If no pair is possible, return an empty list.

For this I wrote the following algorithm

let a, b, target
const currentHighest = (array1, array2, target) => {
 const hashMapA = {}
 const hashMapB = {}
 const arr1 = array1.sort((a, b) => {
 hashMapA[[a[1]]] = a[0]
 hashMapA[[b[1]]] = b[0]
 return a[1] - b[1]
 })
 const arr2 = array2.sort((a, b) => {
 hashMapB[[a[1]]] = a[0]
 hashMapB[[b[1]]] = b[0]
 return a[1] - b[1]
 })
 const id = {}
 const currentHighest = {
 difference: Infinity,
 indexes: []
 }
 let i = 0
 const arr2mid = parseInt(arr2.length / 2)
 while (i < arr1.length) {
 const a1 = arr1[i]
 const difference = target - a1[1]
 if (hashMapB.hasOwnProperty(difference)) {
 if (!id.hasOwnProperty(a1[0])) {
 if (currentHighest.difference !== 0) currentHighest.indexes = []
 id[[a1[0]]] = true
 currentHighest.difference = 0
 currentHighest.indexes.push([a1[0], hashMapB[difference]])
 }
 } else {
 let j = 0;
 let itteratorEndpoint = arr2.length
 if (difference > arr2[arr2mid][1]) j = arr2mid
 while (j < itteratorEndpoint && difference > arr2[j][1]) {
 const a2 = arr2[j]
 const difference2 = target - a2[1]
 if (hashMapA.hasOwnProperty(hashMapA[difference2])) {
 if (!id.hasOwnProperty(a2[0])) {
 if (currentHighest.difference !== 0) currentHighest.indexes = []
 id[[hashMapA[difference2]]] = true
 currentHighest.difference = 0
 currentHighest.indexes.push([hashMapA[difference2], a2[0]])
 }
 }
 const actualDifference = target - (a1[1] + a2[1])
 if (actualDifference > -1) {
 if (currentHighest.difference === actualDifference) currentHighest.indexes.push([a1[0], a2[0]])
 if (currentHighest.difference > actualDifference && currentHighest.difference !== 0) {
 currentHighest.difference = actualDifference
 currentHighest.indexes = [
 [a1[0], a2[0]]
 ]
 }
 }
 j++
 }
 }
 i++
 }
 return currentHighest.indexes
}
a = [
 [1, 8],
 [2, 15],
 [3, 9]
]
b = [
 [1, 8],
 [2, 11],
 [3, 12]
]
target = 20
console.log(currentHighest(a, b, target))

My approach

1. Sort both the arrays and while sorting create an hashMap for A and B

2. id objects make sure if the specific id is not already been iterated over

3. current Index is used to track differences and indexes of those difference.

4. I am starting iteration using while loop, over the sorted array arr1

5. We check the difference between the target value and value of current element in arr1 if the difference exist in hashMapB we are storing the indexes in currentHighest and setting the difference to zero

6. Else, We check the value of midpoint in arr2. we use it compare the value at our midpoint in arr2 and value of our difference, if difference in greater than we can iterate from the midpoint to the point where our difference remains greater

7. Creates difference2 which checks if the value exist in hashMap A, if it does, it will do the same thing which we did previously

8. if not, we calculate the difference between arr1 element and arr2 and that iteration, compare their value and if the difference in their value happens to be less than our stored difference, we set indexes and make that our new difference

9. we return currentHighest.indexes

while the following code, does work, I am not thinking it is optimal. Can someone help me and suggest me on how I can make this code for optimize?

• iRohitBhatia: @Blindman67 Sorry for spamming your notification but since I so admire your previous answer on my post, I would love if you could take a look?
• Roland Illig: Your code is quite long for a task that sounds quite simple. Can you give a summary of what the code does, to give us some hints about the purpose of all these variables you use? The name hashMapA does not give any clue about its purpose, for example.
• iRohitBhatia: @RolandIllig Thanks for replying, just summarised the summary of my algo. Hope this makes my code more comprehendible
• Blindman67: @iRohitBhatia I am a little busy ATM but will have a look when I get a chance and someone else has not provided a good answer.
• iRohitBhatia: @Blindman67 Cool. Thanks a lot :)

Answer 1

Your code seams massively over complex.

I do not see the need to sort the arrays as the overhead does not warrant the the benefit.

Assigning to the maps in the sort function is very inefficient. The sort function will be called many more times than there are items in the array.

I would say that if (hashMapB.hasOwnProperty(difference)) { is redundant as it can be assumed that objects within the environment of leetcode will not have enumerable properties higher in the prototype chain to worry about. Thus if (hashMapB[difference] !== undefined) would be more performant.

The long variable names makes your code hard to follow. Consider short names and use common abbreviations to reduce the length of lines.

JS will automatically insert semicolons, but there are many situations when the location of the inserted semicolon is not obvious. Inexperienced JS coders should always use semicolons. Experienced coders know its easier to include them.

You don't need to delimit single line statement blocks with {} however it is a source of future bugs when modifying code, as adding the {} can easily be overlooked and very hard to spot. Always delimit all statement blocks. eg if (foo) bar =1 is better as if (foo) { bar = 1 }

The link you provided is not a testable problem, rather it is just a leetcode discussion topic. I have nothing to test on apart from the limited arguments provided in the discussion. There are many question that the set of given inputs do not answer, writing the optimal solution is not possible. The example below is just a brute force solution of complexity \$O(nm)\$ where \$n\$ and \$m\$ are the length of the two input arrays.

Example

Comparing this function against yours and assuming that the values to sum are signed integers (not unsigned as that would allow the inner loop to be skipped if an items had a value greater than the sum (3rd arg)).

The example returns a result in 0.589μs against your functions 25.250μs (μs = 1/1,000,000 second)

I did not test it against very large data sets nor did I look too deeply for a less complex solution.

To avoid creating a new array each time a larger max sum is found I use a counter foundCount as an index of where to put new closer indexes in the result array. When the function is done I just trim the array by setting its length to the found count.

function currentHighest(a, b, max) {
 const lenA = a.length, lenB = b.length, result = [];
 var i = 0, j, foundCount = 0, maxFound = -Infinity;
 while (i < lenA) {
 j = 0;
 const pA = a[i], valA = pA[1];
 while (j < lenB) {
 const pB = b[j], sum = valA + pB[1];
 if (sum <= max && sum >= maxFound) {
 if (sum !== maxFound) { foundCount = 0 } 
 maxFound = sum;
 result[foundCount++] = [pA[0], pB[0]];
 }
 j++;
 }
 i++;
 }
 result.length = foundCount;
 return result;
}