Heaters - Practice Coding Problems

Heaters - Problem

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range. 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.

Notice that all the heaters follow your radius standard, and the warm radius will be the same.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: The only heater is at position 2. House at 1 needs radius 1, house at 2 needs radius 0, house at 3 needs radius 1. Maximum radius needed is 1.

Example 2 — Multiple Heaters

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

› Output: 1

💡 Note: Houses at positions 1 and 4 are covered by heaters. House at 2 is closest to heater at 1 (distance 1), house at 3 is closest to heater at 4 (distance 1). Maximum radius needed is 1.

Example 3 — Single House

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

› Output: 0

💡 Note: The house at position 1 has a heater at the exact same position, so radius 0 is sufficient.

Constraints

1 ≤ houses.length, heaters.length ≤ 3 × 10⁴
1 ≤ houses[i], heaters[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Houses and heaters positioned on a line

Process

Find closest heater for each house

Output

Minimum radius to cover all houses

Key Takeaway

🎯 Key Insight: Find each house's closest heater distance, then take the maximum - this ensures all houses are covered with minimum radius

Asked in

G Google 15 a Amazon 12

The key insight is to find the minimum distance from each house to its closest heater, then return the maximum of these distances. The optimal approach uses binary search after sorting heaters for O(n log m + m log m) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Approach	O(n log n + m log m)	O(1)	Sort both arrays and use two pointers to find closest heater for each house
Brute Force	O(n×m)	O(1)	For each house, find the closest heater by checking all heaters
Binary Search with Sorting	O(n log m + m log m)	O(1)	Sort heaters, then for each house use binary search to find closest heater

Two Pointers Approach — Algorithm Steps

Sort both houses and heaters arrays
Use two pointers to traverse both arrays
For each house, find closest heater and calculate distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Arrays

Both houses and heaters are sorted

Move Pointers

Advance heater pointer to find closest

Calculate

Find distance and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* houses, int housesSize, int* heaters, int heatersSize) {
    qsort(houses, housesSize, sizeof(int), compare);
    qsort(heaters, heatersSize, sizeof(int), compare);
    
    int maxRadius = 0;
    int heaterIdx = 0;
    
    for (int i = 0; i < housesSize; i++) {
        int house = houses[i];
        
        // Move heater pointer to find closest heater
        while (heaterIdx < heatersSize - 1 && 
               abs_val(heaters[heaterIdx + 1] - house) <= abs_val(heaters[heaterIdx] - house)) {
            heaterIdx++;
        }
        
        int distance = abs_val(heaters[heaterIdx] - house);
        maxRadius = max(maxRadius, distance);
    }
    
    return maxRadius;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int houses[1000], heaters[1000];
    int housesSize = 0, heatersSize = 0;
    
    // Parse houses array
    char* token = strtok(line1, "[,]");
    while (token != NULL) {
        houses[housesSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    // Parse heaters array
    token = strtok(line2, "[,]");
    while (token != NULL) {
        heaters[heatersSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(houses, housesSize, heaters, heatersSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log m)

Sorting both arrays dominates the complexity

⚡ Linearithmic

Space Complexity

O(1)

Only using pointer variables, sorting can be done in-place

✓ Linear Space

38.0K Views

Medium Frequency

~25 min Avg. Time

1.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler