Huahua’s Tech Road

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

By zxi on October 31, 2020

Given n points on a 2D plane where points[i] = [x_i, y_i], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.

Example 2:

Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3

Constraints:

n == points.length
2 <= n <= 10⁵
points[i].length == 2
0 <= x_i, y_i <= 10⁹

Solution: Sort by x coordinates

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

C++

class Solution {

public:

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

sort(begin(points), end(points), [](const auto& p1, const auto& p2) {

return p1[0] != p2[0] ? p1[0] < p2[0] : p1[1] < p2[1];

});

int ans = 0;

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

ans = max(ans, points[i][0] - points[i - 1][0]);

return ans;

}

};

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

By zxi on October 31, 2020

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution: Hashtable + Sorting

Use a hashtable to track the frequency of each number.

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

C++

class Solution {

public:

vector<int> frequencySort(vector<int>& nums) {

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

sort(begin(nums), end(nums), [&](int a, int b) {

if (freq[a] != freq[b]) return freq[a] < freq[b];

return a > b;

});

return nums;

}

};

花花酱 LeetCode 61. Rotate List

By zxi on October 28, 2020

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution: Find the prev of the new head

Step 1: Get the tail node T while counting the length of the list.
Step 2: k %= l, k can be greater than l, rotate k % l times has the same effect.
Step 3: Find the previous node P of the new head N by moving (l – k – 1) steps from head
Step 4: set P.next to null, T.next to head and return N

Time complexity: O(n) n is the length of the list
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* rotateRight(ListNode* head, int k) {

if (!head) return head;

int l = 1;

ListNode* tail = head;

while (tail->next) { tail = tail->next; ++l; }

k %= l;

if (k == 0) return head;

ListNode* prev = head;

while (--l > k) prev = prev->next;

ListNode* new_head = prev->next;

tail->next = head;

prev->next = nullptr;

return new_head;

}

};

Java

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

class Solution {

public ListNode rotateRight(ListNode head, int k) {

if (head == null) return null;

int l = 1;

ListNode tail = head;

while (tail.next != null) {

tail = tail.next;

++l;

}

k %= l;

if (k == 0) return head;

ListNode prev = head;

for (int i = 0; i < l - k - 1; ++i) {

prev = prev.next;

}

ListNode new_head = prev.next;

prev.next = null;

tail.next = head;

return new_head;

}

Python3

class Solution:

def rotateRight(self, head: ListNode, k: int) -> ListNode:

if not head: return head

tail = head

l = 1

while tail.next:

tail = tail.next

l += 1

k = k % l

if k == 0: return head

prev = head

for _ in range(l - k - 1): prev = prev.next

new_head = prev.next

tail.next = head

prev.next = None

return new_head

花花酱 LeetCode 1632. Rank Transform of a Matrix

By zxi on October 28, 2020

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

The rank is an integer starting from 1.
If two elements p and q are in the same row or column, then:
- If p < q then rank(p) < rank(q)
- If p == q then rank(p) == rank(q)
- If p > q then rank(p) > rank(q)
The rank should be as small as possible.

It is guaranteed that answer is unique under the given rules.

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2:

Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]

Example 3:

Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

Example 4:

Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

Solution: Union Find

Group cells by their values, process groups (cells that have the same value) in ascending order (smaller number has smaller rank).

For cells that are in the same row and same cols union them using union find, they should have the same rank which equals to max(max_rank_x[cols], max_rank_y[rows]) + 1.

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

C++

// Author: Huahua

class DSU {

public:

DSU(int n): p_(n, -1) {}

int find(int x) {

return p_[x] == -1 ? x : p_[x] = find(p_[x]);

}

void merge(int x, int y) {

x = find(x), y = find(y);

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

}

private:

vector<int> p_;

};

class Solution {

public:

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

vector<vector<int>> ans(m, vector<int>(n));

map<int, vector<pair<int, int>>> mp; // val -> {positions}

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

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

mp[matrix[y][x]].emplace_back(x, y);

vector<int> rx(n), ry(m);

for (const auto& [val, ps]: mp) {

DSU dsu(n + m);

vector<vector<pair<int, int>>> cc(n + m); // val -> {positions}

for (const auto& [x, y]: ps)

dsu.merge(x, y + n);

for (const auto& [x, y]: ps)

cc[dsu.find(x)].emplace_back(x, y);

for (const auto& ps: cc) {

int rank = 1;

for (const auto& [x, y]: ps)

rank = max(rank, max(rx[x], ry[y]) + 1);

for (const auto& [x, y]: ps)

rx[x] = ry[y] = ans[y][x] = rank;

}

return ans;

}

};

