475

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

        // Find dist of nearest RHS heater.
        for(int i=0, j=0; i<houses.size() && j<heaters.size(); i++){
            if(houses[i] <= heaters[j])
                dist[i] = (heaters[j]-houses[i]);
            else
                j++, i--;
        }

        // Find dist of nearest LHS heater.
        for(int i=houses.size()-1, j=heaters.size()-1; i>=0 && j>=0; i--){
            if(houses[i] >= heaters[j])
                dist[i] = min(dist[i], (houses[i]-heaters[j]));
            else
                j--, i++;
        }
        return *max_element(dist.begin(), dist.end());
    }
};