C++ 2 pointers solution with detailed explanation


  • 0
    K

    I solved the problem with 2 pointers, following is the explanation:
    First we need to sort both arrays.
    Say that the H1 is the array of the houses and H2 is the array of the heaters. and we let m be the number of houses and n be the number of heaters.

    Now we scan the two arrays from left to right, using i as the current index of H1 and j as of H2 respectively, and r be the minium radius needed.

    We first set i,j,r to 0. Just take H1[i] as the first unknown house, and H2[j] is the last heater we've seen.

    When we meet H1[i], we first check if the current heater H2[j] with current minimum radius r can warm it.

    If 'yes', known houses are increased by 1, we move to the next house. If 'no', we keep increasing j until we find out what is the nearst heater to H1[i].

    Note here that current heater can be the nearest heater to H1[i]. Also note that during 'find out the nearst heater to H1[i]', heaters before current heater j, that is, H2[0,j-1],
    will not be the nearest one so we don't need to consider them.

    Finally when we find it, we can then decide whether increasing the minimum radius is necessary.

    This procedure goes on until all houses are warmed.

    So we claim the following loop invariant,
    1, H1[i] is the next house that if its warmed is unknown.
    2, H2[j] is the last heater examined.
    3, r is the minimum radius after each iteration
    ( In short, 1+2 is saying that houses from [0,i) is covered by heaters from [0,j] )

    Following is the pseudo-code and the analysis of loop invariant

    HEATERS(H1,m,H2,n)
        let i,j,r=0
        for(i = 0 to m-1)
            if(H1[i] is covered by H2[j])
                continue;
            else
                j <- Find nearest heater for H1[i]
                if( H1[i] is within H2[j] +- r )
                    continue
                else
                    r = abs(H1[i] - H2[j])
        return r
    

    Init: Before the first iteration, [0,i) is empty and [0,j] is the first heater.
    we have no houses to cover, so r=0 satisfies. The loop invariant 1,2,3 holds.

    Loop: When a new house H1[i] comes insight, we first check if it's covered already. If not, we start to look for the closest heater to it, and note down its index, j.
    Then we check if current radius is enough for it to cover the new house. If not, we are forced to increase r. So at the end of iteration, we update i,j,r correctly and only when necessary.
    So we feel assured that the loop invariant holds.

    Term: All houses are covered because we have iterated through all of them.

    C++ code is as below.

    class Solution {
    public:
    	int findRadius(vector<int>& houses, vector<int>& heaters) {
    		int len1 = houses.size();
    		int len2 = heaters.size();
    		sort(houses.begin(), houses.end());
    		sort(heaters.begin(), heaters.end());
    		int j = 0;
    		int r = 0;
    		for (int i = 0; i < len1; ++i)
    		{
    			if (heaters[j] + r >= houses[i] && heaters[j] - r <= houses[i])
    				continue;
    			else
    			{
    				int delta = abs(houses[i] - heaters[j]);
    				for (++j; j < len2; ++j)
    				{
    					int newDelta = abs(houses[i] - heaters[j]);
    					if (newDelta <= delta)
    					{
    						delta = newDelta;
    					}
    					else
    					{		
    						break;
    					}
    				}
    				//j-1 is the closest heater to current house.
    				//Note that we can do a small optimization here if we have reached the last heater (by checking if j == len2) but there're still unknown houses - 
    				// we have to use this heater for all the remaining houses.
    				--j;
    				r = max(r, delta);
    			}
    		}
    		return r;
    	}
    };
    
    
    
    

Log in to reply
 

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