Posts tagged as “hard”

花花酱 LeetCode 1735. Count Ways to Make Array With Product

By zxi on January 23, 2021

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [n_i, k_i], find the number of different ways you can place positive integers into an array of size n_i such that the product of the integers is k_i. As the number of ways may be too large, the answer to the i^th query is the number of ways modulo 10⁹ + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the i^th query.

Example 1:

Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation: Each query is independent.
[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].
[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].
[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 10⁹ + 7 = 50734910.

Example 2:

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]

Constraints:

1 <= queries.length <= 10⁴
1 <= n_i, k_i <= 10⁴

Solution1: DP

let dp(n, k) be the ways to have product k of array size n.
dp(n, k) = sum(dp(n – 1, i)) where i is a factor of k and i != k.
base case:
dp(0, 1) = 1, dp(0, *) = 0
dp(i, 1) = C(n, i)
e.g.
dp(2, 6) = dp(1, 1) + dp(1, 2) + dp(1, 3)
= 2 + 1 + 1 = 4
dp(4, 4) = dp(3, 1) + dp(3, 2)
= dp(3, 1) + dp(2, 1)
= 4 + 6 = 10

Time complexity: O(sum(k_i))?
Space complexity: O(sum(k_i))?

C++

// Author: Huahua

class Solution {

public:

vector<int> waysToFillArray(vector<vector<int>>& queries) {

constexpr int kMod = 1e9 + 7;

int n = 0;

unordered_map<int, int> c, dp;

function<int(int, int)> cnk = [&](int n, int k) {

if (k > n) return 0;

if (k == 0 || k == n) return 1;

int& ans = c[(n << 16) | k];

if (!ans) ans = (cnk(n - 1, k - 1) + cnk(n - 1, k)) % kMod;

return ans;

};

function<int(int, int)> dfs = [&](int s, int k) -> int {

if (s == 0) return k == 1;

if (k == 1) return cnk(n, s);

int& ans = dp[(s << 16) | k];

if (ans) return ans;

for (int i = 1; i * i <= k; ++i) {

if (k % i) continue;

if (i != 1)

ans = (ans + dfs(s - 1, k / i)) % kMod;

if (i * i != k)

ans = (ans + dfs(s - 1, i)) % kMod;

}

return ans;

};

vector<int> ans;

for (const auto& q : queries) {

dp.clear();

n = q[0];

ans.push_back(dfs(n, q[1]));

}

return ans;

}

};

花花酱 LeetCode 1719. Number Of Ways To Reconstruct A Tree

By zxi on January 9, 2021

You are given an array pairs, where pairs[i] = [x_i, y_i], and:

There are no duplicates.
x_i < y_i

Let ways be the number of rooted trees that satisfy the following conditions:

The tree consists of nodes whose values appeared in pairs.
A pair [x_i, y_i] exists in pairs if and only if x_i is an ancestor of y_i or y_i is an ancestor of x_i.
Note: the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

0 if ways == 0
1 if ways == 1
2 if ways > 1

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

Example 1:

Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.

Example 2:

Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3:

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.

Constraints:

1 <= pairs.length <= 10⁵
1 <= x_i< y_i <= 500
The elements in pairs are unique.

Solution: Bitset

Time complexity: O(E*V)
Space complexity: O(V^2)

C++

// Author: Huahua

class Solution {

public:

int checkWays(vector<vector<int>>& pairs) {

// Construct a map, key is the node, value is the accessible nodes.

unordered_map<int, bitset<501>> m;

for (auto& e : pairs)

m[e[0]][e[0]] = m[e[1]][e[1]] = m[e[0]][e[1]] = m[e[1]][e[0]] = 1;

// The tree must have one+ node/root that has paths to all the nodes.

if (!any_of(begin(m), end(m), [&m](const auto& kv) {

return kv.second.count() == m.size();})) return 0;

int multiple = 0;

for (const auto& e : pairs) {

// For each pair, check whether one can be the parent of another

// that can conver all the children nodes.

const auto& all = m[e[0]] | m[e[1]];

const int r0 = m[e[0]] == all;

const int r1 = m[e[1]] == all;

if (r0 + r1 == 0) return 0;

// If both can be parents, there can be multiple trees.

multiple |= r0 * r1;

}

return 1 + multiple;

}

};

Python3

# Author: Huahua

class Solution:

def checkWays(self, pairs: List[List[int]]) -> int:

m = defaultdict(set)

for u, v in pairs:

m[u] |= set((u, v))

m[v] |= set((u, v))

if not any(len(m[x]) == len(m) for x in m):

return 0

multiple = 0

for u, v in pairs:

union = m[u] | m[v]

ru, rv = int(m[u] == union), int(m[v] == union)

if not ru + rv: return 0

multiple |= ru * rv

return 1 + multiple

花花酱 LeetCode 1713. Minimum Operations to Make a Subsequence

By zxi on January 3, 2021

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

Example 2:

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

Constraints:

1 <= target.length, arr.length <= 10⁵
1 <= target[i], arr[i] <= 10⁹
target contains no duplicates.

Solution: Reduce to LIS

The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.
Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problem to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.

