[LeetCode] Perfect Rectangle

Problem: Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region. Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

Approach: First thing which we can immediately notice that overlapping is not allowed. That means the sum of areas of all the input rectangles should be equal to the area of rectangle which these small rectangles will form.

If you run through many examples on a paper, you will come to know that all the corner points of these input rectangles should appear even number of times except the corner points of the rectangle formed by these small rectangles. The corner points of this large rectangle must come exactly once.

We can validate the corner points which should appear at even number of times using hash but what to do with the corner points which should come exactly once? If you see if these corner points come more than once then it is a overlapping situation and it is already covered by area calculation.

I think now we are ready to go for our implementation!

    

Implementation in C#:

        public bool IsRectangleCover(int[][] rectangles)

        {

            if (rectangles?.Length == 0 || rectangles[0].Length == 0)

            {

                return false;

            }

            int x1 = int.MaxValue;

            int x2 = int.MinValue;

            int y1 = int.MaxValue;

            int y2 = int.MinValue;

            HashSet<string> hash = new HashSet<string>();

            int area = 0;

            foreach(int[] rectangle in rectangles)

            {

                x1 = Math.Min(x1, rectangle[0]);

                y1 = Math.Min(y1, rectangle[1]);

                x2 = Math.Max(x2, rectangle[2]);

                y2 = Math.Max(y2, rectangle[3]);

                area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);

                // All the corner points of current rectangle

                string[] possiblePoints = new string[] 

                { 

                    $"{rectangle[0]},{rectangle[1]}", 

                    $"{rectangle[0]},{rectangle[3]}", 

                    $"{rectangle[2]},{rectangle[1]}", 

                    $"{rectangle[2]},{rectangle[3]}" 

                };

                foreach(string possiblePoint in possiblePoints)

                {

                    if (hash.Contains(possiblePoint))

                    {

                        hash.Remove(possiblePoint);

                    }

                    else

                    {

                        hash.Add(possiblePoint);

                    }

                }

            }

            if (!hash.Contains($"{x1},{y1}")

                || !hash.Contains($"{x1},{y2}")

                || !hash.Contains($"{x2},{y1}")

                || !hash.Contains($"{x2},{y2}")

                || hash.Count != 4)

            {

                return false;

            }

            return area == (x2 - x1) * (y2 - y1);

        }

Complexity: O(n)