Day 20 Problem

Hello and welcome back brave human being,

Before we delve into the problem, let me share something your auntie might not say: I'm proud of you! You've persevered through these challenging problems and consistently worked on self-improvement.

On Tuesday we ran our first ad!!!! Making this newsletter more sustainable and allows me to keep on going !! Thank you for your support!!!

Day 20: 475. Heaters

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Let's set an example…

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

Output: 1

Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

Let’s set an example:Let’s dive in 🤿:

First things first, nothing guarantees us that either of these arrays are sorted; therefore, the first step is to sort both!

Now, let’s proceed.

How would you do this with a brute-force approach? How would you find which heater belongs to which house?

If the first answer that pops into your mind is to brute force it with a double loop, you are on the right track.

For each radius, we could iterate and check if all houses are covered. This could potentially result in iterating over all houses and all heaters, which would take us O(n×m) time.

Is there a way we could make it faster?

Now that we have sorted both arrays, we could use binary search!

Do you need a refresher?

So, how could we leverage binary search in this case?

Instead of iterating through all of the heaters, we could use binary search to find the closest heater for each house.

But what does that even mean?

Let’s start slow.

Let’s start by defining our variables.

We need a Left and a Right, a Middle, and the LocalDistance and MinDistance.

The LocalDistance variable holds the distance between the current house and the heater at the Middle index. It represents the distance for the current iteration of the binary search.

The MinDistance variable keeps track of the smallest distance found so far for the given house. It represents the absolute minimum distance to a heater for that house.

L=0 
R=heaters.size()−1
minDistance = INT_MAX

In each iteration of the binary search, we’ll define:

Which would be our stopping condition?

If the minimum distance (minDistance) becomes zero, it means the closest heater has been found, or we are done iterating through the heaters, and our answer is stored in the MinDistance variable.

So for each house, we determine the distance to its nearest heater.

What would we send our helper function?

The house we are searching for a heater, you could send the L and R, or you could define heaters as a global variable.

While searching for the nearest heater for each house, we need to keep track of the largest of these smallest distances. This largest distance will be the minimum radius required to ensure all houses are covered.

Let’s set an example:

Complete solution:

Time Complexity

• Sorting: 𝑂(N log⁡ N+ M log⁡ M ))

• Binary Search for Each House: 𝑂(N log⁡ M)

• Total time complexity: O(N log N + M log M + N log M)

As are approaching the closing of the series what type of content would you like to see next?

Cheers to your success and see you Tuesday,

Denisse