Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

475. Heaters

Time: $\max(O(m\log m), O(n\log n))$, where $m = |\texttt{houses}|$ and $n = |\texttt{heaters}|$

Space: $O(1)$

			


class Solution {
 public:
  int findRadius(vector<int>& houses, vector<int>& heaters) {
    sort(begin(houses), end(houses));
    sort(begin(heaters), end(heaters));

    int ans = 0;
    int i = 0;  // Point to the heater that currently used

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

    return ans;
  }
};




			


class Solution {
  public int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(houses);
    Arrays.sort(heaters);

    int ans = 0;
    int i = 0; // Point to the heater that currently used

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

    return ans;
  }
}