LeetCode in Kotlin

3380. Maximum Area Rectangle With Point Constraints I

Medium

You are given an array points where points[i] = [xi, yi] represents the coordinates of a point on an infinite plane.

Your task is to find the maximum area of a rectangle that:

• Can be formed using four of these points as its corners.
• Does not contain any other point inside or on its border.
• Has its edges parallel to the axes.

Return the maximum area that you can obtain or -1 if no such rectangle is possible.

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,3]]

Output: 4

Explanation:

We can make a rectangle with these 4 points as corners and there is no other point that lies inside or on the border. Hence, the maximum possible area would be 4.

Example 2:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output: -1

Explanation:

There is only one rectangle possible is with points [1,1], [1,3], [3,1] and [3,3] but [2,2] will always lie inside it. Hence, returning -1.

Example 3:

Input: points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,2]]

Output: 2

Explanation:

The maximum area rectangle is formed by the points [1,3], [1,2], [3,2], [3,3], which has an area of 2. Additionally, the points [1,1], [1,2], [3,1], [3,2] also form a valid rectangle with the same area.

Constraints:

• 1 <= points.length <= 10
• points[i].length == 2
• 0 <= xi, yi <= 100
• All the given points are unique.

Solution

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun maxRectangleArea(points: Array<IntArray>): Int {
        val set: MutableSet<String?> = HashSet<String?>()
        for (p in points) {
            set.add(p.contentToString())
        }
        var maxArea = -1
        for (point in points) {
            for (j in 1..<points.size) {
                val p2 = points[j]
                if (point[0] == p2[0] || point[1] == p2[1] || !set.contains(
                        intArrayOf(
                            point[0],
                            p2[1],
                        ).contentToString(),
                    ) || !set.contains(intArrayOf(p2[0], point[1]).contentToString()) ||
                    !validate(points, point, p2)
                ) {
                    continue
                }
                maxArea = max(maxArea, (p2[1] - point[1]) * (p2[0] - point[0]))
            }
        }
        return maxArea
    }

    private fun validate(points: Array<IntArray>, p1: IntArray, p2: IntArray): Boolean {
        val top = max(p1[1], p2[1])
        val bot = min(p1[1], p2[1])
        val left = min(p1[0], p2[0])
        val right = max(p1[0], p2[0])
        for (p in points) {
            val x = p[0]
            val y = p[1]
            if ((y == top || y == bot) && x > left && x < right ||
                (x == left || x == right) && y > bot && y < top ||
                (x > left && x < right && y > bot && y < top)
            ) {
                return false
            }
        }
        return true
    }
}

This site is open source. Improve this page.