Posts published in “Geometry”

花花酱 LeetCode 1272. Remove Interval

By zxi on November 30, 2019

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++

// Author: Huahua

class Solution {

public:

vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& r) {

vector<vector<int>> ans;

for (const auto& i : intervals)

// Does not intersect

if (i[1] <= r[0] || i[0] >= r[1])

ans.push_back(i);

else {

// i starts first

if (i[0] < r[0])

ans.push_back({i[0], r[0]});

// i ends later

if (i[1] > r[1])

ans.push_back({r[1], i[1]});

}

return ans;

}

};

花花酱 LeetCode 1138. Alphabet Board Path

By zxi on July 27, 2019

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

We may make the following moves:

'U' moves our position up one row, if the square exists;
'D' moves our position down one row, if the square exists;
'L' moves our position left one column, if the square exists;
'R' moves our position right one column, if the square exists;
'!' adds the character board[r][c] at our current position (r, c) to the answer.

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

1 <= target.length <= 100
target consists only of English lowercase letters.

Solution: Manhattan walk

Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way.
Be aware of the last row, we can only walk on ‘z’, so go left and up first if needed.

Time complexity: O(26*26 + n)
Space complexity: O(26*26)

C++

// Author: Huahua

class Solution {

public:

string alphabetBoardPath(string target) {

vector<vector<string>> paths(26, vector<string>(26));

for (int s = 0; s < 26; ++s)

for (int t = 0; t < 26; ++t) {

int dx = t % 5 - s % 5;

int dy = t / 5 - s / 5;

string path;

while (dx < 0) { path.push_back('L'); dx++; }

while (dy < 0) { path.push_back('U'); dy++; }

while (dx > 0) { path.push_back('R'); dx--; }

while (dy > 0) { path.push_back('D'); dy--; }

paths[s][t] = path;

}

char l = 'a';

string ans;

for (char c : target) {

ans += paths[l - 'a'][c - 'a'] + "!";

l = c;

}

return ans;

}

};

花花酱 LeetCode 391. Perfect Rectangle

By zxi on July 11, 2019

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[3,2,4,4],

[1,3,2,4],

[2,3,3,4]

]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [

[1,1,2,3],

[1,3,2,4],

[3,1,4,2],

[3,2,4,4]

]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[1,3,2,4],

[3,2,4,4]

]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[1,3,2,4],

[2,2,4,4]

]

Return false. Because two of the rectangles overlap with each other.

Solution: Counting corner points

C++

// Author: Huahua

class Solution {

public:

bool isRectangleCover(vector<vector<int>>& rectangles) {

set<pair<int, int>> corners;

int area = 0;

for (const auto& rect : rectangles) {

pair<int, int> p1{rect[0], rect[1]};

pair<int, int> p2{rect[2], rect[1]};

pair<int, int> p3{rect[2], rect[3]};

pair<int, int> p4{rect[0], rect[3]};

for (const auto& p : {p1, p2, p3, p4}) {

const auto& ret = corners.insert(p);

if (!ret.second) corners.erase(ret.first);

}

area += (p3.first - p1.first) * (p3.second - p1.second);

}

if (corners.size() != 4) return false;

const auto& p1 = *begin(corners);

const auto& p3 = *rbegin(corners);

return area == (p3.first - p1.first) * (p3.second - p1.second);

}

};

花花酱 LeetCode 986. Interval List Intersections

By zxi on February 2, 2019

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solution: Two pointers

Time complexity: O(m + n)
Space complexity: O(1)

C++

// Author: Huahua, running time: 36 ms, 925.7 KB

class Solution {

public:

vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {

size_t i = 0;

size_t j = 0;

vector<Interval> ans;

while (i < A.size() && j < B.size()) {

const int s = max(A[i].start, B[j].start);

const int e = min(A[i].end, B[j].end);

if (s <= e) ans.emplace_back(s, e);

if (A[i].end < B[j].end)

++i;

else

++j;

}

return ans;

}

};

Python3

# Author: Huahua, running time: 96 ms, 7.6 MB

class Solution:

def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]':

i, j, ans = 0, 0, []

while i < len(A) and j < len(B):

s = max(A[i].start, B[j].start)

e = min(A[i].end, B[j].end)

if s <= e:

ans.append(Interval(s, e))

if A[i].end < B[j].end:

i += 1

else:

j += 1

return ans

花花酱 LeetCode 973. K Closest Points to Origin

By zxi on January 13, 2019

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 
Output: [[-2,2]] 
Explanation:  The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 
Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Solution: Sort

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

C++

// Author: Huahua, Running time: 180 ms

class Solution {

public:

vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {

vector<long> s(points.size());

for (int i = 0; i < points.size(); ++i)

s[i] = (static_cast<long>(points[i][0] * points[i][0] +

points[i][1] * points[i][1]) << 32) | i;

std::sort(begin(s), end(s));

vector<vector<int>> ans(K);

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

ans[i] = points[static_cast<int>(s[i])];

return ans;

}

};

Python3

# Author: Huahua, running time: 528 ms

class Solution:

def kClosest(self, points, K):

return sorted(points, key = lambda p: p[0]**2 + p[1]**2)[0:K]