Posts tagged as “geometry”

花花酱 LeetCode 959. Regions Cut By Slashes

By zxi on December 18, 2018

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:[  " /",  "/ "]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:[  " /",  "  "]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:[  "\\/",  "/\\"]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)The 2x2 grid is as follows:

Example 4:

Input:[  "/\\",  "\\/"]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)The 2x2 grid is as follows:

Example 5:

Input:[  "//",  "/ "]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

Solution 1: Split grid into 4 triangles and Union Find Faces

Divide each grid into 4 triangles and union them if not split.
Time complexity: O(n^2*alphn(n^2))
Space complexity: O(n^2)

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

DSU dsu(4 * n * n);

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

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

int index = 4 * (r * n + c);

switch (grid[r][c]) {

case '/':

dsu.merge(index + 0, index + 3);

dsu.merge(index + 1, index + 2);

break;

case '\\':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 2, index + 3);

break;

case ' ':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 1, index + 2);

dsu.merge(index + 2, index + 3);

break;

default: break;

}

if (r + 1 < n)

dsu.merge(index + 2, index + 4 * n + 0);

if (c + 1 < n)

dsu.merge(index + 1, index + 4 + 3);

}

int ans = 0;

for (int i = 0; i < 4 * n * n; ++i)

if (dsu.find(i) == i) ++ans;

return ans;

}

private:

class DSU {

public:

DSU(int n): parent_(n) {

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

parent_[i] = i;

}

int find(int x) {

if (parent_[x] != x) parent_[x] = find(parent_[x]);

return parent_[x];

}

void merge(int x, int y) {

parent_[find(x)] = find(y);

}

private:

vector<int> parent_;

};

Solution 2: Euler’s Formula / Union-Find vertices

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

p_ = vector<int>((n + 1) * (n + 1));

// All vertices on the boundaries are merged into root(0).

for (int r = 0; r < n + 1; ++r)

for (int c = 0; c < n + 1; ++c)

p_[getIndex(n, r, c)] = (r == 0 || r == n || c == 0 || c == n) ? 0 : getIndex(n, r, c);

int f = 1;

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

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

if (grid[r][c] == ' ') continue;

// A new face will created if two vertices are already in the same group.

if (grid[r][c] == '/') {

f += merge(getIndex(n, r, c + 1),

getIndex(n, r + 1, c));

} else {

f += merge(getIndex(n, r, c),

getIndex(n, r + 1, c + 1));

}

return f;

}

private:

vector<int> p_;

int getIndex(int n, int r, int c) { return r * (n + 1) + c; }

int find(int x) {

if (p_[x] != x) p_[x] = find(p_[x]);

return p_[x];

}

int merge(int x, int y) {

int rx = find(x);

int ry = find(y);

if (rx == ry) return 1;

p_[ry] = rx;

return 0;

}

};

Solution 3: Pixelation (Upscale 3 times)

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

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

const int n = grid.size();

vector<vector<int>> g(n * 3, vector<int>(n * 3));

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

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

if (grid[i][j] == '/') {

g[i * 3 + 0][j * 3 + 2] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 0] = 1;

} else if (grid[i][j] == '\\') {

g[i * 3 + 0][j * 3 + 0] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 2] = 1;

}

int ans = 0;

for (int i = 0; i < 3 * n; ++i)

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

if (g[i][j]) continue;

visit(g, j, i, n * 3);

++ans;

}

return ans;

}

private:

void visit(vector<vector<int>>& g, int x, int y, int n) {

if (x < 0 || x >= n || y < 0 || y >= n) return;

if (g[y][x]) return;

g[y][x] = 1;

visit(g, x + 1, y, n);

visit(g, x, y + 1, n);

visit(g, x - 1, y, n);

visit(g, x, y - 1, n);

}

};

花花酱 LeetCode 939. Minimum Area Rectangle

By zxi on November 11, 2018

Problem

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Solution 1: HashTable + Brute Force

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua, running time: 96 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_map<int, unordered_set<int>> s;

for (const auto& point : points)

