Huahua's Tech Road

花花酱 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 2656. Maximum Sum With Exactly K Elements

By zxi on April 30, 2023

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

Select an element m from nums.
Remove the selected element m from the array.
Add a new element with a value of m + 1 to the array.
Increase your score by m.

Return the maximum score you can achieve after performing the operation exactly k times.

Example 1:

Input: nums = [1,2,3,4,5], k = 3
Output: 18
Explanation: We need to choose exactly 3 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]
For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]
For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]
So, we will return 18.
It can be proven, that 18 is the maximum answer that we can achieve.

Example 2:

Input: nums = [5,5,5], k = 2
Output: 11
Explanation: We need to choose exactly 2 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]
For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]
So, we will return 11.
It can be proven, that 11 is the maximum answer that we can achieve.

Constraints:

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

Solution: Greedy

Always to chose the largest element from the array.

We can find the largest element of the array m, then the total score will be
m + (m + 1) + (m + 2) + … + (m + k – 1),
We can use summation formula of arithmetic sequence to compute that in O(1)
ans = (m + (m + k – 1)) * k / 2

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

C++

// Author: Huahua

class Solution {

public:

int maximizeSum(vector<int>& nums, int k) {

int m = *max_element(begin(nums), end(nums));

return (m + m + k - 1) * k / 2;

}

};

花花酱 LeetCode 2642. Design Graph With Shortest Path Calculator

By zxi on April 29, 2023

There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [from_i, to_i, edgeCost_i] meaning that there is an edge from from_i to to_i with the cost edgeCost_i.

Implement the Graph class:

Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

Example 1:

Input
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
Output
[null, 6, -1, null, 6]

Explanation

Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]); g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.
g.shortestPath(0, 3); // return -1. There is no path from 0 to 3. 
g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above. 
g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

Constraints:

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= from_i, to_i, from, to, node1, node2 <= n - 1
1 <= edgeCost_i, edgeCost <= 10⁶
There are no repeated edges and no self-loops in the graph at any point.
At most 100 calls will be made for addEdge.
At most 100 calls will be made for shortestPath.

Solution 1: Floyd-Washall

Time complexity:
Init O(n³)
addEdge O(n²)
shortestPath O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Graph {

public:

Graph(int n, vector<vector<int>>& edges):

n_(n),

d_(n, vector<long>(n, 1e18)) {

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

d_[i][i] = 0;

for (const vector<int>& e : edges)

d_[e[0]][e[1]] = e[2];

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

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

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

d_[i][j] = min(d_[i][j], d_[i][k] + d_[k][j]);

}

void addEdge(vector<int> edge) {

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

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

d_[i][j] = min(d_[i][j], d_[i][edge[0]] + edge[2] + d_[edge[1]][j]);

}

int shortestPath(int node1, int node2) {

return d_[node1][node2] >= 1e18 ? -1 : d_[node1][node2];

}

private:

int n_;

vector<vector<long>> d_;

};

Solution 2: Dijkstra

Time complexity:
Init: O(|E|) ~ O(n²)
AddEdge: O(1)
ShortestPath: O(|V|*log(|E|)) ~ O(n*logn)

Space complexity: O(E|) ~ O(n²)

C++

// Author: Huahua

class Graph {

public:

Graph(int n, vector<vector<int>>& edges): n_(n), g_(n) {

for (const auto& e : edges)

g_[e[0]].emplace_back(e[1], e[2]);

}

void addEdge(vector<int> edge) {

g_[edge[0]].emplace_back(edge[1], edge[2]);

}

int shortestPath(int node1, int node2) {

vector<int> dist(n_, INT_MAX);

dist[node1] = 0;

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

q.emplace(0, node1);

while (!q.empty()) {

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

if (u == node2) return d;

for (const auto& [v, c] : g_[u])

if (dist[u] + c < dist[v]) {

dist[v] = dist[u] + c;

q.emplace(dist[v], v);

}

return -1;

}

private:

int n_;

vector<vector<pair<int, int>>> g_;

};

花花酱 LeetCode 2641. Cousins in Binary Tree II

By zxi on April 29, 2023

Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins’ values.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Return the root of the modified tree.

Note that the depth of a node is the number of edges in the path from the root node to it.

Example 1:

Input: root = [5,4,9,1,10,null,7]
Output: [0,0,0,7,7,null,11]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 5 does not have any cousins so its sum is 0.
- Node with value 4 does not have any cousins so its sum is 0.
- Node with value 9 does not have any cousins so its sum is 0.
- Node with value 1 has a cousin with value 7 so its sum is 7.
- Node with value 10 has a cousin with value 7 so its sum is 7.
- Node with value 7 has cousins with values 1 and 10 so its sum is 11.

Example 2:

Input: root = [3,1,2]
Output: [0,0,0]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 3 does not have any cousins so its sum is 0.
- Node with value 1 does not have any cousins so its sum is 0.
- Node with value 2 does not have any cousins so its sum is 0.

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁴

Solution: Level Order Sum

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

DFS, two passes

C++

// Author: Huahua

class Solution {

public:

TreeNode* replaceValueInTree(TreeNode* root) {

unordered_map<TreeNode*, int> parentSum;

parentSum[nullptr] = root->val;

vector<int> levelSums;

function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int depth) {

if (!node) return;

if (levelSums.size() <= depth) {

levelSums.push_back(0);

}

levelSums[depth] += node->val;

if (node->left) {

parentSum[node] += node->left->val;

dfs(node->left, depth + 1);

}

if (node->right) {

parentSum[node] += node->right->val;

dfs(node->right, depth + 1);

}

};

function<void(TreeNode*, TreeNode*, int)> dfs2 =

[&](TreeNode* node, TreeNode* p, int depth) {

if (!node) return;

node->val = levelSums[depth] - parentSum[p];

dfs2(node->left, node, depth + 1);

dfs2(node->right, node, depth + 1);

};

dfs(root, 0);

dfs2(root, nullptr, 0);

return root;

}

};

BFS, one+ pass

C++

// Author: Huahua

class Solution {

public:

TreeNode* replaceValueInTree(TreeNode* root) {

root->val = 0;

queue<TreeNode*> q({root});

while (!q.empty()) {

vector<TreeNode*> nodes;

int sum = 0;

for (int s = q.size(); s; --s) {

TreeNode* node = q.front(); q.pop();

nodes.push_back(node);

if (node->left) {

q.push(node->left);

sum += node->left->val;

}

if (node->right) {

q.push(node->right);

sum += node->right->val;

}

for (TreeNode* node : nodes) {

int val = sum - (node->left ? node->left->val : 0)

- (node->right ? node->right->val : 0);

if (node->left) node->left->val = val;

if (node->right) node->right->val = val;

}

return root;

}

};