Posts published in “Geometry”

花花酱 LeetCode 2249. Count Lattice Points Inside a Circle

By zxi on April 27, 2022

Given a 2D integer array circles where circles[i] = [x_i, y_i, r_i] represents the center (x_i, y_i) and radius r_i of the i^th circle drawn on a grid, return the number of lattice points that are present inside at least one circle.

Note:

A lattice point is a point with integer coordinates.
Points that lie on the circumference of a circle are also considered to be inside it.

Example 1:

Input: circles = [[2,2,1]]
Output: 5
Explanation:
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.

Example 2:

Input: circles = [[2,2,2],[3,4,1]]
Output: 16
Explanation:
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).

Constraints:

1 <= circles.length <= 200
circles[i].length == 3
1 <= x_i, y_i <= 100
1 <= r_i <= min(x_i, y_i)

Solution: Brute Force

Time complexity: O(m * m * n) = O(200 * 200 * 200)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countLatticePoints(vector<vector<int>>& circles) {

auto isIn = [](int u, int v, int x, int y, int r) {

return (u - x) * (u - x) + (v - y) * (v - y) <= r * r;

};

int ans = 0;

for (int u = 0; u <= 200; ++u)

for (int v = 0; v <= 200; ++v) {

bool found = false;

for (const auto& c : circles)

if (isIn(u, v, c[0], c[1], c[2])) {

found = true;

break;

}

ans += found;

}

return ans;

}

};

花花酱 LeetCode 1232. Check If It Is a Straight Line

By zxi on December 23, 2021

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Constraints:

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates contains no duplicate point.

Solution: Slope and Hashset

This is not a easy problem, a few corner cases:

dx == 0
dy == 0
dx < 0

Basically we are counting (dx / gcd(dx, dy), dy / gcd(dx, dy)). We will have only ONE entry if all the points are on the same line.

Time complexity: O(n)
Space complexity: O(1) w/ early exit.

C++

// Author: Huahua

class Solution {

public:

bool checkStraightLine(vector<vector<int>>& coordinates) {

set<pair<int, int>> s;

for (int i = 1; i < coordinates.size(); ++i) {

int dx = coordinates[i][0] - coordinates[0][0];

int dy = coordinates[i][1] - coordinates[0][1];

if (dy == 0)

s.emplace(1, 0);

else if (dx == 0)

s.emplace(0, 1);

else {

if (dx < 0) dx *= -1, dy *= -1;

const int d = gcd(dx, dy);

s.emplace(dx / d, dy / d);

}

if (s.size() > 1) return false;

}

return true;

}

};

花花酱 LeetCode 1895. Largest Magic Square

By zxi on August 9, 2021

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

Example 1:

Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Output: 3
Explanation: The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12

Example 2:

Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁶

Solution: Brute Force w/ Prefix Sum

Compute the prefix sum for each row and each column.

And check all possible squares.

Time complexity: O(m*n*min(m,n)²)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int largestMagicSquare(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<vector<int>> rows(m, vector<int>(n + 1));

vector<vector<int>> cols(n, vector<int>(m + 1));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

rows[i][j + 1] = rows[i][j] + grid[i][j];

cols[j][i + 1] = cols[j][i] + grid[i][j];

}

for (int k = min(m, n); k >= 2; --k)

for (int i = 0; i + k <= m; ++i)

for (int j = 0; j + k <= n; ++j) {

vector<int> s;

for (int r = 0; r < k; ++r)

s.push_back(rows[i + r][j + k] - rows[i + r][j]);

for (int c = 0; c < k; ++c)

s.push_back(cols[j + c][i + k] - cols[j + c][i]);

int d1 = 0;

int d2 = 0;

for (int d = 0; d < k; ++d) {

d1 += grid[i + d][j + d];

d2 += grid[i + d][j + k - d - 1];

}

s.push_back(d1);

s.push_back(d2);

if (count(begin(s), end(s), s[0]) == s.size()) return k;

}

return 1;

}

};

花花酱 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid

By zxi on August 6, 2021

You are given an m x n integer matrix grid.

A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:

Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.

Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

Example 1:

Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
Output: [228,216,211]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 20 + 3 + 200 + 5 = 228
- Red: 200 + 2 + 10 + 4 = 216
- Green: 5 + 200 + 4 + 2 = 211

Example 2:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [20,9,8]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 4 + 2 + 6 + 8 = 20
- Red: 9 (area 0 rhombus in the bottom right corner)
- Green: 8 (area 0 rhombus in the bottom middle)

Example 3:

Input: grid = [[7,7,7]]
Output: [7]
Explanation: All three possible rhombus sums are the same, so return [7].

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁵

Solution: Brute Force

Just find all Rhombus…

Time complexity: O(mn*min(n,m)²)
Space complexity: O(mn*min(n,m)²)

C++

// Author: Huahua

class Solution {

public:

vector<int> getBiggestThree(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> ans;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

ans.push_back(grid[i][j]);

for (int a = 2; a <= min(m, n); ++a)

for (int cy = a - 1; cy + a <= m; ++cy)

for (int cx = a - 1; cx + a <= n; ++cx) {

int s = grid[cy][cx - a + 1]

+ grid[cy][cx + a - 1]

+ grid[cy + a - 1][cx]

+ grid[cy - a + 1][cx];

for (int i = 1; i < a - 1; ++i)

s += grid[cy - i][cx - a + i + 1]

+ grid[cy - i][cx + a - i - 1]

+ grid[cy + i][cx - a + i + 1]

+ grid[cy + i][cx + a - i - 1];

ans.push_back(s);

}

sort(rbegin(ans), rend(ans));

vector<int> output;

for (int x : ans) {

if (output.empty() || output.back() != x)

output.push_back(x);

if (output.size() == 3) break;

}

return output;

}

};

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

By zxi on April 17, 2021

You are given an array points where points[i] = [x_i, y_i] is the coordinates of the i^th point on a 2D plane. Multiple points can have the same coordinates.

You are also given an array queries where queries[j] = [x_j, y_j, r_j] describes a circle centered at (x_j, y_j) with a radius of r_j.

For each query queries[j], compute the number of points inside the j^th circle. Points on the border of the circle are considered inside.

Return an array answer, where answer[j] is the answer to the j^th query.

Example 1:

Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
Output: [3,2,2]
Explanation: The points and circles are shown above.
queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.

Example 2:

Input: points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
Output: [2,3,2,4]
Explanation: The points and circles are shown above.
queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.

Constraints:

1 <= points.length <= 500
points[i].length == 2
0 <= x_i, y_i <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= x_j, y_j <= 500
1 <= r_j <= 500
All coordinates are integers.

Solution: Brute Force

Time complexity: O(P * Q)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {

vector<int> ans;

ans.reserve(queries.size());

for (const auto& q : queries) {

const int rs = q[2] * q[2];

int cnt = 0;

for (const auto& p : points)

if ((q[0] - p[0]) * (q[0] - p[0]) +

(q[1] - p[1]) * (q[1] - p[1]) <= rs)

++cnt;

ans.push_back(cnt);

}

return ans;

}

};