LeetCode 475: Heaters Solution in Python – A Step-by-Step Guide

What Is LeetCode 475: Heaters?

In LeetCode 475: Heaters, you’re given two integer arrays: houses (positions of houses) and heaters (positions of heaters). Your task is to find the minimum radius each heater must have to warm all houses, where a heater at position h with radius r warms houses from h-r to h+r. For example, with houses = [1, 2, 3] and heaters = [2], a radius of 1 works; but with houses = [1, 5] and heaters = [2], you need radius 3. It’s like setting the perfect thermostat range to keep every home toasty.

Problem Statement

• Input: houses (List[int])—house positions; heaters (List[int])—heater positions.
• Output: int—minimum radius to warm all houses.
• Rules:
• Heater at x with radius r warms houses from x-r to x+r.
• All houses must be warmed.
• Positions are non-negative integers.

Constraints

• 1 <= houses.length, heaters.length <= 3 * 10^4.
• 1 <= houses[i], heaters[i] <= 10^9.

Examples to Get Us Started

• Input: houses = [1,2,3], heaters = [2]
• Output: 1 (Heater at 2, radius 1 covers 1-3).
• Input: houses = [1,2,3,4], heaters = [1,4]
• Output: 1 (Radius 1 from 1 and 4 covers all).
• Input: houses = [1,5], heaters = [2]
• Output: 3 (Radius 3 covers 1 and 5).

Understanding the Problem: Warming the Village

To solve LeetCode 475: Heaters in Python, we need to find the smallest radius such that every house is within that distance of at least one heater. A naive approach—checking distances for each house to all heaters—could be O(n * m) (n = houses, m = heaters), slow for 3 * 10^4 each. The key? Sort both arrays and use two pointers or binary search to find the closest heater efficiently. We’ll explore:

• Best Solution (Binary Search with Two-Pointer Optimization): O(n log n + m log m) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Distance Checking): O(n * m) time, O(1) space—simple but slower.

Let’s dive into the binary search solution—it’s the planner’s precise thermostat we need.

Best Solution: Binary Search with Two-Pointer Optimization

Why This Is the Best Solution

The binary search with two-pointer optimization is the top pick because it’s O(n log n + m log m) time (n = houses, m = heaters) and O(1) space, efficiently finding the minimum radius by sorting both arrays and using two pointers to compute the max distance from each house to its closest heater. It avoids redundant distance checks, leveraging sorted order. It’s like setting heaters with a ruler, measuring just the farthest gaps—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Sort houses and heaters.
• Step 2: Use two pointers:
• i for houses, j for heaters.
• For each house, find closest heater (j or j+1).
• Update max radius as min distance to closest heater.
• Step 3: Return max radius found.
• Why It Works:
• Sorted order ensures linear scan finds closest heater.
• Max radius is the largest min-distance to cover all houses.

Step-by-Step Example

Example: houses = [1,2,3], heaters = [2]

• Sort: houses = [1,2,3], heaters = [2].
• Pointers:
• i=0 (1): j=0 (2), dist = |1-2| = 1, max_radius = 1.
• i=1 (2): j=0 (2), dist = 0, max_radius = 1.
• i=2 (3): j=0 (2), dist = |3-2| = 1, max_radius = 1.
• Result: 1.

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

• Sort: houses = [1,2,3,4], heaters = [1,4].
• Pointers:
• i=0 (1): j=0 (1), dist = 0, max_radius = 0.
• i=1 (2): j=0 (1), dist = 1, j=1 (4), dist = 2, min = 1, max_radius = 1.
• i=2 (3): j=0 (1), dist = 2, j=1 (4), dist = 1, min = 1, max_radius = 1.
• i=3 (4): j=1 (4), dist = 0, max_radius = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        # Step 1: Sort both arrays
        houses.sort()
        heaters.sort()

        # Step 2: Two-pointer approach
        max_radius = 0
        i = 0  # House pointer
        j = 0  # Heater pointer

        while i < len(houses):
            # Find distance to current heater
            curr_dist = abs(houses[i] - heaters[j])

            # Check next heater if available
            next_dist = float('inf')
            if j + 1 < len(heaters):
                next_dist = abs(houses[i] - heaters[j + 1])

            # Take min distance to closest heater
            min_dist = min(curr_dist, next_dist)
            max_radius = max(max_radius, min_dist)

            # Move to next house or heater
            if j + 1 < len(heaters) and next_dist <= curr_dist:
                j += 1  # Move to next heater if closer
            else:
                i += 1  # Move to next house

        # Step 3: Return max radius
        return max_radius

• Line 4-5: Sort houses and heaters for linear scan.
• Line 8-11: Initialize pointers and max_radius.
• Line 13-22: For each house:
• Compute distance to current heater (curr_dist).
• Compute distance to next heater (next_dist) if exists.
• Min_dist = closest heater distance.
• Update max_radius with largest min_dist.
• Move j if next heater closer, else move i.
• Line 25: Return max_radius.
• Time Complexity: O(n log n + m log m)—sorting dominates.
• Space Complexity: O(1)—no extra space.

It’s like a heater-tuning maestro!

Alternative Solution: Brute Force Distance Checking

Why an Alternative Approach?

The brute force distance checking method—O(n * m) time, O(1) space—computes the distance from each house to every heater, taking the minimum per house and the maximum overall. It’s slow but intuitive, like measuring every house-to-heater gap with a ruler. Good for small inputs or learning!

How It Works

• Step 1: For each house, find min distance to any heater.
• Step 2: Take max of all min distances.
• Step 3: Return result.

Step-by-Step Example

Example: houses = [1,2,3], heaters = [2]

• House 1: min(|1-2|) = 1.
• House 2: min(|2-2|) = 0.
• House 3: min(|3-2|) = 1.
• Max: 1.
• Result: 1.

Code for Brute Force

Copy codeclass Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        max_radius = 0
        # Step 1: For each house, find min distance
        for house in houses:
            min_dist = float('inf')
            for heater in heaters:
                dist = abs(house - heater)
                min_dist = min(min_dist, dist)
            # Step 2: Update max radius
            max_radius = max(max_radius, min_dist)

        # Step 3: Return result
        return max_radius

• Line 4-10: Compute min distance per house.
• Line 11: Update max_radius.
• Line 14: Return max_radius.
• Time Complexity: O(n * m)—n houses, m heaters.
• Space Complexity: O(1)—minimal space.

It’s a slow heat measurer!

Comparing the Two Solutions

• Binary Search with Two-Pointers (Best):
• Pros: O(n log n + m log m), fast, scalable.
• Cons: Requires sorting logic.
• Brute Force (Alternative):
• Pros: O(n * m), simple.
• Cons: Slower for large inputs.

Binary search wins for efficiency.

Edge Cases and Examples

• Input: houses=[1], heaters=[1] → 0.
• Input: houses=[1,2], heaters=[5] → 4.
• Input: houses=[1], heaters=[1,2] → 0.

Binary search handles all well.

Complexity Recap

• Binary Search: Time O(n log n + m log m), Space O(1).
• Brute Force: Time O(n * m), Space O(1).

Binary search’s the champ.

Key Takeaways

• Binary Search: Sort and scan smartly.
• Brute Force: Measure every gap.
• Python Tip: Sorting speeds up—see [Python Basics](/python/basics).

Final Thoughts: Warm That Village

LeetCode 475: Heaters in Python is a cozy optimization quest. Binary search with two-pointers is your fast thermostat, while brute force is a slow heater checker. Want more optimization? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 410: Split Array Largest Sum. Ready to heat some houses? Head to Solve LeetCode 475 on LeetCode and warm it today—your coding skills are toasty!