CODEWITHSUNDEEP
javaalgorithmoptimization
Ajith Natarajan
Ajith Natarajan

Reputation: 111

How to optimize this solution to avoid exceeding the time limit?

This is my solution to this question:

Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

class Solution {
    public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {

        for(int i=x1; i<=x2; ){
            for(int j=y1; j<=y2; ){                
                System.out.println((Math.pow(i-x_center, 2) +" "+ Math.pow(j-y_center, 2))+" "+Math.pow(radius, 2));
                System.out.println(i+" "+j);
                if((Math.pow(i-x_center, 2)+Math.pow(j-y_center, 2))<=Math.pow(radius, 2)){
                    return true;
                }
                j += 1;
            }
            i += 1;
        }

        return false;
    }
}

I am pretty confident that the logic is correct. Ranging from the bottom left corner of the rectangle to the top right point, for every point, I am checking if it lies inside the circle. If I increase the increment step to anything beyond '1', I see that the code fails for the test cases where the rectangle and circle just 'touch' each other. But having it this way leads to exceeding the time limit in some cases. How do I optimize the code for this logic?

Thanks in advance.

Upvotes: 0

Views: 92

Answers (1)

JunisvaultCo
JunisvaultCo

Reputation: 151

This problem can be simplified. I've found a solution of time complexity O(1) and memory complexity O(1). Instead of checking for every single pixel from the rectangle, you can even only take into consideration the bounds themselves.

As I see it, there are 3 cases:

  1. Circle is fully inside rectangle.
  2. Rectangle is fully inside circle
  3. Circle and rectangle outlines intersect in at least one point. This is the tougher one.

I'll call center of the circle coordinates x0 and y0.

  1. You can simply check the bounding box for the circle, as in, which is the northern most point of the circle(x0,y0-radius), which is the southern-most point of the circle(x0,y0+radius), eastern-most(x0-radius,y0) and western-most(x0+radius,y0). If they all fall within the rectangle, then problem solved.

  2. If a rectangle is fully within a circle, that definitely means that its corners are at a smaller distance from the center of the circle than the radius. Simply check this distance for each corner.

Now comes the hard part.

  1. So, as you have figured out, being in a circle(or intersecting one) means that some point must be at a smaller or equal distance from the center than the radius. However, we can do an optimization for the rectangle checking part, too. Intersection with a rectangle likely means intersection with at least one of the segments that make the outline of the rectangle. So, in the case of an intersection between a rectangle and a circle, you need to check if there is any segment that would be at a smaller or equal distance from the center of the circle than the radius.

Edit: Also, the reason that your code fails on tests where they barely touch is likely due to floating-point errors. Do not use == (or in this case <=, which is similar) for checking if two floating point(or even a floating-point and integer) values are the same. Math.pow() in Java returns double. Just use normal multiplication for squaring. In fact, you might want to stay as far from floating-point as possible, unless you can't figure out how to get rid of them and the problem says "0.001 error is acceptable" or something around the lines. They are both slow and prone to errors.

Edit 2: Also, I've written the code to help you aid in understanding this explanation. I've tested it on the site, it works for every test with runtime 1ms and memory usage 37.7Mb.

class Solution {

    public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        //case 1: circle is fully inside rectangle
        //check the bounding box of the circle against the rectangle
        if(x_center-radius>=x1&&y_center-radius>=y1
         &&x_center+radius<=x2&&y_center+radius<=y2
          )
            return true;
        //case 2: checking closest corner against circle bounds
        int minX=(Math.abs(x_center-x1)>Math.abs(x_center-x2))?(x_center-x2):(x_center-x1);
        int minY=(Math.abs(y_center-y1)>Math.abs(y_center-y2))?(y_center-y2):(y_center-y1);
        if(minX*minX+minY*minY<=radius*radius)
            return true;
        //case 3: checking distances to segments against circle bounds
        //Checking distance from a segment to a point is alike checking
        //the distance from the line the segment is part of to a point,
        //except you have to check if the closest point from the segment
        //is actually on the segment. If it isn't, the distance from a
        //segment to a point is the minimum distance from one of its
        //corners to the point.
        if(x1<=x_center&&x_center<=x2)
            if(minY*minY<=radius*radius)
                return true;
        if(y1<=y_center&&y_center<=y2)
            if(minX*minX<=radius*radius)
                return true;
        return false;
    }
}

This code could be possibly shortened. However, time complexity-wise, it can't get better than O(1).

Upvotes: 1

Related Questions