e.g.
target: [6,4,8,1,3,2] => [0, 1, 2, 3, 4, 5]
array: [4,7,6,2,3,8,6,1] => [1,-1, 0, 5, 4, 2, 0, 3] => [1, 0, 5, 4, 2, 3]
and the LIS is [0, 2, 3] => [6, 8, 1], we need to insert the rest of the numbers.
Ans = len(target) – len(LIS)

Time complexity: O(nlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

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

unordered_map<int, int> m;

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

m[A[i]] = i;

vector<int> dp;

for (int x : B) {

auto mit = m.find(x);

if (mit == end(m)) continue;

const int idx = mit->second;

if (dp.empty() || idx > dp.back())

dp.push_back(idx);

else

*lower_bound(begin(dp), end(dp), idx) = idx;

}

return A.size() - dp.size();

}

};

Python3

# Author: Huahua

class Solution:

def minOperations(self, A: List[int], B: List[int]) -> int:

m = {x: i for i, x in enumerate(A)}

dp = []

for x in B:

if x not in m: continue

if not dp or m[x] > dp[-1]: dp.append(m[x])

else: dp[bisect_left(dp, m[x])] = m[x]

return len(A) - len(dp)

花花酱 LeetCode 1707. Maximum XOR With an Element From Array

By zxi on December 27, 2020

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Solution: Trie on the fly

We can build the trie on the fly by sorting nums in ascending order and queries by its limit, insert nums into the trie up the limit.

Time complexity: O(nlogn + QlogQ)
Space complexity: O(n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children{nullptr, nullptr} {}

Trie* children[2];

};

class Solution {

public:

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {

const int n = nums.size();

sort(begin(nums), end(nums));

const int Q = queries.size();

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

queries[i].push_back(i);

sort(begin(queries), end(queries), [](const auto& q1, const auto& q2) {

return q1[1] < q2[1];

});

Trie root;

auto insert = [&](int num) {

Trie* node = &root;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = new Trie();

node = node->children[bit];

}

};

auto query = [&](int num) {

Trie* node = &root;

int sum = 0;

for (int i = 31; i >= 0; --i) {

if (!node) return -1;

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum |= (1 << i);

node = node->children[1 - bit];

} else {

node = node->children[bit];

}

return sum;

};

vector<int> ans(Q);

int i = 0;

for (const auto& q : queries) {

while (i < n && nums[i] <= q[1]) insert(nums[i++]);

ans[q[2]] = query(q[0]);

}

return ans;

}

};

花花酱 LeetCode 1703. Minimum Adjacent Swaps for K Consecutive Ones

By zxi on December 26, 2020

You are given an integer array, nums, and an integer k. nums comprises of only 0‘s and 1‘s. In one move, you can choose two adjacent indices and swap their values.

Return the minimum number of moves required so that nums has k consecutive 1‘s.

Example 1:

Input: nums = [1,0,0,1,0,1], k = 2
Output: 1
Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.

Example 2:

Input: nums = [1,0,0,0,0,0,1,1], k = 3
Output: 5
Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].

Example 3:

Input: nums = [1,1,0,1], k = 2
Output: 0
Explanation: nums already has 2 consecutive 1's.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is 0 or 1.
1 <= k <= sum(nums)

Solution: Prefix Sum + Sliding Window

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

We only care positions of 1s, we can move one element from position x to y (assuming x + 1 ~ y are all zeros) in y – x steps. e.g. [0 0 1 0 0 0 1] => [0 0 0 0 0 1 1], move first 1 at position 2 to position 5, cost is 5 – 2 = 3.

Given a size k window of indices of ones, the optimal solution it to use the median number as center. We can compute the cost to form consecutive numbers:

e.g. [1 4 7 9 10] => [5 6 7 8 9] cost = (5 – 1) + (6 – 4) + (9 – 8) + (10 – 9) = 8

However, naive solution takes O(n*k) => TLE.

We can use prefix sum to compute the cost of a window in O(1) to reduce time complexity to O(n)

First, in order to use sliding window, we change the target of every number in the window to the median number.
e.g. [1 4 7 9 10] => [7 7 7 7 7] cost = (7 – 1) + (7 – 4) + (7 – 7) + (9 – 7) + (10 – 7) = (9 + 10) – (1 + 4) = right – left.
[5 6 7 8 9] => [7 7 7 7 7] takes extra 2 + 1 + 1 + 2 = 6 steps = (k / 2) * ((k + 1) / 2), these extra steps should be deducted from the final answer.

C++

class Solution {

public:

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

vector<long> s(1);

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

if (nums[i])

s.push_back(s.back() + i);

const int n = s.size();

long ans = 1e10;

const int m1 = k / 2, m2 = (k + 1) / 2;

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

const long right = s[i + k] - s[i + m1];

const long left = s[i + m2] - s[i];

ans = min(ans, right - left);

}

return ans - m1 * m2;

}

};

Python3

class Solution:

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

ans = 1e10

s = [0]

for i, v in enumerate(nums):

if v: s.append(s[-1] + i)

n = len(s)

m1 = k // 2

m2 = (k + 1) // 2

for i in range(n - k):

right = s[i + k] - s[i + m1]

left = s[i + m2] - s[i]

ans = min(ans, right - left)

return ans - m1 * m2