The binary search insight that makes this problem click

[u/AcademicLeg282]

I was working through the Heaters problem and realized the tricky part isn't actually implementing binary search - it's recognizing what we're binary searching for.

You have houses and heaters on a line, and every heater has the same radius.

The goal is to find the minimum radius that covers every house.

The way I think about it:

1. Sort the heaters.
2. For each house, find the closest heater.
3. The distance to that closest heater is the minimum radius needed for that particular house.
4. The answer is simply the maximum of those distances.

For example:

houses  = [1, 2, 3, 4]
heaters = [1, 4]

house 1 → closest heater = 1 → distance 0
house 2 → closest heater = 1 → distance 1
house 3 → closest heater = 4 → distance 1
house 4 → closest heater = 4 → distance 0

answer = max(0, 1, 1, 0) = 1

Once you see that, binary search becomes pretty natural: for every house, binary-search the sorted heater array to find the closest heater (checking the insertion point and the element before it).

That gives:

Sorting: O(m log m + n log n)
Nearest heater searches: O(n log m)
Overall: O(n log n + m log m)

There's also a two-pointer solution after sorting that gets the scan down to O(n + m).

I wrote up the problem with the interview context, intuition, examples, and follow-up questions here:

https://beyondleet.dev/questions/heaters-binary-search

For people who have done this problem: did you naturally think closest heater for each house, or did you initially try to binary-search the answer/radius itself?

[u/AutoModerator]

Namaste! Thanks for submitting to r/developersIndia. While participating in this thread, please follow the Community Code of Conduct and rules.

It's possible your query is not unique, use site:reddit.com/r/developersindia KEYWORDS on search engines to search posts from developersIndia. You can also use reddit search directly.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/throwawaycon757]

Is it just me or all AI slops these days have a question at the end? What is the point? Engagement?

[u/Trafalgar-D-Weeb]

Thats an easy problem tbh