Leetcode

Heaters

May 26, 2022 by aAshish

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

C++

 
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;
  }
};

JAVA

 
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;
  }
}