5-line solution directly using std::lower_bound for binary search (detailed explanation with picture illustration)


  • 2

    Key observation: Each house should be covered by its nearest heater. The nearest heater to a house is either next right to it or next left to it, whichever is closer.

    Algorithm:

    1. Sort heaters vector<int> hts by positions (O(NheaterlogNheater));
    2. For each house h, use std::lower_bound to find the nearest heater and update the overall min heater radius (O(logNheater) for each house). Note
      • Next right heater position: i = lower_bound(hts.begin(), hts.end(), h).
      • Next left heater position: --i for the iterator above .

    The overall time complexity is O((Nhouse+Nheater)logNheater).
    0_1481520322846_heaters.JPG

        int findRadius(vector<int>& houses, vector<int>& hts) {
          sort(hts.begin(), hts.end()); int res = 0; 
          for (int h:houses) { // find nearest distance to heaters
            auto i = lower_bound(hts.begin(), hts.end(), h); // next right heater
            res = max(res, min(i!=hts.begin()? h-*(--i):INT_MAX, i!=hts.end()? *i - h:INT_MAX));
          }
          return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.