Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Rectangle Area II

Posted on August 18, 2018July 26, 2020 by braindenny

Rectangle Area II



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #rectangle, #linesweep

We are given a list of (axis-aligned) rectangles. Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.

Find the total area covered by all rectangles in the plane. Since the answer may be too large, return it modulo 10^9 + 7.

rectangle_area_ii_pic.png

Example 1:

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: As illustrated in the picture.

Example 2:

Input: [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 = (-7)^2 = 49.

Note:

  • 1 <= rectangles.length <= 200
  • rectanges[i].length = 4
  • 0 <= rectangles[i][j] <= 10^9
  • The total area covered by all rectangles will never exceed 2^63 – 1 and thus will fit in a 64-bit signed integer.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:

General Thinkings:


Key Observations:


Walk Through Testdata


// https://code.dennyzhang.com/rectangle-area-ii

linkedin
github
slack

Post Views: 11
Posted in MediumTagged linesweep, rectangle

Post navigation

LeetCode: Exam Room
LintCode: Char to Integer

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.