花花酱 LeetCode 1631. Path With Minimum Effort

By zxi on October 24, 2020

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute differencein heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10⁶

Solution: “Lazy BFS / DP”

dp[y][x] = min(max(dp[ty][tx], abs(h[ty][tx] – h[y][x]))) (x, y) and (tx, ty) are neighbors
repeat this process for at most rows * cols times.
if dp does not change after one round which means we found the optimal solution and can break earlier.

Time complexity: O(n^2*m^2))
Space complexity: O(nm)

C++

// Author: Huahua, 824 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const int r = heights.size();

const int c = heights[0].size();

int dp[100][100];

memset(dp, 0x7f, sizeof(dp));

dp[0][0] = 0;

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

for (int k = 0; k < r * c; ++k) {

bool stable = true;

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

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

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

int tx = x + dirs[d];

int ty = y + dirs[d + 1];

if (tx < 0 || tx == c || ty < 0 || ty == r) continue;

int t = max(dp[ty][tx], abs(heights[ty][tx] - heights[y][x]));

if (t < dp[y][x]) {

stable = false;

dp[y][x] = t;

}

if (stable) break;

}

return dp[r - 1][c - 1];

}

};

Solution 2: Binary Search + BFS

Use binary search to guess a cost and then check whether there is path that is under the cost.

Time complexity: O(mn*log(max(h) – min(h)))
Space complexity: O(mn)

C++

// Author: Huahua, 620 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const int rows = heights.size();

const int cols = heights[0].size();

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

auto bfs = [&](int cost) -> bool {

queue<pair<int, int>> q;

vector<int> seen(cols * rows);

q.emplace(0, 0);

seen[0] = 1;

while (!q.empty()) {

auto [cx, cy] = q.front(); q.pop();

if (cx == cols - 1 && cy == rows - 1) return true;

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

int x = cx + dirs[i];

int y = cy + dirs[i + 1];

if (x < 0 || x == cols || y < 0 || y == rows) continue;

if (abs(heights[cy][cx] - heights[y][x]) > cost) continue;

if (seen[y * cols + x]++) continue;

q.emplace(x, y);

}

return false;

};

int l = 0, r = 1e6 + 1;

while (l < r) {

const int m = l + (r - l) / 2;

if (bfs(m)) {

r = m;

} else {

l = m + 1;

}

return l;

}

};

Solution 3: Dijkstra

Time complexity: O(mnlog(mn))
Space complexity: O(mn)

C++

// Author: Huahua, 216 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

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

const int rows = heights.size();

const int cols = heights[0].size();

using Node = pair<int, int>;

priority_queue<Node, vector<Node>, greater<Node>> q;

vector<int> dist(rows * cols, INT_MAX / 2);

q.emplace(0, 0);

dist[0] = 0;

while (!q.empty()) {

auto [t, u] = q.top(); q.pop();

if (u == rows * cols - 1) return t;

if (t > dist[u]) continue;

const int ux = u % cols;

const int uy = u / cols;

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

const int x = ux + dirs[i];

const int y = uy + dirs[i + 1];

if (x < 0 || x == cols || y < 0 || y == rows) continue;

const int v = y * cols + x;

const int c = abs(heights[uy][ux] - heights[y][x]);

if (max(t, c) >= dist[v]) continue;

q.emplace(dist[v] = max(t, c), v);

}

return -1;

}

};

Huahua's Tech Road

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

Solution: Sort by x coordinates

C++

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

Solution: Hashtable + Sorting

C++

花花酱 LeetCode 61. Rotate List

Solution: Find the prev of the new head

C++

Java

Python3

花花酱 LeetCode 1632. Rank Transform of a Matrix

Solution: Union Find

C++

花花酱 LeetCode 1631. Path With Minimum Effort

Solution: “Lazy BFS / DP”

C++

Solution 2: Binary Search + BFS

C++

Solution 3: Dijkstra

C++