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?

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;
}