Posts tagged as “hard”

花花酱 LeetCode 1585. Check If String Is Transformable With Substring Sort Operations

By zxi on September 13, 2020

Given two strings s and t, you want to transform string s into string t using the following operation any number of times:

Choose a non-empty substring in s and sort it in-place so the characters are in ascending order.

For example, applying the operation on the underlined substring in "14234" results in "12344".

Return true if it is possible to transform string s into string t. Otherwise, return false.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "84532", t = "34852"
Output: true
Explanation: You can transform s into t using the following sort operations:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"

Example 2:

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"34521" -> "23451"
"23451" -> "23415"

Example 3:

Input: s = "12345", t = "12435"
Output: false

Example 4:

Input: s = "1", t = "2"
Output: false

Constraints:

s.length == t.length
1 <= s.length <= 10⁵
s and t only contain digits from '0' to '9'.

Solution: Queue

We can move a smaller digit from right to left by sorting two adjacent digits.
e.g. 18572 -> 18527 -> 18257 -> 12857, but we can not move a larger to the left of a smaller one.

Thus, for each digit in the target string, we find the first occurrence of it in s, and try to move it to the front by checking if there is any smaller one in front of it.

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

C++

class Solution {

public:

bool isTransformable(string s, string t) {

vector<deque<int>> idx(10);

for (int i = 0; i < s.length(); ++i)

idx[s[i] - '0'].push_back(i);

for (char c : t) {

const int d = c - '0';

if (idx[d].empty()) return false;

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

if (!idx[i].empty() && idx[i].front() < idx[d].front())

return false;

idx[d].pop_front();

}

return true;

}

};

Python3

class Solution:

def isTransformable(self, s: str, t: str) -> bool:

idx = defaultdict(deque)

for i, c in enumerate(s):

idx[int(c)].append(i)

for c in t:

d = int(c)

if not idx[d]: return False

for i in range(d):

if idx[i] and idx[i][0] < idx[d][0]: return False

idx[d].popleft()

return True

花花酱 LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

By zxi on September 6, 2020

Alice and Bob have an undirected graph of n nodes and 3 types of edges:

Type 1: Can be traversed by Alice only.
Type 2: Can be traversed by Bob only.
Type 3: Can by traversed by both Alice and Bob.

Given an array edges where edges[i] = [type_i, u_i, v_i] represents a bidirectional edge of type type_i between nodes u_i and v_i, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if it’s impossible for the graph to be fully traversed by Alice and Bob.

Example 1:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Example 2:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Example 3:

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

Constraints:

1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
All tuples (type_i, u_i, v_i) are distinct.

Solution: Greedy + Spanning Tree / Union Find

Use type 3 (both) edges first.

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

C++

class DSU {

public:

DSU(int n): p_(n + 1), e_(0) {

iota(begin(p_), end(p_), 0);

}

int find(int x) {

if (p_[x] == x) return x;

return p_[x] = find(p_[x]);

}

int merge(int x, int y) {

int rx = find(x);

int ry = find(y);

if (rx == ry) return 1;

p_[rx] = ry;

++e_;

return 0;

}

int edges() const { return e_; }

private:

vector<int> p_;

int e_;

};

class Solution {

public:

int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {

int ans = 0;

DSU A(n), B(n);

for (const auto& e: edges) {

if (e[0] != 3) continue;

ans += A.merge(e[1], e[2]);

B.merge(e[1], e[2]);

}

for (const auto& e: edges) {

if (e[0] == 3) continue;

DSU& d = e[0] == 1 ? A : B;

ans += d.merge(e[1], e[2]);

}

return (A.edges() == n - 1 && B.edges() == n - 1) ? ans : -1;

}

};

python3

class DSU:

def __init__(self, n: int):

self.p = list(range(n))

self.e = 0

def find(self, x: int) -> int:

if x != self.p[x]: self.p[x] = self.find(self.p[x])

return self.p[x]

def merge(self, x: int, y: int) -> int:

rx, ry = self.find(x), self.find(y)

if rx == ry: return 1

self.p[rx] = ry

self.e += 1

return 0

class Solution:

def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:

A, B = DSU(n + 1), DSU(n + 1)

ans = 0

for t, x, y in edges:

if t != 3: continue

ans += A.merge(x, y)

B.merge(x, y)

for t, x, y in edges:

if t == 3: continue

d = A if t == 1 else B

ans += d.merge(x, y)

return ans if A.e == B.e == n - 1 else -1

花花酱 LeetCode 1575. Count All Possible Routes

By zxi on September 5, 2020

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.

Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).

Return the count of all possible routes from start to finish.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

Example 4:

Input: locations = [2,1,5], start = 0, finish = 0, fuel = 3
Output: 2
Explanation: There are two possible routes, 0 and 0 -> 1 -> 0.

