JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
LargestCircle | Reply
After wrecking my brains trying to solve this problem for a while, I decided to try out the solution outlined in the editorial

But this approach doesn't seem to work for me, can anybody please point out the bug in this code:

public int radius(String[] grid)
{
	int height = grid.length;
	int width = grid[0].length();
	int maxRadius = Math.min(height/2, width/2);
	
	for (int r = maxRadius; r >= 1; r--)
		for (int cx = r; cx >= width - r; cx--)
			for (int cy = r; cy >= height - r; cy--)
				for (int x = 0; x < height; x++)
					for (int y = 0; y < width; y++)
					{
						int c1 = Math.abs(cx - x);
						int c2 = Math.abs(cx - x - 1);
						int c3 = Math.abs(cy - y);
						int c4 = Math.abs(cy - y - 1);
							
						int min = Math.min(c1,c2)*Math.min(c1,c2) + Math.min(c3,c4)*Math.min(c3,c4);
						int max = Math.max(c1,c2)*Math.max(c1,c2) + Math.max(c3,c4)*Math.max(c3,c4);
							
						if (min < r && max > r)
							continue;
							
						if (grid[x].charAt(y) == '#')
							return r;
					}					
					
	return 0;
}


Any kind of help will be greatly appreciated.
Re: LargestCircle (response to post by shalinmangar) | Reply
This looks wrong to me:
		for (int cx = r; cx >= width - r; cx--)
			for (int cy = r; cy >= height - r; cy--)

if r<=min(floor(width/2),floor(height/2))
then r<=width/2
and width-r >= r, so you should increment cx, not decrement:
		for (int cx = r; cx <= width - r; cx++)
			for (int cy = r; cy <= height - r; cy++)

Haven't looked at the remainder of the solution...
Re: LargestCircle (response to post by shalinmangar) | Reply
if (min < r && max > r)
should be
if (min >= r*r || max <= r*r )
Re: LargestCircle (response to post by shalinmangar) | Reply
Seven years later! :D
for new users like me :)

class LargestCircle {
public:
	int radius(vector <string>);
};
 
int LargestCircle::radius(vector <string> grid) {
	int height = grid.size();
	int width = grid[0].length();
	int maxRadius = min(height/2, width/2);
	bool flag;
 
	for(int r = maxRadius; r >= 1; r--)
	{
		for(int cx = r; cx <= height - r; cx++)
		{
			for(int cy = r; cy <= width - r; cy++)
			{
				flag = 1;
				for(int x = 0; x < height; x++)
				{
					for(int y = 0; y < width; y++)
					{
						int c1 = abs(cx - x);
						int c2 = abs(cx - x - 1);
						int c3 = abs(cy - y);
						int c4 = abs(cy - y - 1);
							
						int m1 = min(c1,c2)*min(c1,c2) + min(c3,c4)*min(c3,c4);
						int m2 = max(c1,c2)*max(c1,c2) + max(c3,c4)*max(c3,c4);
							
						if (m1 >= r*r || m2 <= r*r)
							continue;
							
						if (grid[x][y] == '#')
						{
							flag = 0;
							goto A;
						}
					}
				}	
				if(flag == 1)
						return r;
				A:; 
			}
		}
	}
	return 0;
}
Re: LargestCircle (response to post by ImanAkbari) | Reply
Another five years later!
I was able to solve this problem, not in O(n^^4) time, but in just above O(n) time. Please see my solution on my github site and provide feedback:
https://github.com/stevenlinzer/InterviewPractice
Thank you.
RSS