#StackBounty: #javascript #programming-challenge LeetCode heater binary search solution (w recursion) optimisation

Bounty: 50

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?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.