algoadvance

Leetcode 475. Heaters

Problem Statement

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to heat 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 all houses could be covered by those heaters.

Example 1:

Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

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 radius 1 standard, then all the houses can be warmed.

Example 3:

Input: houses = [1,5], heaters = [2]
Output: 3

Constraints:

Clarifying Questions

  1. Are there any duplicates in the houses and heaters lists?
    • No, each house and heater has a unique position.
  2. Is the input sorted?
    • No, the input arrays houses and heaters are not sorted, but we can sort them for our approach.
  3. Should we consider the case where no heater can cover any house?
    • That won’t occur under the problem’s constraints, as we are assured that there is at least one heater and one house.

Strategy

  1. Sorting:
    • First, sort both the houses and heaters arrays to simplify the problem.
  2. Finding the nearest heater:
    • For each house, compute the distance to the nearest heater. This can be efficiently determined using a binary search method with upper_bound from the C++ STL (Standard Template Library).
  3. Calculate radius:
    • The radius will be the maximum distance from any house to its nearest heater. This ensures all houses are within the coverage of at least one heater.

Code

Here’s a possible implementation in C++:

#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

int findRadius(std::vector<int>& houses, std::vector<int>& heaters) {
    std::sort(houses.begin(), houses.end());
    std::sort(heaters.begin(), heaters.end());
    
    int radius = 0;
    
    for (int house : houses) {
        int left = 0;
        int right = heaters.size() - 1;
        
        // Binary search to find the position of the smallest heater >= house
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (heaters[mid] < house) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        int dist1 = (left < heaters.size()) ? std::abs(heaters[left] - house) : INT_MAX;
        int dist2 = (right >= 0) ? std::abs(heaters[right] - house) : INT_MAX;
        
        int minDist = std::min(dist1, dist2);
        radius = std::max(radius, minDist);
    }
    
    return radius;
}

Time Complexity

Therefore, the overall time complexity is (O(n \log n + m \log m + n \log m)), which simplifies to (O((n + m) \log (n + m))).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI