Maximum Area Rectangle With Point Constraints I Interview Question for Google

def largest_rectangle_area(points):
    """Finds the largest rectangle area formed by points with no interior points.

    Args:
        points: A list of points, where each point is a list [x, y].

    Returns:
        The maximum area of a valid rectangle, or -1 if none exists.
    """
    n = len(points)
    max_area = -1

    # Brute force: Iterate through all combinations of 4 points
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                for l in range(k + 1, n):
                    # Form a subset of 4 points
                    subset = [points[i], points[j], points[k], points[l]]

                    # Check if these 4 points form a valid rectangle
                    area = is_valid_rectangle(subset, points)
                    if area > 0:
                        max_area = max(max_area, area)

    return max_area


def is_valid_rectangle(subset, all_points):
    """Checks if a subset of 4 points forms a valid rectangle.

    A valid rectangle must:
    1. Have sides parallel to the axes.
    2. Not contain any other points inside or on its border.

    Args:
        subset: A list of 4 points.
        all_points: The list of all available points.

    Returns:
        The area of the rectangle if it is valid, otherwise -1.
    """

    # Check if we have exactly 4 points
    if len(subset) != 4:
        return -1

    # Extract x and y coordinates
    x_coords = [p[0] for p in subset]
    y_coords = [p[1] for p in subset]

    # Check if the points form a rectangle (sides parallel to axes)
    if len(set(x_coords)) != 2 or len(set(y_coords)) != 2:
        return -1

    # Calculate the area of the rectangle
    width = abs(x_coords[0] - x_coords[1])  # Width can be between any two points since there's only 2 unique x coordinates
    height = abs(y_coords[0] - y_coords[1])  # Height can be between any two points since there's only 2 unique y coordinates
    area = width * height

    # Define rectangle boundaries
    min_x = min(x_coords)
    max_x = max(x_coords)
    min_y = min(y_coords)
    max_y = max(y_coords)

    # Check for interior points
    for point in all_points:
        x, y = point

        # Check if point is within the rectangle (excluding corners)
        if (min_x < x < max_x) and (min_y < y < max_y):
            return -1  # Interior point found, not a valid rectangle

        # Check if point is on the border (excluding corners)
        if ((min_x <= x <= max_x) and (y == min_y or y == max_y)) or \
           ((min_y <= y <= max_y) and (x == min_x or x == max_x)):
            if point not in subset:  # Avoid counting corner points as interior
                return -1

    return area



# Example Usage
points1 = [[1, 1], [1, 3], [3, 1], [3, 3]]
print(f"Largest rectangle area for {points1}: {largest_rectangle_area(points1)}")  # Output: 4

points2 = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
print(f"Largest rectangle area for {points2}: {largest_rectangle_area(points2)}")  # Output: -1

points3 = [[1, 1], [1, 3], [3, 1], [3, 3], [1, 2], [3, 2]]
print(f"Largest rectangle area for {points3}: {largest_rectangle_area(points3)}")  # Output: 2

Explanation:

1. largest_rectangle_area(points) Function:

Takes a list of points as input, where each point is a list [x, y]. These represent coordinates on a plane.
Initializes max_area to -1. This will store the maximum rectangle area found so far. If no valid rectangles are found, this value is returned.
Uses four nested loops to iterate through all possible combinations of four points from the input list points. The outer loops iterate through indices i, j, k, and l to select four unique points.
For each combination of four points:
- Creates a subset containing the four selected points.
- Calls the is_valid_rectangle(subset, points) function to check if the subset forms a valid rectangle.
- If is_valid_rectangle returns an area greater than 0 (meaning it's a valid rectangle), the max_area is updated with the maximum of the current max_area and the newly found area.
Returns the max_area. If no valid rectangle is found, it returns -1.

2. is_valid_rectangle(subset, all_points) Function:

Takes a subset (list of four points) and all_points (the complete list of points) as input.
Performs several checks to determine if the subset forms a valid rectangle:
- Checks if the subset contains exactly four points. If not, it returns -1.
- Extracts the x and y coordinates from the points in the subset.
- Checks if the points form a rectangle with sides parallel to the axes. It verifies that there are exactly two unique x-coordinates and two unique y-coordinates.
- Calculates the width and height of the rectangle using the absolute difference between the x and y coordinates.
- Computes the area of the rectangle.
- Determines the rectangle boundaries (min_x, max_x, min_y, max_y).
- Iterates through all points in all_points to check for interior points. For each point:
  - Checks if the point lies strictly inside the rectangle. If so, it returns -1.
  - Checks if the point lies on the border of the rectangle (but is not one of the corners). If a point lies on the border, it returns -1.
If all checks pass, it means the subset forms a valid rectangle, and the function returns the calculated area.

Big O Time Complexity:

The largest_rectangle_area function has four nested loops, each iterating up to n times, where n is the number of points. This contributes a factor of O(n^4).
Inside the loops, the is_valid_rectangle function is called.
The is_valid_rectangle function iterates through all the points, which is O(n).
Therefore, the overall time complexity is O(n^4 * n) = O(n^5).

Big O Space Complexity:

The dominant space usage comes from storing the input points, which requires O(n) space.
The subset variable used in the loops takes up constant space, O(1).
The is_valid_rectangle function uses a few lists for x and y coordinates, but their size is constant (at most 4), so it's O(1).
Therefore, the overall space complexity is O(n).