Press "Enter" to skip to content

Posts published in “Geometry”

花花酱 LeetCode 1476. Subrectangle Queries

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:

1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

  • Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).

2. getValue(int row, int col)

  • Returns the current value of the coordinate (row,col) from the rectangle.

Example 1:

Input
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
Output

[null,1,null,5,5,null,10,5]

Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4×3) looks like: // 1 2 1 // 4 3 4 // 3 2 1 // 1 1 1 subrectangleQueries.getValue(0, 2); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 subrectangleQueries.getValue(0, 2); // return 5 subrectangleQueries.getValue(3, 1); // return 5 subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 subrectangleQueries.getValue(3, 1); // return 10 subrectangleQueries.getValue(0, 2); // return 5

Example 2:

Input
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
Output

[null,1,null,100,100,null,20]

Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // return 100 subrectangleQueries.getValue(2, 2); // return 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // return 20

Constraints:

  • There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
  • 1 <= rows, cols <= 100
  • rows == rectangle.length
  • cols == rectangle[i].length
  • 0 <= row1 <= row2 < rows
  • 0 <= col1 <= col2 < cols
  • 1 <= newValue, rectangle[i][j] <= 10^9
  • 0 <= row < rows
  • 0 <= col < cols

Solution 1: Simulation

Update the matrix values.

Time complexity:
Update: O(m*n), where m*n is the area of the sub-rectangle.
Query: O(1)

Space complexity: O(rows*cols)

C++

Solution 2: Geometry

For each update remember the region and value.

For each query, find the newest updates that covers the query point. If not found, return the original value in the matrix.

Time complexity:
Update: O(1)
Query: O(|U|), where |U| is the number of updates so far.

Space complexity: O(|U|)

C++

花花酱 LeetCode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCutsSince the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Constraints:

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length < min(h, 10^5)
  • 1 <= verticalCuts.length < min(w, 10^5)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • It is guaranteed that all elements in horizontalCuts are distinct.
  • It is guaranteed that all elements in verticalCuts are distinct.

Solution: Geometry

Find the max gap between vertical cuts mx and max gap between horizontal cuts my. ans = mx * my

Time complexity: O(nlogn)
Space complexity: O(1) if sort in place otherweise O(n)

C++

花花酱 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane. 

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

  • 1 <= points.length <= 100
  • points[i].length == 2
  • -10^4 <= points[i][0], points[i][1] <= 10^4
  • 1 <= r <= 5000

Solution 1: Angular Sweep

See for more details: https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

Time complexity: O(n^2*logn)
Space complexity: O(n^2)

C++

花花酱 LeetCode 1401. Circle and Rectangle Overlapping

Given a circle represented as (radiusx_centery_center) and an axis-aligned rectangle represented as (x1y1x2y2), where (x1y1) are the coordinates of the bottom-left corner, and (x2y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0) 

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Constraints:

  • 1 <= radius <= 2000
  • -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
  • x1 < x2
  • y1 < y2

Solution: Geometry

Find the shortest distance from the center to the rectangle, return dist <= radius.

Time complexity: O(1)
Space complexity: O(1)

C++

花花酱 LeetCode 1272. Remove Interval

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Constraints:

  • 1 <= intervals.length <= 10^4
  • -10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

Solution: Geometry

Time complexity: O(n)
Space complexity: O(n)

C++