850. Rectangle Area II LeetCode Solution

In this guide, you will get 850. Rectangle Area II LeetCode Solution with the best time and space complexity. The solution to Rectangle Area II 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
Rectangle Area II solution in C++
Rectangle Area II solution in Java
Rectangle Area II solution in Python
Additional Resources

850. Rectangle Area II LeetCode Solution image

Problem Statement of Rectangle Area II

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.
Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.
Return the total area. Since the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

Example 2:

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 1018 modulo (109 + 7), which is 49.

Constraints:

1 <= rectangles.length <= 200
rectanges[i].length == 4
0 <= xi1, yi1, xi2, yi2 <= 109
xi1 <= xi2
yi1 <= yi2
All rectangles have non zero area.

Complexity Analysis

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

850. Rectangle Area II LeetCode Solution in C++

struct Event {
  int x;
  int y1;
  int y2;
  char type;
};

class Solution {
 public:
  int rectangleArea(vector<vector<int>>& rectangles) {
    constexpr int kMod = 1'000'000'007;

    vector<Event> events;

    for (const vector<int>& r : rectangles) {
      events.emplace_back(r[0], r[1], r[3], 's');
      events.emplace_back(r[2], r[1], r[3], 'e');
    }

    ranges::sort(events, ranges::less{},
                 [](const Event& event) { return event.x; });

    long ans = 0;
    int prevX = 0;
    vector<pair<int, int>> yPairs;

    for (const auto& [currX, y1, y2, type] : events) {
      if (currX > prevX) {
        const int width = currX - prevX;
        ans = (ans + width * getHeight(yPairs)) % kMod;
        prevX = currX;
      }
      if (type == 's') {
        yPairs.emplace_back(y1, y2);
        ranges::sort(yPairs);
      } else {  // type == 'e'
        const auto it =
            find(yPairs.begin(), yPairs.end(), pair<int, int>(y1, y2));
        yPairs.erase(it);
      }
    }

    return ans % kMod;
  }

 private:
  long getHeight(const vector<pair<int, int>>& yPairs) {
    int height = 0;
    int prevY = 0;

    for (const auto& [y1, y2] : yPairs) {
      prevY = max(prevY, y1);
      if (y2 > prevY) {
        height += y2 - prevY;
        prevY = y2;
      }
    }

    return height;
  }
};
/* code provided by PROGIEZ */

850. Rectangle Area II LeetCode Solution in Java

class Event {
  public int x;
  public int y1;
  public int y2;
  public char type;
  public Event(int x, int y1, int y2, char type) {
    this.x = x;
    this.y1 = y1;
    this.y2 = y2;
    this.type = type;
  }
}

class Solution {
  public int rectangleArea(int[][] rectangles) {
    final int kMod = 1_000_000_007;
    List<Event> events = new ArrayList<>();

    for (int[] r : rectangles) {
      events.add(new Event(r[0], r[1], r[3], 's'));
      events.add(new Event(r[2], r[1], r[3], 'e'));
    }

    Collections.sort(events, (a, b) -> Integer.compare(a.x, b.x));

    long ans = 0;
    int prevX = 0;
    List<Pair<Integer, Integer>> yPairs = new ArrayList<>();

    for (Event e : events) {
      if (e.x > prevX) {
        final int width = e.x - prevX;
        ans = (ans + width * getHeight(yPairs)) % kMod;
        prevX = e.x;
      }
      if (e.type == 's') {
        yPairs.add(new Pair<>(e.y1, e.y2));
        Collections.sort(yPairs, Comparator.comparing(Pair::getKey));
      } else { // type == 'e'
        yPairs.remove(new Pair<>(e.y1, e.y2));
      }
    }

    return (int) (ans % kMod);
  }

  private long getHeight(List<Pair<Integer, Integer>> yPairs) {
    int height = 0;
    int prevY = 0;

    for (Pair<Integer, Integer> pair : yPairs) {
      final int y1 = pair.getKey();
      final int y2 = pair.getValue();
      prevY = Math.max(prevY, y1);
      if (y2 > prevY) {
        height += y2 - prevY;
        prevY = y2;
      }
    }

    return height;
  }
}
// code provided by PROGIEZ

850. Rectangle Area II LeetCode Solution in Python

class Solution:
  def rectangleArea(self, rectangles: list[list[int]]) -> int:
    events = []

    for x1, y1, x2, y2 in rectangles:
      events.append((x1, y1, y2, 's'))
      events.append((x2, y1, y2, 'e'))

    events.sort(key=lambda x: x[0])

    ans = 0
    prevX = 0
    yPairs = []

    def getHeight(yPairs: list[tuple[int, int]]) -> int:
      height = 0
      prevY = 0

      for y1, y2 in yPairs:
        prevY = max(prevY, y1)
        if y2 > prevY:
          height += y2 - prevY
          prevY = y2

      return height

    for currX, y1, y2, type in events:
      if currX > prevX:
        width = currX - prevX
        ans += width * getHeight(yPairs)
        prevX = currX
      if type == 's':
        yPairs.append((y1, y2))
        yPairs.sort()
      else:  # type == 'e'
        yPairs.remove((y1, y2))

    return ans % (10**9 + 7)
 # code by PROGIEZ