Example 5:

Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

Constraints:

2 <= locations.length <= 100
1 <= locations[i] <= 10^9
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

Solution: DP

dp[j][f] := # of ways to start from city ‘start’ to reach city ‘j’ with fuel level f.

dp[j][f] = sum(dp[i][f + d]) d = dist(i, j)

init: dp[start][fuel] = 1

Time complexity: O(n^2*fuel)
Space complexity: O(n*fuel)

C++

class Solution {

public:

int countRoutes(vector<int>& x, int start, int finish, int fuel) {

constexpr int kMod = 1e9 + 7;

const int n = x.size();

vector<vector<int>> dp(n, vector<int>(fuel + 1));

dp[start][fuel] = 1;

for (int f = fuel; f > 0; --f)

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

if (!dp[i][f] || abs(x[i] - x[finish]) > f) continue; // pruning.

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

const int d = abs(x[i] - x[j]);

if (i == j || f < d) continue;

dp[j][f - d] = (dp[j][f - d] + dp[i][f]) % kMod;

}

return accumulate(begin(dp[finish]), end(dp[finish]), 0LL) % kMod;

}

};

Python3

# Author: Huahua

class Solution:

def countRoutes(self, x: List[int], start: int, finish: int, fuel: int) -> int:

@lru_cache(None)

if f < 0: return 0

return (sum(dp(j, f - abs(x[i] - x[j]))

for j in range(len(x)) if i != j) + (i == finish)) % (10**9 + 7)

return dp(start, fuel)

花花酱 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST

By zxi on August 30, 2020

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

Example 2:

Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.

Example 4:

Input: nums = [3,1,2,5,4,6]
Output: 19

Example 5:

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
All integers in nums are distinct.

Solution: Recursion + Combinatorics

For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l / r nodes, we have ways(left) / ways(right) different ways to re-arrange those nodes. So the total # of ways is:
C(l + r, l) * ways(l) * ways(r)
Don’t forget to minus one for the final answer.

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

C++

class Solution {

public:

int numOfWays(vector<int>& nums) {

const int n = nums.size();

const int kMod = 1e9 + 7;

vector<vector<int>> cnk(n + 1, vector<int>(n + 1, 1));

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

for (int j = 1; j < i; ++j)

cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % kMod;

function<int(vector<int>)> trees = [&](const vector<int>& nums) {

const int n = nums.size();

if (n <= 2) return 1;

vector<int> left;

vector<int> right;

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

if (nums[i] < nums[0]) left.push_back(nums[i]);

else right.push_back(nums[i]);

long ans = cnk[n - 1][left.size()];

ans = (ans * trees(left)) % kMod;

ans = (ans * trees(right)) % kMod;

return static_cast<int>(ans);

};

return trees(nums) - 1;

}

};

python3

class Solution:

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

def ways(nums):

if len(nums) <= 2: return 1

l = [x for x in nums if x < nums[0]]

r = [x for x in nums if x > nums[0]]

return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)

return (ways(nums) - 1) % (10**9 + 7)

花花酱 LeetCode 1563. Stone Game V

By zxi on August 23, 2020

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice’s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice’s is initially zero.

Return the maximum score that Alice can obtain.

Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.

Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28

Example 3:

Input: stoneValue = [4]
Output: 0

Constraints:

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6

Solution: Range DP + Prefix Sum

dp[l][r] := max store Alice can get from range [l, r]
sum_l = sum(l, k), sum_r = sum(k + 1, r)
dp[l][r] = max{
dp[l][k] + sum_l if sum_l < sum_r
dp[k+1][r] + sum_r if sum_r < sum_l
max(dp[l][k], dp[k+1][r])) + sum_l if sum_l == sum_r)
} for k in [l, r)

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

class Solution {

public:

int stoneGameV(vector<int>& stoneValue) {

const int n = stoneValue.size();

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stoneValue[i];

vector<vector<int>> cache(n, vector<int>(n, -1));

// max value alice can get from range [l, r]

function<int(int, int)> dp = [&](int l, int r) {

if (l == r) return 0;

int& ans = cache[l][r];

if (ans != -1) return ans;

for (int k = l; k < r; ++k) {

// left: [l, k], right: [k + 1, r]

int sum_l = sums[k + 1] - sums[l];

int sum_r = sums[r + 1] - sums[k + 1];

if (sum_l > sum_r)

ans = max(ans, sum_r + dp(k + 1, r));

else if (sum_l < sum_r)

ans = max(ans, sum_l + dp(l, k));

else

ans = max(ans, sum_l + max(dp(l, k), dp(k + 1, r)));

}

return ans;

};

return dp(0, n - 1);

}

};