Number of Rectangles in a Circle

Time: O(r^2)

Space: O(1)

Intuition

Count axis-aligned rectangles that fit inside a circle of radius r. Enumerate half-widths and compute valid half-heights.

Algorithm

1For each half-width w from 1 to r: max half-height h = floor(sqrt(r^2 - w^2)). Count += h * 4 (all combinations of signs and w/h swap if distinct).

Common Pitfalls

•Count ordered pairs (w,h) with w^2+h^2 <= r^2, w,h >= 1. Each gives distinct rectangle size. Multiply by 4 for all sign combinations.

Number of Rectangles in a Circle.java

Java

// Approach: Count integer pairs (w,h) where diagonal <= r*2 and w,h >= 1 using mathematical approach.
// Time: O(r^2) Space: O(1)
class Solution {
    int rectanglesInCircle(int r) {
        int ans = 0;
        int dia = 2 * r;
        int d2 = 4 * r * r;
        
        for(int i = 1; i < dia; i++)
        {
            int diff = d2 - (i * i);
            ans += Math.sqrt(diff);
        }
        
        return ans;
    }
};

Was this solution helpful?