s[point[0]].insert(point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

for (int j = i + 1; j < n; ++j) {

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

if (!s[x1].count(y0) || !s[x0].count(y1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

C++ / 1D hashtable

// Author: Huahua, 68 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_set<int> s;

for (const auto& point : points)

s.insert((point[0] << 16) | point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

for (int j = i + 1; j < n; ++j) {

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

int p0 = (x1 << 16) | y0;

int p1 = (x0 << 16) | y1;

if (!s.count(p0) || !s.count(p1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

花花酱 LeetCode 223. Rectangle Area

By zxi on September 19, 2018

Problem

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Example:

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

Note:

Assume that the total area is never beyond the maximum possible value of int.

Solution:

area1 + area2 – overlapped area

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int area1 = (C - A) * (D - B);

int area2 = (G - E) * (H - F);

int x1 = max(A, E);

int x2 = max(x1, min(C, G));

int y1 = max(B, F);

int y2 = max(y1, min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1);

}

};

Java

// Author: Huahua

class Solution {

public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int area1 = (C - A) * (D - B);

int area2 = (G - E) * (H - F);

int x1 = Math.max(A, E);

int x2 = Math.max(x1, Math.min(C, G));

int y1 = Math.max(B, F);

int y2 = Math.max(y1, Math.min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1);

}

Python3

# Author: Huahua

class Solution:

def computeArea(self, A, B, C, D, E, F, G, H):

area1 = (C - A) * (D - B);

area2 = (G - E) * (H - F);

x1 = max(A, E);

x2 = max(x1, min(C, G));

y1 = max(B, F);

y2 = max(y1, min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1)

花花酱 LeetCode 892. Surface Area of 3D Shapes

By zxi on August 26, 2018

Problem

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

Example 1:

Input: [[2]]
Output: 10

Example 2:

Input: [[1,2],[3,4]]
Output: 34

Example 3:

Input: [[1,0],[0,2]]
Output: 16

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

Note:

1 <= N <= 50
0 <= grid[i][j] <= 50

Solution: Geometry

3D version of 花花酱 LeetCode 463. Island Perimeter

Ans = total faces – hidden faces.

each pile with height h has the surface area of 2 (top/bottom) + 4*h (sides)

\(ans = ans + 2 + 4 * h\)

if a cube has a neighbour, reduce the total surface area by 1

For each pile, we check 4 neighbours, the number of total hidden faces of this pile is sum(min(h, neighbour’s h)).

\(ans = ans – \Sigma min(h, n.h)\)

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

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

static const vector<int> dirs{0, -1, 0, 1, 0};

int m = grid.size();

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

int ans = 0;

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

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

int h = grid[i][j];

if (h == 0) continue;

ans += 2 + 4 * h;

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

int tx = j + dirs[k];

int ty = i + dirs[k + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

int th = grid[ty][tx];

ans -= (th <= 0 ? 0 : min(h, th));

}

return ans;

}

};

C++ (opt)

Since the neighbor relationship is symmetric, we can only consider the top and left neighbors and double the hidden faces.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

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

int m = grid.size();

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

int ans = 0;

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

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

int h = grid[i][j];

if (h == 0) continue;

ans += 2 + 4 * h;

if (i) ans -= 2 * min(h, grid[i - 1][j]);

if (j) ans -= 2 * min(h, grid[i][j - 1]);

}

return ans;

}

};

花花酱 LeetCode 887. Projection Area of 3D Shapes

By zxi on August 4, 2018

Problem

On a N * N grid, we place some 1 * 1 * 1 cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Now we view the projection of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane.

Here, we are viewing the “shadow” when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

Input: [[2]]
Output: 5

Example 2:

Input: [[1,2],[3,4]]
Output: 17
Explanation: 
Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

Example 3:

Input: [[1,0],[0,2]]
Output: 8

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 14

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 21

Note:

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 50

Solution: Brute Force

Sum of max heights for each cols / rows + # of non-zero-height bars.

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time : 4 ms

class Solution {

public:

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

int n = grid.size();

int m = grid[0].size();

int ans = 0;

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

int h = 0;

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

h = max(h, grid[i][j]);

if (grid[i][j] != 0) ++ans;

}

ans += h;

}

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

int h = 0;

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

h = max(h, grid[i][j]);

ans += h;

}

return ans;

}

};