Huahua’s Tech Road

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

}

};

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

}

};

花花酱 LeetCode 2639. Find the Width of Columns of a Grid

By zxi on April 29, 2023

You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.

For example, if grid = [[-10], [3], [12]], the width of the only column is 3 since -10 is of length 3.

Return an integer array ans of size n where ans[i] is the width of the i^th column.

The length of an integer x with len digits is equal to len if x is non-negative, and len + 1 otherwise.

Example 1:

Input: grid = [[1],[22],[333]]
Output: [3]
Explanation: In the 0^th column, 333 is of length 3.

Example 2:

Input: grid = [[-15,1,3],[15,7,12],[5,6,-2]]
Output: [3,1,2]
Explanation: 
In the 0^th column, only -15 is of length 3.
In the 1^st column, all integers are of length 1. 
In the 2^nd column, both 12 and -2 are of length 2.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-10⁹ <= grid[r][c] <= 10⁹

Solution: Simulation

Note: width of ‘0’ is 1.

Time complexity: O(m*n*log(x))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

for (int j = 0; j < grid[0].size(); ++j) {

int maxWidth = 1;

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

int x = grid[i][j];

int width = 0;

if (x < 0) {

x = -x;

++width;

}

while (x) {

x /= 10;

++width;

}

maxWidth = max(maxWidth, width);

}

ans.push_back(maxWidth);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2656. Maximum Sum With Exactly K Elements

Solution: Greedy

C++

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

Solution 1: Floyd-Washall

C++

Solution 2: Dijkstra

C++

花花酱 LeetCode 2641. Cousins in Binary Tree II

Solution: Level Order Sum

C++

C++

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

Solution: Prefix Sum

C++

花花酱 LeetCode 2639. Find the Width of Columns of a Grid

Solution: Simulation

C++