two pointers c++ solution


  • 0
    S

    I feel like binary search route might be a little overkill...

    class Solution {
     public:
     	int findRadius(vector<int>& houses, vector<int>& heaters) {
     		int heaterId = 0;
     		int houseId = 0;
     		int minR = 0;
     
     		sort(houses.begin(), houses.end());
     		sort(heaters.begin(), heaters.end());
     
     		while(houseId < (int) houses.size()) {
     			while(heaterId < (int) heaters.size()-1 &&
     			      houses[houseId] >= heaters[heaterId+1]) {
     				heaterId++;
     			}
     			if(heaterId == (int) heaters.size()-1) {
     				minR = max(abs(houses[houseId] - heaters[heaterId]), minR);
     			} else {
     				minR = max( min(abs(houses[houseId] - heaters[heaterId]), abs(houses[houseId] - heaters[heaterId+1])),
     					    minR);
     			}
     			houseId++;
     
     		}
     		return minR;
     	}
     };

Log in to reply
 

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