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
Sort both the arrays and while sorting create an hashMap for A and B
id objects make sure if the specific id is not already been iterated over
current Index is used to track differences and indexes of those difference.
I am starting iteration using while loop, over the sorted array
arr1
We check the difference between the target value and value of current element in
arr1
if the difference exist inhashMapB
we are storing the indexes incurrentHighest
and setting the difference to zeroElse, 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
Creates difference2 which checks if the value exist in hashMap A, if it does, it will do the same thing which we did previously
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
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?
hashMapA
does not give any clue about its purpose, for example. \$\endgroup\$