Skip to content

475.heaters.md

Latest commit

 

History

History
269 lines (225 loc) · 10.3 KB

475.heaters.md

File metadata and controls

269 lines (225 loc) · 10.3 KB

475. Heaters

Test Cases

Edge / Corner Cases

  • All the houses are left to the first heater. The last house < the first heater:
            h1 h2   h3  // houses
*  *    *               // heaters
  • (Reverse the above case) All the heater are left to the first house. The last heater < the first house:
h1 h2   h3              // heaters
              *     * * // houses

Key Insights

Idea!! To find the minimum required distance to cover all houses, we always find the cloest heater for each house. (Greedy). Then question becomes how to find the closest heater for each house efficiently.

For each house, we can find the minimum distance of the "previous" and "next" closest heater that can cover it. The answer is the maximum of all minimum distances.

取最小值是因為我們要確保每個房子被最近的加熱器覆蓋，這樣才能保證半徑最小。至於最終答案取最大值，是因為我們要找到覆蓋所有房子的最小半徑，這個半徑必須足夠大以覆蓋最遠的房子。

     h1,       h2,         h3
*     |  *      |   *       |
|-----^--|------^---|-------^
  10    5   15    7    20

distance(h1) = min(10, 5) = 5
distance(h2) = min(15, 7) = 7
distance(h3) = min(20)    = 20

ans = 20

Pay attention: We should use heaters[i] and houses[i] which is the actual position to calculate the distance, not the index i itself.

Binary Search

We can sort the heaters so that we can use binary search to find the closest heater for each house.

对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离。

遍历所有 houses[i]，记录其位置 pos，在有序的 heaters 序列里找到第一个大于（等于）pos的迭代器元素 it，判断 it和 it-1 与 pos 的距离，较小值就是该 house[i] 的最小供暖半径。

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
   *        H                  *
   |---3----|--------6---------|
heaterA                     heaterB
  • Previous closest heater: Binary search the last heater <= house[i].
O, O, O, O, X, X, X
         ^    
               House
  • Next closest heater: Binary search the first heater >= house[i].
X, X, X, X, O, O, O
            ^        
  House

Furthermore, we also have to handle the corner cases (see above):

They are optinal, it can be covered by above bineary search approach.

  • The last house < the first heater: heater[0] - house[i]
h1  h2                      // houses
^   ^ |---------|
                *      *    // heaters
  • The last heater < the first house (reverse the above case): house[i] - heater[n - 1] (n is the size of the heaters array)
                h1  h2  // houses
     |---------| ^   ^
*    *                  // heaters
fun findRadius(houses: IntArray, heaters: IntArray): Int {
    heaters.sort()
    var minRadius = 0
    for (i in 0 until houses.size) {
        // (Optional) We can short-circuit the distance calculation if the house
        // is on the left of the first heater or on the right of the last heater.
        val distance = if (houses[i] <= heaters.first()) {
            heaters.first() - houses[i]
        } else if (heaters.last <= houses[i]) {
            houses[i] - heaters.last()
        } else {
            // The key part, find the previous and next closest heater for the house.
            val previousDistance = searchPreviousHeater(heaters, houses[i])
            val nextDistance = searchNextHeater(heaters, houses[i])
            minOf(previousDistance, nextDistance)
        }
        minRadius = maxOf(minRadius, distance)
    }
    return minRadius
}

// find previous heater, binary search the last heater <= num
// 1, 3, *5      8, 9
// O  O   O      X  X
//           6
private fun searchPreviousHeater(heaters: IntArray, house: Int): Int {
    var left = 0
    var right = heaters.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (heaters[middle] > house) {
            right = middle - 1
        } else if (heaters[middle] < house) {
            left = middle + 1
        } else {
            left = middle + 1
        }
    }
    return if (right in 0 until heaters.size) (house - heaters[right]) else Int.MAX_VALUE
}

