Posts tagged as “medium”

花花酱 LeetCode 2662. Minimum Cost of a Path With Special Roads

By zxi on April 30, 2023

You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY).

The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.

There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1_i, y1_i, x2_i, y2_i, cost_i] indicates that the i^th special road can take you from (x1_i, y1_i) to (x2_i, y2_i) with a cost equal to cost_i. You can use each special road any number of times.

Return the minimum cost required to go from (startX, startY) to (targetX, targetY).

Example 1:

Input: start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
Output: 5
Explanation: The optimal path from (1,1) to (4,5) is the following:
- (1,1) -> (1,2). This move has a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) -> (3,3). This move uses the first special edge, the cost is 2.
- (3,3) -> (3,4). This move has a cost of |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5). This move uses the second special edge, the cost is 1.
So the total cost is 1 + 2 + 1 + 1 = 5.
It can be shown that we cannot achieve a smaller total cost than 5.

Example 2:

Input: start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation: It is optimal to not use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.

Constraints:

start.length == target.length == 2
1 <= startX <= targetX <= 10⁵
1 <= startY <= targetY <= 10⁵
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1_i, x2_i <= targetX
startY <= y1_i, y2_i <= targetY
1 <= cost_i <= 10⁵

Solution: Dijkstra

Create a node for each point in special edges as well as start and target.
Add edges for special roads (note it’s directional)
Add edges for each pair of node with default cost, i.e. |x1-x2| + |y1-y2|
Run Dijkstra’s algorithm

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

C++

// Author: Huahua

class Solution {

public:

int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {

unordered_map<long, int> ids;

vector<pair<int, int>> pos;

auto getId = [&](int x, int y) {

const auto key = ((unsigned long)x << 32) | y;

if (ids.count(key)) return ids[key];

const int id = ids.size();

ids[key] = id;

pos.emplace_back(x, y);

return id;

};

const int s = getId(start[0], start[1]);

const int t = getId(target[0], target[1]);

vector<vector<pair<int, int>>> g;

auto addEdge = [&](int x1, int y1, int x2, int y2, int c = INT_MAX) {

int n1 = getId(x1, y1);

int n2 = getId(x2, y2);

if (n1 == n2) return;

while (g.size() <= max(n1, n2)) g.push_back({});

int cost = min(c, abs(x1 - x2) + abs(y1 - y2));

g[n1].emplace_back(cost, n2);

// directional for special edge

if (c == INT_MAX) g[n2].emplace_back(cost, n1);

};

for (const auto& r : specialRoads)

addEdge(r[0], r[1], r[2], r[3], r[4]);

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

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

addEdge(pos[i].first, pos[i].second,

pos[j].first, pos[j].second);

vector<int> dist(ids.size(), INT_MAX);

dist[s] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

q.emplace(0, s);

while (!q.empty()) {

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

if (d > dist[u]) continue;

if (u == t) return d;

for (auto [c, v] : g[u])

if (d + c < dist[v])

q.emplace(dist[v] = d + c, v);

}

return -1;

}

};

花花酱 LeetCode 2661. First Completely Painted Row or Column

By zxi on April 30, 2023

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

Example 1:

Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]
Output: 2
Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2:

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Output: 3
Explanation: The second column becomes fully painted at arr[3].

Constraints:

m == mat.length
n = mat[i].length
arr.length == m * n
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= arr[i], mat[r][c] <= m * n
All the integers of arr are unique.
All the integers of mat are unique.

Solution: Map + Counter

Use a map to store the position of each integer.

Use row counters and column counters to track how many elements have been painted.

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

C++

// Author: Huahua

class Solution {

public:

int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {

const int m = mat.size();

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

vector<int> rows(m);

vector<int> cols(n);

vector<pair<int, int>> pos(m * n + 1);

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

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

pos[mat[i][j]] = {i, j};

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

auto [r, c] = pos[arr[i]];

if (++rows[r] == n) return i;

if (++cols[c] == m) return i;

}

return -1;

}

};

花花酱 LeetCode 2658. Maximum Number of Fish in a Grid

By zxi on April 30, 2023

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

A land cell if grid[r][c] = 0, or
A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

Catch all the fish at cell (r, c), or
Move to any adjacent water cell.

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.

Constraints:

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

Solution: Connected Component

Find the connected component that has the max sum.

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

C++

// Author: Huahua

class Solution {

public:

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

const int m = grid.size();

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

function<int(int, int)> dfs = [&](int r, int c) {

if (r < 0 || r >= m || c < 0 || c >= n || !grid[r][c]) return 0;

return exchange(grid[r][c], 0)

+ dfs(r - 1, c) + dfs(r, c - 1) + dfs(r + 1, c) + dfs(r, c + 1);

};

int ans = 0;

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

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

ans = max(ans, dfs(r, c));

return ans;

}

};

花花酱 LeetCode 2657. Find the Prefix Common Array of Two Arrays

By zxi on April 30, 2023

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Solution 1: Bitset

Use bitsets to store the numbers seen so far for each array, and use sA & sB to count the common elements.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

bitset<51> sA;

bitset<51> sB;

vector<int> ans;

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

sA.set(A[i]);

sB.set(B[i]);

ans.push_back((sA & sB).count());

}

return ans;

}

};

Solution 2: Counter

Use a counter to track the frequency of each element, when the counter[x] == 2, we found a pair.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

vector<int> count(A.size() + 1);

vector<int> ans;

for (int i = 0, s = 0; i < A.size(); ++i) {

if (++count[A[i]] == 2) ++s;

if (++count[B[i]] == 2) ++s;

ans.push_back(s);

}

return ans;

}

};

花花酱 LeetCode 2640. Find the Score of All Prefixes of an Array

By zxi on April 29, 2023

We define the conversion array conver of an array arr as follows:

conver[i] = arr[i] + max(arr[0..i]) where max(arr[0..i]) is the maximum value of arr[j] over 0 <= j <= i.

We also define the score of an array arr as the sum of the values of the conversion array of arr.

Given a 0-indexed integer array nums of length n, return an array ans of length n where ans[i] is the score of the prefix nums[0..i].

Example 1:

Input: nums = [2,3,7,5,10]
Output: [4,10,24,36,56]
Explanation: 
For the prefix [2], the conversion array is [4] hence the score is 4
For the prefix [2, 3], the conversion array is [4, 6] hence the score is 10
For the prefix [2, 3, 7], the conversion array is [4, 6, 14] hence the score is 24
For the prefix [2, 3, 7, 5], the conversion array is [4, 6, 14, 12] hence the score is 36
For the prefix [2, 3, 7, 5, 10], the conversion array is [4, 6, 14, 12, 20] hence the score is 56

Example 2:

Input: nums = [1,1,2,4,8,16]
Output: [2,4,8,16,32,64]
Explanation: 
For the prefix [1], the conversion array is [2] hence the score is 2
For the prefix [1, 1], the conversion array is [2, 2] hence the score is 4
For the prefix [1, 1, 2], the conversion array is [2, 2, 4] hence the score is 8
For the prefix [1, 1, 2, 4], the conversion array is [2, 2, 4, 8] hence the score is 16
For the prefix [1, 1, 2, 4, 8], the conversion array is [2, 2, 4, 8, 16] hence the score is 32
For the prefix [1, 1, 2, 4, 8, 16], the conversion array is [2, 2, 4, 8, 16, 32] hence the score is 64

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Prefix Sum

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> findPrefixScore(vector<int>& nums) {

vector<long long> ans(nums.size());

for (int i = 0, m = 0; i < nums.size(); ++i) {

m = max(m, nums[i]);

ans[i] = (i ? ans[i - 1] : 0) + nums[i] + m;

}

return ans;

}

};