Posts tagged as “medium”

花花酱 LeetCode 2770. Maximum Number of Jumps to Reach the Last Index

By zxi on July 11, 2023

You are given a 0-indexed array nums of n integers and an integer target.

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target

Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

Example 1:

Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3.

Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5.

Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.

Constraints:

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Solution: DP

Let dp(i) denotes the maximum jumps from index i to index n-1.

For each index i, try jumping to all possible index j.

dp(i) = max(1 + dp(j)) if j > i and abs(nums[j] – nums[i) <= target else -1

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

Python3

# Author: Huahua

class Solution:

def maximumJumps(self, nums: List[int], target: int) -> int:

n = len(nums)

@cache

def dp(i):

if i == n - 1: return 0

ans = -1

for j in range(i + 1, n):

if abs(nums[j] - nums[i]) <= target and dp(j) != -1:

ans = max(ans, 1 + dp(j))

return ans

return dp(0)

花花酱 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;

}

};