Skip to content

475. Heaters

  • Time: $\max(O(m\log m), O(n\log n))$, where $m = |\texttt{houses}|$ and $n = |\texttt{heaters}|$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int findRadius(vector<int>& houses, vector<int>& heaters) {
    ranges::sort(houses);
    ranges::sort(heaters);

    int ans = 0;
    int i = 0;  // heaters' index (currently used)

    for (const int house : houses) {
      while (i + 1 < heaters.size() &&
             house - heaters[i] > heaters[i + 1] - house)
        ++i;  // The next heater is better.
      ans = max(ans, abs(heaters[i] - house));
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(houses);
    Arrays.sort(heaters);

    int ans = 0;
    int i = 0; // heaters' index (currently used)

    for (final int house : houses) {
      while (i + 1 < heaters.length && house - heaters[i] > heaters[i + 1] - house)
        ++i; // The next heater is better.
      ans = Math.max(ans, Math.abs(heaters[i] - house));
    }

    return ans;
  }
}