3380. Maximum Area Rectangle With Point Constraints I LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3380. Maximum Area Rectangle With Point Constraints I LeetCode Solution with the best time and space complexity. The solution to Maximum Area Rectangle With Point Constraints I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Area Rectangle With Point Constraints I solution in C++
Maximum Area Rectangle With Point Constraints I solution in Java
Maximum Area Rectangle With Point Constraints I solution in Python
Additional Resources

3380. Maximum Area Rectangle With Point Constraints I LeetCode Solution image

Problem Statement of Maximum Area Rectangle With Point Constraints I

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.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

3380. Maximum Area Rectangle With Point Constraints I LeetCode Solution in C++

class SegmentTree {
 public:
  explicit SegmentTree(int n, int kInf) : kInf(kInf), n(n), tree(4 * n, kInf) {}

  // Updates nums[i] to val.
  void update(int i, int val) {
    update(0, 0, n - 1, i, val);
  }

  // Returns min(nums[i..j]).
  int query(int i, int j) const {
    return query(0, 0, n - 1, i, j);
  }

 private:
  const int kInf;    // the invalid value
  const int n;       // the size of the input array
  vector<int> tree;  // the segment tree

  void update(int treeIndex, int lo, int hi, int i, int val) {
    if (lo == hi) {
      tree[treeIndex] = val;
      return;
    }
    const int mid = (lo + hi) / 2;
    if (i <= mid)
      update(2 * treeIndex + 1, lo, mid, i, val);
    else
      update(2 * treeIndex + 2, mid + 1, hi, i, val);
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
  }

  int query(int treeIndex, int lo, int hi, int i, int j) const {
    if (i <= lo && hi <= j)  // [lo, hi] lies completely inside [i, j].
      return tree[treeIndex];
    if (j < lo || hi < i)  // [lo, hi] lies completely outside [i, j].
      return kInf;
    const int mid = (lo + hi) / 2;
    return merge(query(treeIndex * 2 + 1, lo, mid, i, j),
                 query(treeIndex * 2 + 2, mid + 1, hi, i, j));
  }

  int merge(int left, int right) const {
    return max(left, right);
  }
};

class Solution {
 public:
  int maxRectangleArea(vector<vector<int>>& points) {
    int ans = -1;
    ranges::sort(points);
    const vector<int> ys = getUniqueAndSortedYs(points);
    SegmentTree tree(ys.size(), /*kInf=*/-1);
    unordered_map<int, int> yToIndex;
    unordered_map<int, int> yToX;

    for (int i = 0; i < ys.size(); ++i)
      yToIndex[ys[i]] = i;

    int prevX = points[0][0];
    int prevY = points[0][1];

    for (int i = 1; i < points.size(); ++i) {
      const int x = points[i][0];
      const int y = points[i][1];
      if (yToX.contains(prevY) && yToX.contains(y)) {
        const int xLeft = yToX[y];
        if (prevX == x && yToX[prevY] == xLeft &&
            xLeft > tree.query(yToIndex[prevY] + 1, yToIndex[y] - 1))
          ans = max(ans, (y - prevY) * (x - xLeft));
      }
      yToX[prevY] = prevX;
      tree.update(yToIndex[prevY], prevX);
      prevX = x;
      prevY = y;
    }

    return ans;
  }

 private:
  vector<int> getUniqueAndSortedYs(const vector<vector<int>>& points) {
    vector<int> ys;
    for (const vector<int>& point : points)
      ys.push_back(point[1]);
    ranges::sort(ys);
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    return ys;
  }
};
/* code provided by PROGIEZ */

3380. Maximum Area Rectangle With Point Constraints I LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3380. Maximum Area Rectangle With Point Constraints I LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents