LeetCode heater binary search solution (w recursion) optimisation

Question

I was doing LeetCode heater problem.

Question: https://leetcode.com/problems/heaters/

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Example Input

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

The solution I wrote is accepted by leetcode but it isn't optimal

Runtime: 656 ms, faster than 39.02% of JavaScript online submissions for Heaters. Memory Usage: 48.2 MB, less than 12.20% of JavaScript online submissions for Heaters.

My solution with comments

function findClosest (house, heaters) {
// if only one heater in array of heaters, subtract it with house number to get the difference and return it 
if (heaters.length === 1) return Math.abs(house - heaters[0]) 
 const middleIndex = Math.floor((heaters.length - 1)/2)
 // if middle heater is equal to house, heater exist on that house number, difference would be zero
 if (house === heaters[middleIndex]) return 0 
 // heater on the leftside and rightside of the middle Heater, if leftside and rightside does not contain any elements (undefinned) then middle would be the left and right most element
 const left = heaters[middleIndex - 1] || heaters[middleIndex] 
 const right = heaters[middleIndex + 1] || heaters[middleIndex]
 // if the left side heater location is greater than current house location, we need to move to left
 if (left > house) { 
 return findClosest(house, heaters.slice(0, middleIndex+1))
 }
 // if the right side heater is less than current house, we need to move to right
 if (house>right) { 
 return findClosest(house, heaters.slice(middleIndex + 1, heaters.length))
 }
 // finding diff b/w left, right and middle index and returning the ones with lease distance
 const middleDiff = Math.abs(house-heaters[middleIndex])
 const leftDiff = house - left 
 const rightDiff = right - house 
 return Math.min(middleDiff, leftDiff, rightDiff)
}
function findRadius (houses, heater) {
 let maxIndex = 0
 houses.sort((a,b) => a-b)
 heater.sort((a,b) => a-b)
 for (let i=0; i<houses.length; i++) {
 const currentIndex = findClosest(houses[i], heater)
 if (currentIndex > maxIndex) maxIndex = currentIndex // if the current returned distance is the highest, set that as maxIndex
 }
 return maxIndex
}

Can someone help me in optimising it?

• Mast: The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly.
• iRohitBhatia: @Mast Sorry, I wasn't able to follow your instruction. where did I go wrong?
• Turksarama: if you read the link, right near the top is says: Titling your question State what your code does in your title, not your main concerns about it. Be descriptive and interesting, and you'll attract more views to your question.
• iRohitBhatia: @Turksarama Sorry for spamming, Can you please let me know if this is any better? Want to understand better way of writing question. Apparently, the other related question also have improper title (probably) -> imgur.com/a/r4yIZx0
• Mast: The status of other questions is irrelevant for determining the quality of your question. When in doubt, see our FAQ on asking questions for guidance.

Answer 1

Performance The main optimization that can be made here is to, while iterating over the sorted houses, to inch along the heaters one-by-one while testing their distance. Increment a heater index only if the difference between the house and the next heater is less than the difference between the house and the current heater. This way, whenever a heater is tested, if the distance between it and the current house has become too great, that heater never gets tested again.

For example, when iterating over 5 houses and 5 heaters, the persistent indicies for each collection being used by the algorithm could look like this:

Indicies being examined:
houses heaters
0 0
1 0
2 0
2 1 // at this point, heater 1 is found to be closer to house 2 than heater 0
2 2 // heater 2 is found to be closer to house 2 than heater 1
3 2
4 2
4 3
4 4
5 4
5 5

And that's it. And, of course, on every iteration, check the distance difference between the heater and the house, and call Math.max on that difference and the current distance record to get the new distance record.

This approach reduces the overall computational complexity from O(n log m) (a binary search for every house) to O(n + m).

function findRadius(houses, heaters) {
 houses.sort((a, b) => a - b);
 heaters.sort((a, b) => a - b);
 // Persistent variable of the current closest heater to the house being iterated over
 let closestHeater = heaters[0];
 // and its index
 let closestHeaterIndex = 0;
 // Current record of needed heater radius
 let requiredRadius = 0;
 for (let i = 0, len = houses.length; i < len; i++) {
 let lastDiff = Math.abs(houses[i] - closestHeater);
 // If we aren't at the end of the heater array,
 // test the next heater to see if we need to increment the heater index:
 while (heaters[closestHeaterIndex + 1]) {
 const nextDiff = Math.abs(heaters[closestHeaterIndex + 1] - houses[i]);
 if (nextDiff > lastDiff) break;
 // This heater is closer to houses[i] than the current one in closestHeater
 lastDiff = nextDiff;
 closestHeaterIndex++;
 closestHeater = heaters[closestHeaterIndex];
 }
 requiredRadius = Math.max(requiredRadius, lastDiff);
 }
 return requiredRadius;
}

Result (screenshot):

Runtime: 88 ms, faster than 98.89% of JavaScript online submissions for Heaters.

Memory Usage: 42.6 MB, less than 5.56% of JavaScript online submissions for Heaters.

A couple other notes regarding your code:

Save array length If performance is an issue (it rarely is except in these competitions), you can save the current length of the array in a for loop in a variable to save a bit of calculations, like I did above:

for (let i = 0, len = houses.length; i < len; i++) {

Branches are expensive Logical branches like if and else are often required, but keep in mind that they generally slow things down more than most other operations:

As a general rule of thumb, branches are slower than straight-line code (on all CPUs, and with all programming languages). -jmrk, V8 developer

If you have a lot of branches, your code may not be as fast as you'd want it to be. Reduce them when possible if performance really is an issue.

Braced blocks create environments - or environment records, which are internal mappings of identifiers to their variable names. If you follow the specification exactly, having such blocks results in a bit more operations being performed. I'm not sure if it's an issue with modern engines, or if they can optimize it away completely, but leaving off { and }s when the block contains only a single statement might make things a smidgen faster. (But on the other hand, leaving off braces arguably makes the code a bit harder to read...)

Use representative variable names You defined the function as

function findRadius (houses, heater) {

but heater is a collection of heaters; seeing heater.sort((a,b) => a-b) confused me at first glance. Best to name collections something plural, probably.