How do you solve Heaters on LeetCode?

Heaters (LeetCode #475) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Sorting helps in efficiently finding the closest heater for each house.

What is the brute force solution for Heaters?

The brute force approach for Heaters is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each house against every heater to find the minimum radius needed to cover all houses. It’s straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Heaters?

Heaters uses the following concepts: Array, Two Pointers, Binary Search, Sorting. The recommended patterns to study are: Two Pointers, Sorting.

What are the interview tips for Heaters?

Always discuss your thought process and approach before coding. Consider edge cases and constraints early in the problem-solving process. Practice explaining your code as you write it, as this simulates the interview environment.

What are common mistakes when solving Heaters?

Not sorting the arrays before applying the two-pointer technique. Forgetting to handle edge cases, such as when there are no heaters.

#475

Heaters

Medium

ArrayTwo PointersBinary SearchSortingTwo PointersSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

By sorting both the houses and heaters, we can efficiently find the closest heater for each house using a two-pointer technique, significantly reducing the time complexity.

⚙️

Algorithm

4 steps

1Step 1: Sort the houses and heaters arrays.
2Step 2: Use two pointers to traverse both arrays: one for houses and one for heaters.
3Step 3: For each house, find the closest heater and calculate the distance.
4Step 4: Keep track of the maximum distance found, which will be the required radius.

solution.py13 lines

1# Full working Python code
2
3def findRadius(houses, heaters):
4    houses.sort()
5    heaters.sort()
6    radius = 0
7    h = 0
8    for house in houses:
9        while h < len(heaters) - 1 and abs(house - heaters[h]) >= abs(house - heaters[h + 1]):
10            h += 1
11        radius = max(radius, abs(house - heaters[h]))
12    return radius
13

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step, and O(1) for space since we are using a constant amount of extra space.

1Sorting helps in efficiently finding the closest heater for each house.
2Using two pointers reduces unnecessary comparisons, optimizing the search.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.