// find next heater, binary search the first heater >= num
// 1, 3, 5      *8, 9
// X  X  X       O  O
//          6
private fun searchNextHeater(heaters: IntArray, house: Int): Int {
    var left = 0
    var right = heaters.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (heaters[middle] > house) {
            right = middle - 1
        } else if (heaters[middle] < house) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return if (left in 0 until heaters.size) (heaters[left] - house) else Int.MAX_VALUE
}
  • Time Complexity: O((n * log n + m * log n) where n is the size of the heaters array and m is the size of the houses array:
    • O(n * log n) for sorting the heaters array.
    • O(m * log n) for binary search the closest heater for each house.
  • Space Complexity: O(log n) for sorting.

WA

fun findRadius(houses: IntArray, heaters: IntArray): Int {
    // We should check the heaters size, not houses size, it's used to access the heaters[i] after binary search.
    val n = houses.size 
    heaters.sort()
    var radius = 0
    for (house in houses) {
        // search left closest
        val leftIndex = lowerBound(house, heaters)
        // search right closest
        val rightIndex = upperBound(house, heaters)

        // There are two mistakes:
        // We don't use the last or first heater if we can't find the left or right closest heater.
        // If we use Int.MAX_VALUE, then we should calculate the distance here, not below.

        // Correct: 
        // val left = if (leftIndex in 0 until n) house - heaters[leftIndex] else Int.MAX_VALUE
        // val right = if (rightIndex in 0 until n) heaters[rightIndex] - house else Int.MAX_VALUE
        // val requiredRadius = minOf(left, right)

        val left = if (leftIndex in 0 until n) heaters[leftIndex] else heaters.last()
        val right = if (rightIndex in 0 until n) heaters[rightIndex] else heaters.first()

        // calculate the minimum of the two distances
        val requiredRadius = minOf(house - left, right - house)

        // update the global maximum of radius
        radius = maxOf(radius, requiredRadius)
    }
    return radius
}

Two Pointers

As the houses increase in coordinate value, the "nearest heater" also only moves to the right. We never need to move the heater pointer backward.

We can also solve this problem using two pointers. The key idea is the same as the binary search approach. We try to locate the next closest heater for each house first, then find the previous closest heater by minus one (if exist or not out of bound) from the next closest heater.

We sort the houses and heaters array first, so that we can iterate each house in order and then find the previous and next closest heater for it.

Q: Why sort?

  1. Sorint heaters: This allows us to say, "If I'm at houses[j], the only potential better heater is the next one heaters[j + 1].", Without sorting, the nearest heater could be anywhere in the array, focusing us to re-check every heater again.
  2. Sorting houses: If houses are sorted, then as we move from house A to B (A < B), the nearest heater for house B cannot be the previous nearest heater for house A. Because both are sorted, we only move the pointers forward. We never "look back", that's why this approach is so efficient.
         A             B
-------- 8 ---------- 16 -------> // Houses
   ^           ^          ^
   a           b          c       // Heaters

Heaters a and b are the previous and next closest heaters for house A, as we move to house B, it's impossible for heater a to be the nearest heater for house B. Heater a is natually even further away from house B than heater b.

First we locate the next closest heater of houses[i]:

// Move to the closest next heatzers heaters[j] <= houses[i]
houses               7       10
heaters  1 2    5    7 
         j --------> j'

houses               7       10
heaters  1 2    5       8 
         j -----------> j'

Then the current j and previous position j - 1 of the heater can be the previous and next closest heater for the house. We calculate the minimum distance from the previous and next heaters, and update the answer.

houses              h1,      h2
                    i
heaters  * *    *       * 
                        j   (next heater)
                ^ 
                j - 1  (previous heater)

Please note that it's necessary to handle the two corner cases explicitly to avoid out of bound when accessing the heaters[j].

fun findRadius(houses: IntArray, heaters: IntArray): Int {
    val m = houses.size
    val n = heaters.size
    houses.sort()
    heaters.sort()

    var minRadius = 0
    var j = 0 // heater index
    for (i in 0 until m) {
        // We move to the closest "next" heater (e.g. house[i] <= heaters[j]).
        while (j < n && heaters[j] < houses[i]) j++

        // My mistake: This only locates the last heater that heaters[j] < house[i].
        // while (j + 1 < n && heaters[j + 1] <= houses[i]) j++

        val distance = if (j == 0) { // Corner case 1: (all houses) ... heaters[0]
            heaters.first() - houses[i]
        } else if (j == n) { // Corner case 2: (all heaters) ... houses[0]
            houses[i] - heaters.last()
        } else {
            // We do have previous and next heaters.
            val previousDistance = houses[i] - heaters[j - 1]
            val nextDistance = heaters[j] - houses[i]
            minOf(previousDistance, nextDistance)
        }
        minRadius = maxOf(minRadius, distance)
    }
    
    return minRadius
}
  • Time Complexity: O(n * log n + m * log m + (m + n)) = O(n log n + m * log m) where n is the size of the heaters array and m is the size of the houses array:
    • O(n * log n) for sorting the heaters array.
    • O(m * log m) for sorting the houses array.
  • Space Complexity: O(log n + log m) for sorting.